오늘 설명할 문제는 백준 2109번 순회 강연이다.
https://www.acmicpc.net/problem/2109
2109번: 순회강연
문제 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한
www.acmicpc.net
전형적인 그리디 알고리즘 문제로, 이 알고리즘에 대한 이해가 있다면 어렵지 않게 풀 수 있는 문제이다.
그리디 알고리즘은 문제를 해결하는 과정에서 그 순간 순간마다 최선이라고 생각하는 방향으로 결정하는 방식의 알고리즘이다. (削除) 마치 우리의 인생처럼. (削除ここまで) 그러다 보니 문제 전체를 해결했을 때 가장 최선의 선택을 하지 않을 가능성도 존재한다.
예를 들면 이런 경우다. 그리디 알고리즘으로 매 순간 순간 최선의 선택을 하면 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)이 시간복잡도로 계산된다.
아래는 내가 제출한 자바 소스 코드이다.
그리디 알고리즘 연습하기 좋은 너무 까다롭지 않은 문제이다. 추천!
'Computer Sci. > Algorithms' 카테고리의 다른 글
| 백준 1300 / 이분 탐색 (Binary Search) / JAVA (0) | 2020年05月07日 |
|---|---|
| 백준 10422 / 동적 계획법 (Dynamic Programming) / JAVA (0) | 2020年05月05日 |
| 백준 16946 / BFS, 플러드 필 알고리즘(Flood Fill) / JAVA (1) | 2020年04月21日 |
| 백준 1865 / 벨만 포드 알고리즘(Bellman Ford) / JAVA (1) | 2020年04月14日 |
| 백준 1655 / 최대힙(MaxHeap), 최소힙(MinHeap) / JAVA (0) | 2020年04月09日 |