문제 해결력을 높이는 알고리즘과 자료 구조 6장 연습 문제 풀이

GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이

연습 문제 풀이에 많은 시간을 쏟았다.

새로 배우고 깨달은 것이 많아 간단히 정리하고자 한다.

 

6.1번

좌표 압축, 모든 요소가 서로 다르다는 조건이 있으므로 unique는 필수적이지 않다.

 

6.2번

각 b[i]에 대응하는 a[i]와 c[i]의 개수를 잘 세주자.

 

6.3번

2개씩 나누어서 조합하자. O(NlogN)은 N=10^6일 때도 잘 돌아간다.

 

6.4번

최소 거리가 x일 때 모든 소를 배치할 수 있는가?

 

6.5번

K번째로 작은 값이 x 이상인가?

= x 미만인 요소가 K개 미만인가?

 

6.6번

실수 이분 탐색, 실수를 출력할 때는 특별한 이유가 없다면 높은 정밀도로 출력하자.

 

6.7번

수열 m의 중앙값이 x 이상인가?

= 수열 m에 x보다 작은 요소가 (N * (N + 1) / 2 / 2)개 이하인가?

 

구간 [l, r]의 중앙값은 x보다 작다.

= 구간 [l, r] 내에 x보다 작은 요소가 ((r - l + 1) / 2 + 1)개 이상이다.

 

변형된 구간 합을 정의하자.

psum[i] = psum[i - 1] + (A[i] < x ? 1 : -1);

 

아래 조건을 만족하는 (i, j)의 개수를 O(NlogN)에 세주면 된다.

i < j && psum[i] < psum[j]

 

이를 위하여 Fenwick Tree를 사용한다.

Segment Tree나 pbds를 사용할 수도 있으나 상수가 크다.

 

Fenwick Tree 사용 시 실행 시간은 대략 100 ms이다.

pbds 사용 시 실행 시간은 대략 1400 ms이다.

 

끝

끝