탐욕법(Greedy Method)
탐욕법이란?
탐욕법은 최적화 문제를 풀 때, 최적해의 한 조각을 선택할 때마다 각 단계마다 가장 좋아보이는 선택을 취해나가는 방법이다. 탐욕법은 보통 다음 두 가지 상황에서 사용한다.
- 특정 기준으로 가장 좋은 선택을 해나가는 것이 최적해를 보장하는 경우로 탐욕적 선택이 최적해를 가져다준다는 증명이 필요하다.
- 최적해를 찾는 방법이 너무 오래 걸릴경우 적당히 괜찮은 근사해를 찾으려고 하는 경우
연습 문제
BOJ 11047 동전 0 (문제 보기)
Ai (i >= 2)는 Aj (0<= j < i)의 배수이기 때문에 가치가 가장 큰 동전부터 최대한 많이 사용해나가면 최소의 동전으로 가치의 합 K를 만들 수 있다.
BOJ 1946 신입 사원 (문제 보기)
모든 지원자의 성적이 공개되기 때문에 각 지원자는 자신의 채용 가능 여부를 명확하게 알 수 있다. 서류 또는 면접 성적으로 정렬하면 각 지원자의 채용 가능 여부를 \(O(N)\)에 확인할 수 있다.
BOJ 2437 저울 (문제 보기)
현재 a까지 측정 가능하다고 가정하자. 여기에 무게 x인 저울이 추가된다면 x ~ a + x도 측정 가능하다. a까지 밖에 측정할 수 없다는 것은 가능한 모든 x에 대해 x > a+1이라는 것이다. 다시 말하면 가능한 x중 가장 작은 것인 x_min에 대해 x_min > a+1 이라는 말과 같다. 따라서 a=0인 순간부터 가장 작은 무게의 추 x_min을 추가해가면서 x_min > a+1 이 되는 순간을 찾으면 된다.
BOJ 1700 멀티탭 스케줄링 (문제 보기)
전기 용품 a를 사용할 차례라고 하자. 이때, 다음 순서를 따르면 된다.
- 멀티탭에 a용품이 이미 꽂혀 있으면, 그대로 사용한다.
- a가 꽂혀있는 칸은 없지만 멀티탭에 빈 칸이 있으면 전기 용품 a를 빈 칸에 꽂는다.
- 빈 칸도 없으면 가장 오랜 기간 사용되지 않을 전기 용품을 멀티탭에서 뺀 후 꽂는다.
1, 2는 직관적으로 이해할 수 있지만 3의 경우 그럴듯해보이지만 명확한 증명이 어려울 수 있다. 이 문제는 사실 운영체제에서 가상 메모리를 효율적으로 관리하기 위해 최소로 페이지를 교체하는 방법을 찾는 문제와 동일한 문제다. 최적의 페이지 교체 알고리즘(optimal page replacement algorithm, min cache replacement algorithm)에서는 미래에 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이 알고리즘의 정당성을 증명하는 것은 (읽어보지는 않았지만) 다소 복잡하다고 한다.
BOJ 1507 궁금한 민호 (문제 보기)
모든 간선이 제거된 그래프에서 두 정점 사이의 최단 거리가 가장 짧은 두 점 a, b(주어진 배열에서 가장 작은 값)부터 연결해나가면서 플로이드 와샬 알고리즘으로 모든 쌍의 최단 거리를 구해준다. 이 작업을 그래프의 모든 정점간의 최단 거리가 주어진 배열과 같아질 때까지 반복한다. 매 단계마다 최단 거리가 d로 가장 짧은 두 점 a, b를 연결하려고 할 때, 다음 세 가지 상황이 존재한다.
- 이전 단계에서 구한(플로이드로 인해) a, b 사이의 최단 거리가 d와 같다면 a, b 사이에 간선을 추가할 필요가 없다.
- 이전 단계에서 구한 a, b 사이의 최단 거리가 d보다 크다면 a, b 사이에 간선을 추가해야 한다.
- 이전 단계에서 구한 a, b 사이의 최단 거리가 d보다 작다면 모순이므로 주어진 정보가 잘못된 것이다.
BOJ 1931 회의실배정 (문제 보기)
가장 빨리 끝나는 회의부터 되는대로 선택해나가면 된다. 가장 빨리 끝나지 않는 회의부터 시작하는 최적의 배정 방법이 있다고 가정하면 이 배정 방법의 첫 시작 회의를 가장 빨리 끝나는 회의로 바꾸더라도 더 나빠지지 않으므로 가장 빨리 끝나는 회의부터 선택해나가는 것이 최적해를 가져다줌을 알 수 있다.
BOJ 1201 NMK (문제 보기)
1부터 N까지 정렬된 배열이 있다고 하자. 이 배열을 M개로 분할한 후(M-1번 자른 후), 각각 분할된 배열의 순서를 뒤집으면 된다. 주의해서 구현할 점은 각 분할된 배열은 최소 1개의 원소를 가지도록 해야 되고, 분할된 배열 중 적어도 하나는 K개의 원소를 가지도록 해야 한다. 불가능한 경우는 N이 너무 적거나 (N < M + K - 1) N이 너무 큰 경우 (N > M \(\times\) K)이다.
BOJ 2212 센서 (문제 보기)
참고 자료
- 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만
- Competive Programming 3, Steven Halim