백준 2109 / 그리디(Greedy) 알고리즘 / JAVA

 

오늘 설명할 문제는 백준 2109번 순회 강연이다.

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

2109번: 순회강연

전형적인 그리디 알고리즘 문제로, 이 알고리즘에 대한 이해가 있다면 어렵지 않게 풀 수 있는 문제이다.

그리디 알고리즘은 문제를 해결하는 과정에서 그 순간 순간마다 최선이라고 생각하는 방향으로 결정하는 방식의 알고리즘이다. 마치 우리의 인생처럼. 그러다 보니 문제 전체를 해결했을 때 가장 최선의 선택을 하지 않을 가능성도 존재한다.

예를 들면 이런 경우다. 그리디 알고리즘으로 매 순간 순간 최선의 선택을 하면 3 -> 10 -> 20 으로 선택을 하지만, 실제 가장 큰 숫자는 50인 것처럼 말이다. 이처럼 그리디 알고리즘으로 전체 문제의 최적의 답을 찾지 못하는 경우도 발생한다.

그럼에도 불구하고 왜 우리는 그리디 알고리즘을 사용하는 걸까? 그 이유는 그리디 알고리즘이 빠르기 때문이다! 동적 프로그래밍(Dynamic Programming) 방식 보다 훨씬 빠른 장점을 가지고 있다. 실제로 동적 프로그래밍과 그리디 알고리즘은 서로 보완하는 역할을 한다 (하나는 정확도, 하나는 속도)

그러면 이 문제에서 그리디 알고리즘이 어떻게 쓰이는지 한 번 보도록 하자.

문제에서 한 학자가 여러 개(0<=n<=10,000)의 강연을 받았다. 각 강연은 강연료와 날짜 제한이 있다. 하루에 하나씩만 할 수 있으며, 당연히 같은 날에 두 강연이 있다면 더 비싼 강연료를 주는 강연을 하는 것이 이득이다. 이렇게 해서 전체 제안을 통해 가장 높은 강연료를 얼마 받을 수 있는지 구하는 문제이다.

우선 Lecture 라는 클래스를 먼저 만들고, 여기에 pay와 day라는 프로퍼티를 넣는다. 그리고 하나의 강의를 Lecture 객체로 만들어서 큐에 넣으면 좋을 것 같다는 생각을 했다. 

이제 적절한 날짜에 적절한 강의를 배정해야 한다. 그래서 나는 이 문제에서 우선순위 큐를 사용했다. 자바에는 PriortyQueue 클래스가 있는데, 클래스의 프로퍼티에 따라 우선순위를 매겨서 정렬해 주는 큐이다. 우선순위 큐에서 첫 번째 기준은 강연료가 높은 순서로 우선순위를 두었고, 두 번째 기준으로는 같은 강연료일 경우 날짜 제한이 빠른 강연을 우선순위에 두었다. 그런 기준을 가지고 정렬을 하면 오른쪽과 같이 정렬이 된다.

이 상태에서 강연 스케줄을 잡는다. 시작 하기 전에 가장 날짜 제한이 긴 강연값을 통해 전체 강연 날짜 체크 boolean 배열을 만든다. 그래서 특정 날짜에 강연이 배정되면 해당 배열의 값을 true로 바꾸어 준다.

이제 PriortyQueue에서 하나씩 꺼내준다. 먼저 첫 번째 강연이다. 강연료는 100이고 날짜 제한은 2일까지이다. 그러면 2일째부터 역순으로(2일 -> 1일) checked 배열을 체크한다. 2일에 아직 강연이 없으므로 2일에 이 강연을 넣고, checked[2] = true 로 바꾸어 준다. 현재까지 강연료 합계는 100이다.

두 번째 강연을 꺼내본다. 두 번째 강연은 강연료 50에 날짜 제한이 10일이다. 마찬가지로 10일부터 역순으로 체크를 하면서 비어있는 날짜에 바로 강연을 넣는다. 10일이 비어있으므로 여기에 두 번째 강연을 넣고 checked[10] = true로 바꾸어 준다. 현재까지 강연료 합은 150이다.

세 번째 강연을 꺼내본다. 세 번째 강연은 강연료 20에 날짜 제한이 1일이다.1일이 비어있으므로 여기에 두 번째 강연을 넣고 checked[1] = true로 바꾸어 준다. 현재까지 강연료 합은 170이다.

이런식으로 모든 PriorityQueue 안의 Lecture에 대해서 반복문을 돌린다. 만약 어떤 강연을 꺼냈는데, 날짜 제한을 역순으로 체크해 보아도 비어있는 날짜가 없다면, 그 강연은 받을 수 없게 된다. 문제에서 주어진 테스트 케이스에 대해서 loop를 수행한 결과는 아래와 같다.

이 문제의 시간 복잡도는 PriortyQueue를 전체 loop 하는데 N이 소요되고, 각각의 원소에서 checked 배열을 역순으로 loop 하므로 N이 소요된다. 즉 O(N^2)이 시간복잡도로 계산된다.

아래는 내가 제출한 자바 소스 코드이다.

그리디 알고리즘 연습하기 좋은 너무 까다롭지 않은 문제이다. 추천!