[방학의 PS] 그리디 알고리즘 - BOJ_1931, BOJ_1541

그리디 알고리즘의 정의

그리디 알고리즘이란 어떤 문제를 해결해야 할 때, 그 문제를 반복되는 여러 단계로 나눈 뒤에, 각 단계의 문제에 대한 최적해를 구하는 것을 반복하는 알고리즘입니다.

 

그리디 알고리즘의 예

간단한 예를 통해 말씀드리면, 거스름돈 구하기 문제를 셍각해 볼 수 있습니다. 만일 여러분이 편의점 알바생이고, 손님에게 X원의 현금을 거슬러주어야 할 때, 누구나 자연스럽게 가장 큰 단위의 화폐부터 거슬러주게 됩니다. 예를 들어 6670원을 거슬러준다면, 5000원짜리 한 장, 1000원 짜리 한 장, 500원 한 개, 100원 한 개, 50원 한 개, 10원 2개 순서로 거슬러 드릴 것입니다. 즉 X원을 거슬러 드리는 문제를 5000원을 거슬러 드리는 문제, 1000원을 거슬러 드리는 문제... 등 최댓값 문제로 바꾸어 각 단계에 대한 최적해를 구한 것이죠.

 

그리디 알고리즘의 단점

그러나 이러한 그리디 알고리즘에는 치명적인 단점이 존재합니다. 바로 각 단계의 최적해를 구한다고 해서 전체 문제의 최적해가 보장되는 것은 아니라는 것입니다. 예를 들어, 여러분이 서울에서 부산까지 갈 때, 여러분은 대구를 거쳐 자동차로 가는 경로와 인천을 거쳐 배를 타고 가는 경로, 두 가지 사이에서 선택해야 한다고 합시다. 만약 거리를 바탕으로 최적화 문제를 생각할 경우, 당연히 당장에야 인천까지 가는 경로가 대구까지 가는 경로에 비해 훨씬 더 가까울 것입니다. 우리의 목적지인 부산을 생각해 본다면 당장의 거리만 보고 인천으로 출발하는 것은 어불성설입니다. 그러나 그리디 알고리즘을 적용한다면 여러분은 묻지도 따지지도 않고 인천을 향해야 합니다.

 

 

그리디 알고리즘 문제의 정수

그렇기 때문에 어떤 문제를 그리디 알고리즘으로 풀어야 한다는 것은 세심한 주의를 요합니다. 첫째로, 각 단계별 최적해를 따라 가는 것이 곧 전체 문제의 최적해를 도출한다는 보장이 있어야 하죠. 위의 부산행 문제를 살펴보면, 서울-대구-부산, 또는 서울-인천-부산의 교통편을 선택하는 것이 서울-부산의 직항 교통편보다 확실히 우월한지 잘 살펴봐야 하죠.

둘째로, 만일 쪼개서 최적해를 구한다면 어떠한 기준으로 최적해를 판단할 것인가를 분석해야 합니다. 다시 위의 예를 통해 설명하면, 과연 거리를 기준으로 최적화할 것인지, 시간을 기준으로 최적화할 것인지, 아니면 교통비를 중심으로 최적화할 것인지를 고려해야 할 것입니다. 저는 이 두 가지가 그리디 알고리즘의 정수라고 봅니다.

 

그리디 알고리즘 문제 풀이

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

회의실 문제(1931번)를 생각해 봅시다. 그리디 알고리즘에 대해서 공부하고 나니 이 문제는 아주 훌륭한 그리디 알고리즘 문제로 보입니다. 우선 이 문제가 그리디 알고리즘 문제인가를 파악하는 것이 쉽지 않습니다. 그리고 만약 어떤 사람이 회의실을 쓰고 난 뒤 그 다음 누가 회의실을 써야 하는가를 고민했을 때, 남아 있는 이용자들 중 가장 빨리 회의실을 비워줄 수 있는 사람이 와야 한다는 것을 파악해야 합니다. 저의 경우, 이것을 알아차리는 것도 쉽지 않았습니다. 이것이 문제의 핵심이었죠.

 

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

잃어버린 괄호 문제(1541번)에 대해서 이야기해보자면, 역시 '-'로 둘러쳐진 부분부터 계산하자는 것이 핵심이었습니다. 즉, '-' 부분부터 계산하는 것을 반복하면 결국 최적해에 도달할 수 있다는 것입니다.

 

(제 코드는 상당히 모범적이지 못한 방식으로 구현했기 때문에 생략하겠습니다. 양해 부탁드립니다.)