Greedy
그리디 알고리즘에 대한 개념과 문제 풀이
1. 개념
그리디 알고리즘은 문제 해결 과정에서 결정 순간마다 눈앞에 보이는 최선의 선택을 하며 선택은 번복하지 않는다. 이런 특성으로 ‘그리디 알고리즘은 지역 최적해를 추구한다’고 말하디고 한다.
하지만 그리디 알고리즘은 특정한 상황에서 최적해를 보장하므로 이를 활용하면 문제를 잘 해결할 수 있다. 특정한 상황이란 다음 2가지를 말한다.
- 최적 부분 구조(optiomal substructure) : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
- 그리디 선택 속성(greedy selection property) : 선택 과정이 다른 과정에 영향을 주지 않음
1.1. 최소 신장 트리
신장 트리(spanning tree)는 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프를 말한다. 신장 트리 중 간선의 가중치 합이 최소면 최소 신장 트리(MST, minimum spanning tree)라고 한다.
최소 신장 트리를 구하는 대표적인 그리디 알고리즘은 프림 알고리즘과 크루스칼 알고리즘이다.
1.1.1. 프림 알고리즘 (prim’s algorithm)
프림 알고리즘을 통해 최소 신장 트리를 구하는 과정을 살펴보자.
- 임의의 정점 하나를 선택해서 최소 신장 트리에 추가한다.
- 최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가한다(그리디). 단, 순환을 형성하지 않는 정점을 추가해야 한다.
- 과정 2를 신장 트리 조건에 만족할 때까지 반복한다.
1.1.2. 크루스칼 알고리즘(kruskal algorithm)
크루스칼 알고리즘은 다음과 같다.
- 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
- 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가한다(그리디). 단, 순환을 형성하지 않아야 한다.
- 과정 2를 신장 트리 조건에 만족할 때까지 반복한다.
1.1.3. 프림 알고리즘과 크루스칼 알고리즘의 비교
| 프림 | 크루스칼 | |
|---|---|---|
| 알고리즘 목적 | 최소 신장 트리 | 최소 신장 트리 |
| 시간 복잡도 (정점 V, 간선 E) | O(E * logV) (인접 행렬 활용 시 O(N^2)) | O(E * logE) |
| 탐색 방법 | 임의 정점에서 최소 인접 가중치를 가지는 정점을 찾아 확장하는 방식 | 최소 가중치를 가지는 간선부터 하나씩 추가하는 방식 |
1.2. 배낭 문제
배낭에 담을 수 있는 최대 무게가 존재하고, 무게와 가치가 다른 짐들이 있다. 이 짐들을 잘 조합해서 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제를 배낭 문제라고 한다.
배낭 문제의 목표는 모두 ‘최대한 배낭에 높은 가치에 짐을 넣는다’ 이지만 짐을 쪼갤 수 있는지 없는지에 따라 부분 배낭 문제와 0/1 배낭 문제로 나뉜다.
1.2.1. 짐을 쪼갤 수 있는 배낭 문제
부분 배낭 문제를 해결하려면 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘을 사용하면 된다.
- 짐별로 무게당 가치를 구한다
- 무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣는다.
- 배낭 용량이 짐 무게보다 크면 짐을 쪼개서 넣는다.
- 과정 2를 배낭이 허용하는 용량이 0이 될 때까지 수행한다.
매 순간 짐을 선택하는 방식은 무게당 가치가 높은 짐이므로 최적 부분 구조를 만족한다. 그리고 짐을 쪼갤 수 있으니 앞에서 선택한 짐이 다른 짐 선택에 영향을 주지도 않으므로 그리디적 선택 요소에도 만족한다. 따라서 이 방식은 최적해를 보장한다고 할 수 있다.
1.2.2. 짐을 쪼갤 수 없는 0/1 배낭 문제
이제 0/1 배낭 문제이다. 이 문제는 짐을 쪼갤 수 없어서 지금 선택한 짐이 다음 짐 선택에 영향을 준다. 그래서 그리디 알고리즘을 적용하면 최적의 해를 구할 수 없다. 최적의 해를 구하려면 동적 계획법으로 접근해야 한다.
2. (문제) 예산
2.1. 설명
S사에서는 각 부서에 필요한 물품을 지원해주기 위해 부서별로 물품을 구매하는 데 필요한 금액을 조사했습니다. 다만 전체 예산이 정해져 있기 때문에 모든 부서가 필요로 하는 물품을 구매할 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매하려고 합니다. 물품을 구매할 때는 각 부서가 신청한 금액만큼은 모두 지원해야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며 1,000원보다 적은 금액을 지원할 수는 없습니다. 부서별로 신청한 금액이 들어 있는 배열 d와 예산 budget이 주어질 때 최대 몇 개의 부서에 물품을 지원할 수 있는지 반환하는 solution() 함수를 완성하세요.
2.2. 제약 조건
- d는 부서별로 신청한 금액이 들어 있는 배열이며, 길이(전체 부서 개수)는 1 이상 100 이하입니다.
- d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별로 신청 금액은 1 이상 100,000 이하의 자연수입니다.
- budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.
2.3. 입출력의 예
| d | budget | result |
|---|---|---|
| [1,3,2,5,4] | 9 | 3 |
| [2,2,3,3] | 10 | 4 |
2.4. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fun solution(d: IntArray, budget: Int): Int {
var result = 0
var current = budget
val sorted = d.toList().sorted()
for (i in sorted) {
if (current - i < 0) {
return result
} else {
result++
current -= i
}
}
return result
}
println(solution(intArrayOf(1, 3, 2, 5, 4), 9))