Study with book/Algorithms

[백준]힙 정렬


백준저지

[힙 정렬]https://www.acmicpc.net/problem/2220


힙 자료구조 삭제에 대한 이해도를 가지고

백준에서 제시된 예시 (5, 4, 3, 2, 1)(6, 5, 3, 2, 4, 1)에 대해 삭제를 펜으로 몇 번 해보았는데

규칙이 금방 발견되었다.

동적 알고리즘의 냄새가 물씬 나서 혹시나 하는 생각에 (2 ~ 1)(3 ~ 1)부터 (6 ~ 1)까지 힙을 그려 봤는데 동적 알고리즘이었다.

 

[구현]

먼저 첫 번째 규칙은 최댓값을 삭제 했을 때, 무조건 전 값의 힙 모양이 나온다는 것이었다.

예를 들어 (6, 5, 3, 2, 4, 1)에서 6을 삭제하게 되면 무조건 5일 때 최대로 swap이 되는 모양의 힙이 나온다는 것이다. , (5, 4, 3, 2, 1)이 된다.

마찬가지로 (5, 4, 3, 2, 1)에서 5를 삭제하게 되면 4일 때 최대로 swap되는 모양의 힙(4, 2, 3, 1)이 나온다는 것이다.

두 번째 규칙최대의 swap을 위해 무조건 1이 힙에서 가장 끝에 위치해야 된다는 점이다.

즉 다시 말해서 최댓값이 삭제가 되면 (힙 삭제 규칙 상) 1이 최댓값 자리로 swap(이 스왑은 힙 삭제 규칙이기 때문에 교환 횟수로 간주하지 않는다.)이 되게 되고, 이 때부터 1은 힙 정렬의 끝의 자리를 목표점으로 교환이 되어야 한다는 점이다.

예를 들어 3의 경우 (4, 3, 2, 1)(4, 2, 3, 1)2가지 경우가 존재하게 되는데,

(4, 3, 2, 1)의 경우 (1, 3, 2) (3, 1, 2) swapCnt++

(3, 1, 2)의 경우 (2, 1)

1번의 교환이 이루어지게 되는데, 이는 swap1의 위치가 힙의 끝에 위치하지 않기 때문이다.

그렇다면 (4, 2, 3, 1)의 경우를 보자.

(4, 2, 3, 1)의 경우 (1, 2, 3) (3, 2, 1) swapCnt++

(3, 2, 1)의 경우 (1, 2) (2, 1) swapCnt++

2번의 교환이 이루어지게 된다. 여기서 중요한 것은 (4, 2, 3, 1)의 삭제 결과 (3, 2, 1)은 최대로 swap이 많이 되는 힙 모양이다.

 

그렇다면 구현을 어떻게 해야 될까?

필자는 동적 알고리즘답게 2부터 시작해서 입력 값까지의 힙 모양을 구하는 방식으로 구현을 진행하였다.

i=1일 때, vecArr[1]=1로 세팅을 하고,

i=2일 때, 힙의 맨 마지막에 2를 삽입(vecArr[2]=2)하고 숫자 1을 힙의 맨 마지막에 두어야 하니까 vecArr[1]vecArr[2]swap한다.

그리고 최대 힙 모양을 맞춰야 하니까 while(20번째 라인)을 통해 최대 힙 모양을 만든다.

사실 이게 전부다. 필자도 풀면서 혹시나 하는 마음에 몇 개를 더 해봤는데 한 번 해보시길 바란다.

결과는 변함이 없을 것이다.

i=3일 때, 힙의 맨 마지막에 3을 삽입(vecArr[3]=3)하고 숫자 1을 힙의 맨 마지막에 두어야 하니까 (2, 1, 3)모양에서 vecArr[2]vecArr[3]을 교환한다. 그러면 (2, 3, 1) 모양이 되고 최대 힙을 위해 vecArr[1]vecArr[2]를 교환한다. 그러면 (3, 2, 1)일 때 swap이 가장 많이 되는 힙이 된다.

자 마지막으로 i=4일 때를 진행해보자

i=4일 때, 힙의 맨 마지막에 4를 삽입(vecArr[4]=4)하고 숫자 1을 힙의 맨 마지막에 두어야 하니까 (3, 2, 1, 4)모양에서 vecArr[3]vecArr[4]를 교환한다. 이쯤 되면 1의 위치는 항상 맨 마지막에 존재한다는 것을 눈치 챘을 것이다. 그러면 (3, 2, 4, 1)이 되고 최대 힙을 맞추기 위해 vecArr[3]vecArr[1]을 교환한다. 이것도 INDEX로 따지면 2를 나눈 값과 교환하는 것을 눈치 챌 수 있다. 그러면 (4, 2, 3, 1)이 되고 4일 때 교환이 가장 많이 되는 힙 배열은 (4, 2, 3, 1)이 된다.

이 후 과정은 생략하도록 하겠다.

아래는 필자가 짠 코드이다.

혹시 더 빠르거나 더 좋은 알고리즘이 있다면 코멘트 바란다.


#include <iostream>
#include <vector>

using namespace std;

void SwapArr(vector<int>& vecArr, int n1, int n2) {
	int tmp = vecArr[n1];
	vecArr[n1] = vecArr[n2];
	vecArr[n2] = tmp;
}

int main(void) {
	int num;
	cin >> num;
	vector<int> vecArr(num+1, 0);
	vecArr[1] = 1;
	for (int i = 2; i <= num; i++) {
		vecArr[i] = i; int j = i-1;
		SwapArr(vecArr, i, i - 1);
		while (j != 1) {
			SwapArr(vecArr, j, j / 2);
			j = j / 2;
		}
	}

	for (int i = 1; i <= num; i++)
		cout << vecArr[i] << " ";

	return 0;
}


'Study with book > Algorithms' 카테고리의 다른 글

[백준]이진탐색트리  (2) 2017.01.12
[백준]트리  (2) 2017.01.02
[백준]2xn 타일링2  (0) 2016.12.23
[백준]2xn 타일링  (0) 2016.12.23
[백준]순열 사이클  (0) 2016.12.22