우선순위 큐를 이용한 그리디 문제

그리디 문제를 풀다보면, 우선순위 큐가 필요할 때가 종종 등장한다.

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

이런 문제들이 우선순위 큐를 가지고 풀어야 하는 문제다.

물론 다른 방식으로 풀 수 있지만, 시간초과가 발생하는 경우가 많다.

 

이 문제들은 왜 우선순위 큐가 필요할까? 또 우선순위 큐를 어떻게 이용할까?

 

첫 번째, '카드 정렬하기(1715)'문제를 보자.

카드 정렬하기 문제의 핵심은 '고르는 순서'다.

문제의 설명에 나온 대로 10장, 20장, 40장의 카드 묶음이 있을 때, (10+20)을 묶고, 이 30장짜리 카드묶음을 (30+40)으로 또 묶어버리면 100번의 비교가 필요하지만, (10+40)을 묶고, 50장짜리 카드묶음을 (50+20)으로 묶어버리면 120번의 비교가 필요하다. 

결국 첫 번째 방법은 10 + 20 + 30(10+20) + 40 = 100이고

두 번째 방법은 10 + 40 + 50(10 + 40) + 20 = 120으로 해석할 수 있다.

따라서 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치는 것을 알 수 있다.

묶음의 개수는 정해져 있으므로, 카드의 개수가 작은 순서대로 먼저 합쳐야 한다는 것을 알 수 있다.

그래서 작은 묶음의 데이터 2개를 뽑아서 계속 비교해나가므로 삽입, 삭제, 정렬이 자주 일어난다는것을 알 수 있다.

 

두 번째 문제로, '강의실 배정(11000)' 문제를 보자.

강의실 배정하기의 문제의 핵심은 '수업을 최대한 겹치지 않게' 배정하는 것이다.

수업 시작시간을 기준으로, 가장 빨리 끝나는 시간을 비교해서 같은 강의실 안에 최적으로 배치해서 최소한의 강의실을 이용해야 한다.

따라서 (1,3), (2,4), (3,5)의 수업이 주어졌을 때, 가장 일찍 시작하는 수업을 먼저 배치하고, 그 다음 수업들을 비교해서 다른 수업의 시작시간이 처음 고른 수업의 종료시각보다 느리면 우선순위큐에 넣는다.

위의 예제를 이용해 말로 풀어서 설명하면, 1시부터 3시까지 진행하는 수업을 강의실에 배치하고, 2시부터 4시까지 진행하는 수업은 아직 강의실이 비지 않았으니 새로운 강의실에 배치한다(pQueue.offer). 3시부터 5시까지 진행하는 수업은 우선순위큐의 top을 봤을 때(pQueue.peek) 3시에 끝나는 수업이 있으므로 이 수업을 꺼내고, 3시부터 5시까지 진행하는 수업을 넣는다.

결국 마지막에 남는 우선순위 큐에는 (2,4) (3,5)가 남고, 이 큐가 결국 필요한 강의실의 개수가 되는 것이다.

우선순위 큐를 사용하지 않으려면 강의를 전체 배정하고, 시작시간을 기준으로 정렬한 뒤 강의를 매번 돌면서 겹치지 않는 수업을 지워줘야 한다. ArrayList의 조회 시간복잡도는 O(1)이지만, 삽입과 삭제의 시간복잡도는 O(N)이기 때문에 조회와 삽입/삭제를 같이 해주어야 해서 N*N의 시간복잡도가 걸리기 때문에 최대 (200,000) * (200,000)의 연산을 하게 된다.

이 또한 삽입, 삭제, 정렬이 자주 일어나는 문제임을 알 수 있다.

 

마지막으로, '보석 도둑(1202)' 문제를 보자.

보석 도둑 문제의 핵심은 '가방의 무게보다 같거나 작은 최소 무게로 최대한의 가격'을 내야 한다.

무게, 가격이 (1,65), (5,23), (2,99)인 보석과 무게가 각각 (10), (2)인 가방이 있을 때

첫번째와 두 번째 보석을 훔친다면 65+23 = 88의 가격을 낼 수도 있지만,

첫번째와 마지막 보석을 훔친다면 65+99 = 164의 가격을 낼 수 있다.

그래서 가방의 무게를 기준으로 들어갈 수 있는 보석의 list를 나열해서 가격이 최대인 보석을 넣어야 한다.

그런데 각 가방의 무게를 기준으로 들어갈 수 있는 보석을 전부 나열해서 고르고, 보석 리스트에서 제거하려면 어마어마한 시간이 소요되게 된다.

그래서 보석과 가방의 무게를 기준으로 정렬한 뒤, 보석의 리스트를 새로 갱신하지 않고 우선순위 큐에 추가해서 가격이 높은것만 빼주는 것이다.

먼저 보석을 무게순으로 정렬하면 (1,65) , (2,99), (5,23)이 될 것이다.

그 다음 가방의 무게가 2라면 첫번째 보석과 두 번째 보석을 우선순위 큐에 넣고, 그 중 가격이 가장 높은 (2,99)보석을 택한다. 그 다음 무게가 10인 가방이 있으므로 나머지 보석 리스트에서 무게가 10 이하인 보석들을 전부 우선순위 큐에 넣는다. 그러면 (1,65), (5,23)중에서 또 밸류가 높은 보석을 뽑으면 된다.

 

이 3개의 문제를 봤을 때, 공통점은 '삽입, 삭제, 조회가 빈번하느냐'이다.

그런데 '삽입, 삭제, 조회가 빈번하느냐'에 무조건 우선순위 큐를 쓰냐고 하면 그런건 또 아니다.

에초에 삽입/삭제/조회시간을 줄이기 위해서 알고리즘을 풀기 때문에...

그렇다고 문제 유형을 일일히 외워두고 '이런 유형은 무조건 우선순위 큐를 써야지'라고 생각하면 또 안된다.

두 번째 문제와 비슷한 '회의실 배정(1931)' 문제를 보자.

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

정말 비슷하게 생긴 문제지만, 이 문제는 우선순위 큐가 사용되지 않는다.

회의실을 1개만 사용하기 때문에, 겹치지 않는 회의를 최대한 밀어넣으면 끝이기 때문이다.

 

그럼, 언제 우선순위 큐를 사용해야 하는 것일까?

1번, 2번, 3번 문제를 보면, 공통적으로 나타나는 특징이 하나 있다.

남아있는 리스트를 계속 사용하면서, 어떤 시점에서 재조회를 하지 않고 최대/최소를 찾아야 한다.

카드 정렬하기 문제를 보면, 카드 뭉치를 하나씩 사용하면서 다시 그 뭉치를 이용한 최솟값 조회를 해야 한다.

강의실 배정 문제를 보면, 가장 빨리 끝나는 강의실을 갱신하면서 다른 강의의 시작시간을 조회해야 한다.

보석 도둑 문제를 보면, 주어진 무게 이하의 무게에서 가치의 최댓값을 조회해야 한다.

 

따라서, 조회가 빈번하게 일어나는 상황 속에서, 기존의 데이터를 포함해서 계속 갱신을 해나가며 최댓값/최솟값을 찾을 때 우선순위 큐를 이용해야 한다는 결론에 도달한다.

 

기존 데이터의 마지막 값만을 참조하는 스택을 이용하는 문제와는 다르다.

개인적으로는, '이런 문제는 우선순위 큐다 / 스택이다' 보다는, 계속 문제를 풀어보면서 스택을 이용하는지, 또 우선순위큐를 이용하는지 감을 익히는것이 제일 중요하다고 생각한다.