본문 바로가기
반응형

Algorithm Problem/Codility

 (91)
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..
Lesson 10. Prime and composite numbers - Flags #2 (속도 개선-1) 1. 속도 개선 아이디어최대 Flag 개수(K)는 Peak 개수와 동일하다.또한 K만큼 꽂기 위해서는, 최소 \( K * (K - 1) \) 만큼의 거리가 확보되어야 한다. 위 성질을 이용하면, 전체 탐색을 줄일 수 있다.Peak 개수를 구한다Peak 간 '총 거리'를 구한다'총 거리'에, (이론적으로) 꽂을 수 있는 최대 Flag 수(K)를 구한다. { 총 거리 \( >= K * (K - 1) \) }구해진 K개를 기준으로, Flag를 꽂을 수 있는지 확인한다.가능하면 return K, 불가능하면 K를 줄여나간다. 2. 코드 (C++)int solution(vector &A) { //peak 개수 구하기 vector peaks = {}; for(size_t i = 1; i A[i - ..
반응형

티스토리툴바