Lesson 6. Sorting - MaxProductOfThree
1. 문제A non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P For example, array A such that:A[0] = -3A[1] = 1A[2] = 2A[3] = -2A[4] = 5A[5] = 6contains the following example triplets:(0, 1, 2), product is −3 * 1 * 2 = −6(1, 2, 4), product is 1 * 2 * 5 = 10(2, 4, 5), product is 2 * 5 * 6 = 60Your goal is to find the maximal produ..
Lesson 5. Perfix Sums - MinAvgTwoSlice #2 (속도 개선)
1. 속도 개선 아이디어평균에 대한 고찰이 필요하다. A \( \leq \) B 일 때,(A, B)의 평균은 A 보다 크거나 같다. 예)A(2) + B(2) = 4, 평균 2A(2) + B(4) = 6, 평균 3 \( A \leq B \leq C \leq D \) 일 때,(A, B, C, D)의 평균은 (A + B + C + D) / 4 = { (A, B)평균 + (C,D)평균 } / 2(A, B, C, D)의 평균은 (A, B)평균 보다 크거나 같다. 즉, 구하고자 하는 평균은, 평균을 구하기 위해 더해지는 요소의 값들 중, 최저값보다 크거나 같다. 우리는 가장 작은 그룹의, 가장 작은 평균 값을 찾아야 한다.왜냐하면, (A, B, C, D) 평균 값은, (A, B) 두 개의 평균 값보다 작아질 수 없..
Lesson 5. Perfix Sums - GenomicRangeQuery #2 (속도 개선)
1. 속도 개선 아이디어각 문자가 나타난 횟수를 미리 저장해둔다. 예를들어 S = CAGCCTA 일 때, 다음과 같이 부분 합(Prefix Sums)을 생각해 볼 수 있다.index문자열SACGT0초기 상태00001C01002CA11003CAG11104CAGC12105CAGCC13106CAGCCT13118CAGCCTA2311 P = 2, Q = 4 를 생각해보자.S[2]까지의 부분합은 [1, 1, 0, 0] 이다.S[4]까지의 부분합은 [1, 3, 1, 0] 이다. (초기 상태가 있기 때문에, index 5를 봐야한다.)이제 S[4] - S[2]를 해보면, [0, 2, 1, 0] 임을 알 수 있다. 즉, S[2] ~ S[4] 구간에서 C와 G가 나타났음을 알 수 있다. 2. C++ (코드)vector ..
