본문 바로가기

Algorithm Problem

 (93)
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 - ..
Lesson 10. Prime and composite numbers - Flags #1 1. 문제A non-empty array A consisting of N integers is given.A peak is an array element which is larger than its neighbours. More precisely, it is an index P such that 0 A[P + 1].For example, the following array A:A[0] = 1A[1] = 5 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 four peaks: elements 1, 3, 5 and 10.You are going on a trip to a ..
Lesson 10. Prime and composite numbers - MinPerimeterRectangle 1. 문제An integer N is given, representing the area of some rectangle.The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.For example, given integer N = 30, rectangles of area 30 are:(1, 30), with a perimeter of 62,(2, ..
Lesson 10. Prime and composite numbers - CountFactors #3 (속도 개선-2) (CountFactors #2)에서 100%가 안된 이유가 무엇일까? 알고리즘의 개선이 필요하다기 보다는, 약간의 코드 최적화가 필요하다. 아래 코드에서는 while(조건문)을 수정했다.#include int solution(int N) { int cnt = 0; int i = 1; //while(i * i  이전 코드의 조건문은 N과 비교하기 전, 항상 \( i \times i \) 연산이 필요했다.변경된 코드에서는 \( i \times i \) 연산없이 N과 바로 비교할 수 있다. 조건문을 변경하면서, sqrt(N) 함수를 호출하고 있다.sqrt(N) 함수의 경우, 내부적으로 1번만 연산하고 계속 재활용 된다.왜냐하면, sqrt(N)의 값은 바뀌지 않기 때문이다. (상수)
Lesson 10. Prime and composite numbers - CountFactors #2 (속도 개선-1) 1. 속도 개선 아이디어약수는 쌍으로 존재하는 특징을 이용하면 전체 탐색을 하지 않아도 된다. 수학적 이론: 약수와 소수구현: 약수의 개수 구하기 2. 코드 (C++)int solution(int N) { int cnt = 0; int i = 1; while(i * i  3. 결과
Lesson 10. Prime and composite numbers - CountFactors #1 1. 문제A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).Write a function:  int solution(int N);that, given a positive integer N, returns the number of its factors.For example, given N = 24, the function should return 8, because 24 has 8 factors, namely..
Lesson 9. Maximum slice problem - MaxDoubleSliceSum #2 (속도 개선) 1. 속도 개선 아이디어부분 집합에 대해 살펴봐야 한다.이 문제에서 부분 집합(double slice)은 사실상 배열을 2등분 하는 것과 같다. 배열을 2등분 한다 = 부분 집합의 크기가 정해져 있다 = 미리 계산해 놓을 수 있다(Prefix Sums) 2. 예제 분석양 끝은 항상 포함되지 않고, 양 끝을 제외한 중간 값들은, Y값을 제외하고는 반드시 포함되어야 한다. 3. 문제풀이 전략왼쪽 부분과 오른쪽 부분의 합을 미리 계산한다. (Prefix Sums)맨 앞 요소와 맨 뒤 요소는 Prefix Sums에 포함시키지 않는다.index Y를 기준으로 왼쪽과 오른쪽을 구분한다.index Y를 최대 합 계산에서 (편하게)제외시키기 위해 Prefix Sums 배열을 A와 동일하게 만든다.부분 합이 음수가 나오..
Lesson 9. Maximum slice problem - MaxDoubleSliceSum #1 1. 문제A non-empty array A consisting of N integers is given.A triplet (X, Y, Z), such that 0 ≤ X The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].For example, array A such that:A[0] = 3A[1] = 2A[2] = 6 A[3] = -1A[4] = 4A[5] = 5A[6] = -1A[7] = 2contains the following example double slices:double slice (0, 3, 6), sum is 2 ..

티스토리툴바