Gidhub BE Developer

[BOJ] 2220. 힙 정렬

2018-02-19
goodGid
Algorithm

Problem

Problem URL : 힙 정렬

Explain Logic

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

예를 들어 (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번의 교환이 이루어지게 되는데,

이는 swap된 1의 위치가 힙의 끝에 위치하지 않기 때문이다.


그렇다면 (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문을 통해 최대 힙 모양을 만든다.

그리고 이게 전부다.


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일 때,

힙의 맨 마지막에 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)이 된다.


위 설명은 출처 Blog에서 발췌해

(내 기준)가독성을 높이는 문장 구조로

입맛에 맛게 수정했다.

[1] Answer Code (18. 02. 19)

#include<iostream>
#include<vector>
#include<algorithm>
#define def_swap(a,b) a ^= b ^= a ^= b
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;
  
        // #include<algorithm>
        swap(vecArr[i],vecArr[i-1]);
        
        // define Func
//        def_swap(vecArr[i],vecArr[i-1]);
        
        // Make Func
//        SwapArr(vecArr, i, i - 1);
        while (j != 1) {
            swap(vecArr[j], vecArr[j >> 1]);
//            def_swap(vecArr[j], vecArr[j >> 1]);
//            SwapArr(vecArr, j, j / 2);
            j = j / 2;
        }
    }
    
    for (int i = 1; i <= num; i++)
        cout << vecArr[i] << " ";
    
    return 0;
}

Review

  • 3가지의 방법으로 swap을 하였다.

  • define swap 방법은 동작 과정이 신기하다.

Recommend

Index