[Competitive Programming] – 연습문제 2장 <작성중>

2.3.8)

최대 힙에서 두 번째로 제일 큰 수가 루트의 자식이 아니라면, 루트와 해당 노드의 거리는 최소 2이며, 경로 내에 최소 하나의 다른 노드가 있다. 최대 힙의 성질에 따라 이 노드는 2번째보다 큰 수이므로 가정에 모순으로 두 번째로 제일 큰 수는 반드시 루트의 자식이다. 세 번째로 큰 수의 경우는 두 번째로 큰 노드가 루트의 왼쪽 자식인 경우 그 노드의 왼쪽 자식인 경우이면 루트의 오른쪽 자식보다 크더라도 최대 힙의 성질을 만족하므로 반드시 루트의 자식일 필요가 없다. 세 번째로 큰 수의 경우 가능한 경우는 루트의 자식이거나, 루트의 자식의 자식인 경우 뿐이다.

2.3.9)

최대 힙을 사용하는 경우는 O(n)의 시간이 든다. 최소 힙을 사용하는 경우는 재귀적 탐색 중 v보다 큰 값의 노드부터는 탐색할 필요가 없지만 최악의 경우는 결국 O(n)이다.

2.3.10)

n을 k개 단위로 나누어 정렬을 할 때 시간 복잡도는 O(n log k)이다. 이후 각 (n / k)개의 부분에서 최솟값을 뽑아내는 것은 O(n / k)이고, 이것을 k개 반복하면 O(n / k * k) = O(n)이다.

따라서 시간복잡도는 O(n + n log k)가 된다.

2.3.11)

 

C++ STL next_permutation

C++ STL 중 <algorithm>에 포함되어 있는 next_permuation은 배열의 시작과 끝을 입력받아 현재 배열보다 알파벳 순으로 바로 다음의 순열을 생성한다. 리턴 값은 next_permutation이 존재하면 1, 존재하지 않는 마지막 순열이면 0을 리턴하며 인자로 넣은 배열의 값을 변경하는 식으로 새로운 순열을 만든다. UVa 문제 146번이 여기에 해당하며 예제 코드는 다음과 같다.