★정렬 최상급1 - 1문제()★

🏅 플래티넘 이상의 난이도는 각 문제의 접근방향 뿐만 아니라, 사고과정 흐름까지 최대한 리마인드하는 방식으로 기억하자!

 

🏅 정렬관련 포스팅 하단 참조

 

🏅 정렬에는 정말 많은 알고리즘이 있다. 플래이상의 난이도급 문제에서 정렬을 어떤 방식으로 접근하는 지 알아보자

---

★ 2220 힙 정렬 ★

 

import math
n = int(input())
if n==1:print(1)
elif n==2:print(2,1)
elif n==3:print(3,2,1)
else:
    arr = [3,2,1]
    for i in range(n-3):
        end=int(math.log(i+3,2))
        idx=len(arr)-1
        for _ in range(end):
            arr[idx],arr[(idx-1)//2]=arr[(idx-1)//2],arr[idx]
            idx=(idx-1)//2
        arr[0]=(i+4)
        arr.append(1)

    print(*arr)

 

🤹 heapify() 알고리즘에서 진행되는 swap 연산 횟수를 최대로 하는 heap을 구하는 문제.

 

🤹 일단 heapsort의 시간 복잡도는 $O(nlogn)$이며, heapsort란, binary heap이라는 자료구조에서, 최상단 노드를 매번 heapify()마다 빼고 제쳐둔 뒤, 맨 마지막 원소를 최상단 노드로 다시 올려 다시 heapify()를 반복하는 sorting이다.

 

(하단 heapsort 포스팅 참조)

 

🤹 이 때, heapify()에서 heap 구조를 유지하기 위해 parent node 기준, 두 자식 node와 대소비교를 하는 과정이 있다. 이 때, heap의 기준을 충족하기 위해 swap이 진행될 수 있는데, 초기에 어떻게 heap 구조를 유지하면 swap 횟수를 최대화할 수 있는지가 관건.

 

🤹 * 재귀적으로 접근

ex) 최대 swap 횟수가 나오는, 예시로 든 n=6일 때의 초기 heap 구조는 [6, 5, 3, 2, 4, 1]이다. 이를 heapify()하는 과정을 일일이 살펴본다면, 아래 그림과 같다.

 

※ swap 개수가 최대가 되기 위해서는, 부모와 자식간의 비교연산에서 무조건 swap이 진행되게 하면 된다. 이를 구현할 수 있고, 위 그림과 같이 최종 1만 남을 때 까지 모든 과정을 해부하면, comparison 과정 제외 1부터 5까지의 max-heap snapshot이 포함되어 있으며, 이는 곧 1부터 5까지의 최대 swap 개수를 가지는 heapify() 과정도 포함(재귀)되어 있다는 뜻이다.

 

→ 그렇다면 거꾸로, n=3([3,2,1]) 과정부터 시작한다면, 가장 끝의 원소 1을 한 층 올라가며 swap하고, 최상단 node를 1로 더한 결과인 4를 넣고, 끝의 자리에 1을 추가한다. / n=4의 경우 로그값은 2이므로 heap의 높이가 2로 증가. 각 높이별로 모두 swap되게끔, 방금 추가한 1을 최상단 node까지 올라가며 swap. 앞서 한 결과와 똑같이 1로 더한 결과인 5를 최종 1의 자리인 최상단 node에 넣고, 마지막에 1 추가. / 이렇게 진행한다면 제일 최솟값 1을 가지고 움직이므로 모든 height별 swap이 진행되고, 이는 곧 모든 height별로 무조건 swap이 일어나기에 swap 횟수가 최대가 됨을 뜻하며, 최종 swap 갯수를 가지는 원하는 n 개수의 heap을 만들 수 있다!

 

※ 재귀적으로 접근해 heapify() 과정을 풀어 이해하고, 거꾸로 다시 올라가며 heap을 생성하는 흐름 (heapsort 알고리즘을 거꾸로) ※

 

→ 코드 분석)

①  주어진 높이까지 올라가야 하므로, $\lfloor \log_2 (i+3) \rfloor$까지 swap과정 진행

② python(first index 0) 기준, 자식 node(idx)를 기준으로 했을 때 부모 node의 index는 $\lfloor \cfrac{(idx-1)}{2} \rfloor$. 따라서 두 개의 index에 해당하는 원소를 서로 swap. 이후 idx update

Binary heap

③ 마무리로 append(1)로 맨 끝에 1을 추가하고, 첫 번째 원소(heap 최상단)로 기존 배열 최댓값에 1을 더한 값 추가

---