문제
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.
매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.
N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.
출력
첫째 줄에 최소 비교 횟수를 출력한다.
예제 입력 1
3
10
20
40예제 출력 1
1001. 문제 접근 과정(DP -> 우선 순위 큐)
처음 이 문제를 봤을 때는 카드 묶음의 일부의 최소 비교 횟수를 알고, 다른 카드 묶음의 개수를 알면 전체의 최소 비교 횟수를 알 수 있다고, 즉 Dynamic programming 방식으로 풀 수 있다고 가정하고, 우선 문제에 나온 카드 묶음이 3개 있을 때의 최소 카드 비교 횟수를 어떻게 알 수 있는 지를 파악해 보았습니다.
우선, 카드 묶음이 2개 있으면 최소 비교 횟수는 무조건 두 카드 묶음의 개수를 합한 것입니다(∵ 양쪽 카드 묶음을 한 장씩 비교하며 정렬). 그러나 카드 묶음이 3개면 경우의 수가 생기는데, 카드 수가 예시처럼 10, 20, 40인 카드 묶음 3개를 최소 비교 횟수로 정렬한다고 할 때,
- (10 + 20)을 먼저 비교하고, (정렬된 30 + 40)을 비교하는 경우
- (10 + 40)을 먼저 비교하고, (정렬된 50 + 20)을 비교하는 경우
- (20 + 40)을 먼저 비교하고, (정렬된 60 + 10)을 비교하는 경우
이렇게 3가지 경우의 수가 생깁니다. 이 때 최소 비교 횟수는 1번(10+20 + 30+40 = 100)인데, 왜 1번이 최소 비교 횟수인 지를 생각해보면, 3개의 카드 묶음을 비교할 때, 먼저 비교하는 한 쌍의 비교 횟수, 즉 두 카드 묶음의 카드 장수의 합은 새로운 카드 묶음을 만들어 냅니다. 이는 남은 한 카드 묶음과 또 다시 비교를 해야 하는데, 이때 (남은 한 카드 묶음의 장수 + 아까 정렬한 카드 장수)의 값이 비교 횟수입니다. 즉, 먼저 비교한 카드 묶음들의 카드 수의 합( = 비교 횟수)은 남은 카드 묶음의 장수와 한 번 더 더해지게 됩니다.
이 이유 때문에 합이 가장 적은, 즉 가장 적은 수의 카드 묶음과 두 번째로 적은 수의 카드 묶음을 먼저 더해야 최소 비교 횟수를 구할 수 있습니다. 이를 생각해보면 (n-1)개의 카드 묶음들의 정렬을 위한 최소 비교 횟수를 안다면, n개의 카드 묶음들의 최소 비교 횟수를 알 수 있다는 DP적인 문제해결이 어렵다는 것을 알 수 있습니다.
만약 카드 묶음이 10, 11, 12, 13이라면 먼저 10장짜리와 11장짜리를 비교하여 21장짜리 카드 묶음을 만들고, 12장짜리와 13장짜리를 정렬해 25장짜리 카드 묶음을 만들어야 최소 비교 횟수가 나오는데, DP식으로 문제를 해결하면 n-1개의 카드 묶음을 정렬하고자 할 때 최소 비교 횟수를 알아도, 1개를 추가한 후의 최소 비교 횟수는 결국 기존의 카드 묶음들 중 1,2 번째로 적은 카드 수의 묶음을 알아야 하기 때문에 DP로 이전의 해답을 알고 있는 것이 의미가 없게 됩니다.
따라서 이 문제의 해결 알고리즘은 다음과 같습니다.
- 현재 카드 묶음들에서 가장 장수가 적은 묶음 2개를 뽑아 정렬합니다(둘의 장수를 더함).
- 1에서 정렬한 횟수를 총 비교 횟수에 저장합니다.
- 정렬이 끝난 묶음을 다시 카드 묶음들에 넣고, 카드 묶음이 하나가 될 때까지 1번으로 돌아갑니다.
이 알고리즘을 가장 간단하게 해결하는 방식은 우선순위 큐를 사용하면 됩니다.
우선순위 큐란?
일반적인 큐는 FIFO(First In First Out)에 따라 가장 먼저 넣은 데이터가 가장 처음 나오게 됩니다. 그러나 우선순위 큐는 넣은 순서에 상관없이 우선순위(직접 지정가능)에 따라 우선순위가 높은 데이터가 먼저 나오게 되는 자료구조입니다. 우리는 넣은 순서에 상관없이 정렬이 진행 중일 때도 가장 카드 장수가 적은 묶음 2개를 알고 싶기 때문에 이 자료구조를 사용하는 것이 적합합니다.
우선순위 큐의 구현 - Heap
우선순위 큐를 구현하기 위해서는 Heap을 사용하면 됩니다. Heap이란, 부모 노드와 자식 노드가 통일된 하나의 관계(예: 대소 관계)를 가지는 완전 이진 트리(한 쪽으로 쏠린, 즉 skewed되지 않고 노드가 같은 높이 상에서 왼쪽->오른쪽으로 추가되는 트리)입니다. 부모와 자식간의 관계만 따지기 때문에, 모든 부모 노드의 값이 자식 노드보다 값은 min heap을 예로 들면, 같은 부모와 연결된 자식이더라도 대소 관계는 상관하지 않습니다.
heap은 push는 가장 아래 층의 노드 중 가장 오른쪽에 추가되고(요소가 아무리 추가되도 완전 이진 트리를 만족), pop은 root 노드에서 값이 빠집니다. push, pop 둘 다 요소를 추가, 삭제한 후에 부모 / 자식간의 관계를 유지하기 위해, push는 추가한 요소, 즉 가장 아래에서부터, pop은 가장 위에서부터 부모 / 자식 요소과 값을 비교하며 관계가 유지될 때까지 값을 swap합니다.
먼저 기존 min-heap에 2라는 값을 push하는 예시를 그림으로 보시겠습니다. 트리의 가장 마지막 위치에 우선 값을 추가 후, 부모 노드와 비교하며 대소 관계가 맞을 때까지 값을 swap해가며 반복합니다. 2가 root 노드에 간 후부터는 더이상 비교할 부모가 없기 때문에 연산이 종료되었습니다.
다음은 pop과정입니다. 가장 작은 3이 빠지고, 가장 마지막 위치의 노드의 값을 root로 옮긴 후에 자식들과 비교합니다. 이때, 자식이 한쪽(완전 이진트리이므로 무조건 왼쪽)만 있으면 그 자식과 값을 비교하면 되지만, 자식이 둘 다 있으면 둘 중에 작은 값과 비교하여 swap연산을 수행 후, 비교를 이어가야 합니다.
왜냐하면, 2번째 그림에서 11과 자식 4, 6을 비교할 때, 어쨌든 11이 6보다 작으니 4보다 큰 6과 11을 swap하게 되면, 6이 4의 부모 노드로 가기 때문에 min-heap에 맞지 않습니다.
따라서, heap의 우선순위가 높은 자식 노드와 부모를 비교해 swap을 할지 연산을 중단할 지를 결정해야 합니다.
위 과정들은 최대 logn번의 swap이 무조건 일어날 수밖에 없습니다. 이때 logn이 커지거나 노드 속의 값이 큰 용량을 차지한다면 시간적으로나 메모리적으로 overhead가 있을 수 있는데, 아래 방식으로 한 번의 swap없이 비교 연산, 대입 연산만으로 push(pop도 같은 방식으로 가능)를 수행할 수 있습니다.
push할 때 부모 노드를 타고 올라가며 계속 비교하는 대상은 결국 새로 추가한 값이기 때문에, 이를 별도의 변수에 저장 후, 부모 노드와 비교해주며 swap할 필요가 생긴다면 단지 부모 노드의 값을 자식으로 복사해주고, 새 노드가 추가될 자리를 얻는다면 그 자리에 값을 복사해주면 됩니다.
우선순위 큐는, 이러한 heap 자료구조를 바탕으로, 원하는 우선순위를 설정해 heap에 반영하여, 우선순위가 높은 값이 먼저 나갈 수 있도록 설계할 수 있습니다.
우선순위 큐 구현 & 코드
C++에 우선순위 큐 라이브러리가 있지만, 혹시나 코테에서 사용법이 떠오르지 않을 때를 대비할 겸, 자료구조를 공부할 겸 직접 매우 간단한 코드로 구현해보았습니다.
class PriorityQueue {
private:
int arr[100001];
int idx;
public:
PriorityQueue() {
idx = 1; // place to insert data
}
int length() {
return idx-1;
}
void insert (int n) {
int id;
id = idx++;
while (id/2 > 0 && arr[id/2] > n) {
arr[id] = arr[id/2];
id /= 2;
}
arr[id] = n;
}
int dele() {
int ret = arr[1];
int num, min, id;
num = arr[--idx];
id = 1;
while (id*2 < idx) {
if (id*2+1 == idx) {
if (arr[id*2] >= num)
break;
id *= 2;
arr[id/2] = arr[id];
break;
}
id = (arr[id*2] < arr[id*2+1]) ? id*2 : id*2+1;
min = arr[id];
if (min >= num) {
id /= 2;
break;
}
arr[id/2] = min;
}
arr[id] = num;
return ret;
}
};
우선 PriorityQueue class의 멤버 변수는 min-heap을 위한 완전 이진 트리 arr, 현재 내가 노드를 삽입할 위치(길이 - 1)를 나타낸 idx로 구성됩니다. insert(push)와, dele(pop) 둘 다 각 연산을 시작하는 지점을 id로 하고, 이를 id /= 2 or id *= 2하며 위치를 부모, 자식 방향으로 이동합니다. 그 과정에서 비교할 부모/자식이 없거나 부모/자식간의 우선순위가 지켜졌다면 연산을 중단합니다.
다음은 전체 코드입니다.
- 해당 우선순위 큐를 사용해, 입력 받은 카드 묶음을 큐에 모두 넣어줍니다.
- 가장 장수가 적은 카드 묶음 2개를 뽑고, 이를 더해(비교하여 정렬) 생긴 정렬된 카드 묶음은 다시 큐에 넣어주고,
- 방금 더한 횟수, 즉 소요된 비교 연산의 횟수를 sum에 누적한 뒤, 모두 정렬이 되면 sum을 답으로써 출력합니다.
#include <bits/stdc++.h>
using namespace std;
class PriorityQueue {
private:
int arr[100001];
int idx;
public:
PriorityQueue() {
idx = 1; // place to insert data
}
int length() {
return idx-1;
}
void insert (int n) {
int id;
id = idx++;
while (id/2 > 0 && arr[id/2] > n) {
arr[id] = arr[id/2];
id /= 2;
}
arr[id] = n;
}
int dele() {
int ret = arr[1];
int num, min, id;
num = arr[--idx];
id = 1;
while (id*2 < idx) {
if (id*2+1 == idx) {
if (arr[id*2] >= num)
break;
id *= 2;
arr[id/2] = arr[id];
break;
}
id = (arr[id*2] < arr[id*2+1]) ? id*2 : id*2+1;
min = arr[id];
if (min >= num) {
id /= 2;
break;
}
arr[id/2] = min;
}
arr[id] = num;
return ret;
}
};
int main() {
PriorityQueue q;
int num, len, sum;
int n1, n2;
cin >> len;
for (int i = 0; i < len; i++) {
cin >> num;
q.insert(num);
}
if (q.length() == 1) {
cout << 0;
return 0;
}
sum = 0;
while (q.length() != 1) {
n1 = q.dele();
n2 = q.dele();
sum += n1 + n2;
q.insert(n1 + n2);
}
cout << sum << "\n";
return 0;
}'baekjoon(solved)' 카테고리의 다른 글
| [BOJ 12865] 평범한 배낭 - Dynamic Programming (3) | 2024.09.30 |
|---|---|
| [BOJ 9251] LCS - Dynamic Programming (1) | 2024.09.23 |