본문 바로가기
반응형

Algorithm Problem

 (93)
Lesson 11. Sieve of Eratosthenes - CountSemiPrimes #1 1. 문제A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.You are given two non-empty arrays P and Q, each consisting of M integers. These arrays rep..
Lesson 11. Sieve of Eratosthenes - CountNonDivisible #2 (속도 개선) 1. 속도 개선 아이디어배열A의 요소가 가질 수 있는 약수의 개수(혹은 약수가 아닌 수의 개수)는 A.size()를 초과할 수 없다.여기서 약수가 아닌 값을 찾지 말고, 약수인 수를 찾아서 제외한다. 왜냐하면 이전에 사용했던 약수 찾기 알고리즘을 사용하면, N의 약수는 \( O(\sqrt{N}) \) 속도로 찾을 수 있기 때문이다. 2. 코드 (C++)찾은 약수의 개수를 빠르게 제거하기 위해, 배열A의 요소를 map로 정리해 둔다.#include #include //약수 찾기vector get_divisors(int n){ vector divisors = {}; int i = 1; while(i solution(vector &A) { vector result = {}; ma..
Lesson 11. Sieve of Eratosthenes - CountNonDivisible #1 1. 문제You are given an array A consisting of N integers.For each number A[i] such that 0 ≤ i For example, consider integer N = 5 and array A such that:A[0] = 3A[1] = 1A[2] = 2 A[3] = 3 A[4] = 6For the following elements:A[0] = 3, the non-divisors are: 2, 6,A[1] = 1, the non-divisors are: 3, 2, 3, 6,A[2] = 2, the non-divisors are: 3, 3, 6,A[3] = 3, the non-divisors are: 2, 6,A[4] = 6, there aren't..
Lesson 10. Prime and composite numbers - Peaks #3 (속도 개선-2) 이미 Peaks #2에서 100%를 달성했지만, 조금 더 수정해보자. 1. 속도 개선 아이디어Peak 조건을 제외하고, 최대 블럭 수를 구한다면, 최대 블럭 수는 몇 개 일까? 정답, N개그렇다면 Peak 조건을 추가해서, 최대  블럭수를 구한다면, 최대 블럭 수는 몇 개 일까? Peak개 이전까지는 최소 약수로 시작해서, 최대 블럭 수를 찾아봤다.이번에는 반대로 최대 블럭 수(Peak 개)로 시작해서, 최소 블럭 수(1개) 순서로 찾아보면 어떨까? 이렇게 하면, 중간에 '약수를 구하는 코드'와 '약수 정렬 코드'를 제거할 수 있다. 2. 코드 (C++)peak 구하기 → 최대 블럭 수 구하기int solution(vector &A) { //peak 구하기 vector peaks = {}; ..
Lesson 10. Prime and composite numbers - Peaks #2 (속도 개선-1) 1. 이전 코드 문제점나누어진 각 블럭에 peak값이 있는지 확인하기 위해, peak 배열을 전체 탐색하고 있다.예제를 3개의 블럭으로 나눴을 때, 각 블럭에 peak가 있는지, 없는지 어떻게 확인하는지 자세히 뜯어보자.A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]A[11]123434123462 index로 나타내면 다음과 같다.  block: (0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11)peak: (3, 5, 10) 첫번째 블럭: peak index 3 포함됨두번째 블럭: peak index 3 미포함 / peak index 5 포함세번째 블럭: peak index 3 미포함 / peak index 5 미포함 / peak index 10..
Lesson 10. Prime and composite numbers - Peaks #1 1. 문제A non-empty array A consisting of N integers is given.A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 A[P + 1].For example, the following array A:A[0] = 1A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2has exactly three peaks: 3, 5, 10.We want to divide this array into blocks con..
Lesson 10. Prime and composite numbers - Flags #4 (번외) 지금까지(#1, #2, #3)와는 다른 방식으로 문제를 풀어본다. 그 동안은 대략 다음과 같은 과정으로 문제를 풀었다.거리(D)를 구한다거리(D)를 기반으로 최대 Flag개수(K)를 구한다최대 Flag개수(K)를 검증한다 이번에는 배열A의 각 요소에서 가장 가까운 Peak값을 기록해두고, 이를 이용해서 전체 탐색을 줄여본다. 예시)A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]A[11]153434123462 가장 가까운 Peak(next_peak) 정보를 추가해보자.A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]A[11]1534341234621133551010101010-1 A[0]의 가장 가까운 Peak는 A[1]이다.A[1]의 가장 ..
Lesson 10. Prime and composite numbers - Flags #3 (속도 개선-2) 1. 속도 개선 아이디어이전에 구했던 수식을 좀 더 살펴봐야 한다. 총거리(D) \( >= K * (K - 1) \) 위 식은 다음과 같이 정리할 수 있다.\( D >= K * (K - 1) \)\( D >= K^{2} - K \)\( \textcolor{red}{D + K >= K^{2}} \) 여기서 \( D \) 와 \( K^{2} \)의 관계에 대해서 생각해보자.\( \textcolor{red}{D + K >= K^{2}} \) 성립하기 위해서는, \( \textcolor{red}{\sqrt{D} >= K} \) 이어야 한다.왜냐하면 \( \textcolor{red}{\sqrt{D} >= K} \) 이면, \( \textcolor{red}{D >= K^{2}} \) 이기 때문에, \( \textc..
반응형

티스토리툴바