문제 : [백준] 실버V_24174: 알고리즘 수업 - 힙 정렬 2
🤔 문제 분석
최소 힙의 동작에 대한 메서드를 슈도 코드로 나타낸 것 같다. 이 슈도 코드를 해석하는 것이 가장 큰 힌트이자 어려움인 것 같다.
힙을 정렬하는 heap_sort 메서드는 안에 build_min_heap, 루트 노드와 i번째 노드가 교환이 이루어지고 그 노드가 힙 성질을 성립하는지 확인하는 heapify 메서드가 있다. build_min_heap 안에서는 A배열의 n/2 ~ 1 인덱스 까지 heapify 메서드가 실행된다. heapify메서드는 해당 인덱스 노드의 자식노드끼리 비교하고, 해당 인덱스와 비교하여 교환이 이루어지고 재귀 동작이 이루어진다.
-> 사실 쓰면서도 정리가 잘 되지 않는다. 재귀 문제를 마주하면 항상 이러는 듯 하다.
입력 예시
5 2
2 5 1 4 3(1) (heapify(A, 2, 5)) -> 2 3 1 4 5
(2) (heapify(A, 1, 5)) -> 1 3 2 4 5 <<<<<<< 출력(3) (A[1] <-> A[5]) -> 5 3 2 4 1
(4) (heapify(A, 1, 4)) -> 2 3 5 4 1(5) (A[1] <-> A[4]) -> 4 3 5 2 1
(6) (heapify(A, 1, 3)) -> 3 4 5 2 1(7) (A[1] <-> A[3]) -> 5 4 3 2 1
(8) (heapify(A, 1, 2)) -> 4 5 3 2 1(9) (A[1] <-> A[2]) -> 5 4 3 2 1
---> 총 9회 교환이 발생하고 두 번째 교환 직후 배열 A의 모습은 1 3 2 4 5
✍️ 내가 작성한 풀이
슈도 코드가 나와 있어서 슈도 코드를 해석하면 쉽게 해결 할 수 있을 줄 알았는데, 슈도코드 분석조차 쉽지 않았던 것 같다. 결국 다른분의 풀이를 보고 분석하기로 했다.
👀 다른사람 풀이
heapSort(int[])
public static void heapSort(int[] arr) {
buildMinHeap(arr, arr.length - 1);
for (int i = arr.length - 1; i > 1 ; i--) {
swap(arr, 1 , i);
heapify(arr, 1, i - 1);
}
}A 배열을 입력 받아서 모든 동작이 이루어지게 작성하셨다. 슈도코드에 있는 메서드 외에도 노드를 교환하는 swap(arr, 1, i) 도 있는 것을 볼 수 있다.
buildMinHeap(int[], int)
public static void buildMinHeap(int[] arr, int num) {
for (int i = num / 2; i >= 1 && !isOut; i--) {
heapify(arr, i, num);
}
}메서드명을 봐서는 최소힙으로 만든다는 것 같은데, N/2 인덱스 부터 1까지 감소하며 heapify를 실행하는 동작 같다. -> N/2 인덱스부터 1까지인 이유는 리프 인덱스는 자식 노드가 없기 때문이지 않을까 싶다.
heapify(int[], int, int)
public static void heapify(int[] arr, int k, int num) {
int left = 2 * k;
int right = 2 * k + 1;
int smaller = -1;
if (right <= num) {
smaller = arr[left] < arr[right] ? left : right;
} else if (left <= num) {
smaller = left;
} else {
return;
}
if (arr[smaller] < arr[k]) {
swap(arr,k,smaller);
heapify(arr, smaller, num);
}
}핵심 동작을 하는 메서드 heapify는 배열(A)과 특정 인덱스 k, 배열의 전체 크기를 나타내는 n(num)를 매개변수로 받아 동작하는데, k의 왼쪽 자식노드 인덱스(left) 오른쪽 자식노드 인덱스(right)를 비교하여 더 작은 값을 지닌 자식노드와, 부모노드[k]의 값을 비교하여 교환이 이루어지고, 그 자식노드를 다시 heapify 하는 동작인 것 같다.
swap(int[], int, int)
public static void swap (int[] arr, int a, int b){
cnt++;
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
if(cnt == target){
StringBuilder sb = new StringBuilder();
for (int i = 1; i < arr.length; i++) {
sb.append(arr[i]);
sb.append(" ");
}
System.out.print(sb.toString());
isOut = true;
}
}배열 A의 a노드와 b노드를 교체하고, 교체횟수를 증가 시킨 후, 목표한 교환 횟수(K)인지 검증하여, 목표에 도달 하였다면, 출력하고 isOut을 true로 변경(목표한 교체 횟수에 도달 or 힙 정렬을 완료했지만 isOut이 true가 아닐시)하여 동작을 멈추게하는 것 같다.
💪 배운점
- 힙 구조 동작, 특히 최소 힙의 동작에 대해 다시 생각해볼 수 있게 되었다.
- 슈도코드 해석을 위해 슈도코드 작성법에 대해서 찾아 볼 수 있었고, 조금이나마 해석할 수 있게 되었다.
- 재귀 동작에 대해서 다시한번 생각해볼 수 있게 되었다.
완벽하게 이해한 것이 아니라 아쉬움이 많이 남는 문제 같다. 나중에 다시한번 풀어봐야할 것 같다.
✅ 참고
