구간 트리. [12899]
[1. 문제 설명] 아래 쿼리를 수행하는 프로그램을 작성한다. A. 수열 S 에 자연수 X 를 추가한다. (append) B. 수열 S 에 포함된 숫자 중 X 번째로 작은 수를 출력하고, 수열에서 제거한다. [2. 풀이 접근] 간단한 풀이를 생각해보면, 트립(treap) 의 적용을 생각해 볼 수 있다. 트립을 통해 원소의 삽입과 삭제를 logN 에 할 수 있다. 또한 K번째 원소도 쉽게 찾을 수 있다. 그러나 구현이 살짝 까다로울 수 있으니, 나중에 다시 정리해보도록 하고, 구간 트리를 사용하여 풀이를 해볼 수 있다. 자연수 X 의 범위는 1 이상 2,000,000 이하이므로, 구간을 [1, 2,000,000] 을 하는 구간 트리를 생각 해 볼 수 있다. 각 노드가 저장하는 값은 구간이 포함하는 원소의 ..
구간 트리. [9345]
[1. 문제 설명] ... [2. 풀이 접근] 1차 풀이 (실패) 구간의 합을 구하여 같은지 확인 한다. => [1, 5] 구간에 1~5 DVD 가 존재 할 경우 [1, 5] 구간의 부분 합은 1+2+3+4+5=15 가 되어야 한다. 반례) => [2, 4] 구간이 1,3,5 로 이루어진 경우 2+3+4 == 1+3+5 == 9 => 둘다 같은 값이나, 2, 3, 4 가 있어야 하나 1, 3, 5 가 있으므로 대여 조건을 만족하지 않는다. 올바른 풀이 구간의 최대, 최소를 모두 갖고 있는 경우 성공. [2, 4] 구간은 2,3,4 가 존재해야 한다. [2, 4] 구간의 최소, 최대는 2, 4 인 것이 자명하다. 시리즈는 1씩 증가하므로, [2, 4] 구간이 2 와 4 만 존재 할 수 는 없다. [3. 코..
구간 트리. [1517]
[1. 문제 설명] 1 1 2 3 5 정렬 된 상태 3 2 1 5 1 최초 상태 2 3 1 5 1 3, 2 swap 2 1 3 5 1 3, 1 swap 2 1 3 1 5 5, 1 swap 1 2 3 1 5 2, 1 swap 1 2 1 3 5 3, 1 swap 1 1 2 3 5 2, 1 swap 3 이 3번의 swap 을 유도하고, 5 가 1번의 swap 2 가 2번의 swap 총 6번의 swap 이 발생하였다. [2. 풀이 접근] 이해가 된 부분 까지만 정리 하도록 swap 의 주체는 인접한 두 값 중 큰 값 이다. 예를들어, 3 과 2 의 swap 이 발생 했을 때, 3 입장에서 한번 swap, 2 입장에서 한번 swap, 총 2번의 swap 이 발생과 같은 중복 처리는 있어선 안된다. 3 이 2 를 ..
