오늘은 그리디 알고리즘에 대해서 알아보겠습니다.
그리디 알고리즘
그리디 알고리즘, 욕심쟁이 알고리즘이라고 불리는 이 방식은 문제를 해결하기 위핸 문제해결 패러다임 중 하나입니다.
매순간마다 직면한 상황에서 가장 좋은 선택지를 선택하는 알고리즘이죠.
그리디 알고리즘에 속하는 많은 알고리즘이 있습니다.
- 동전 거스름돈 문제
- 최소 신장 트리(MST) 구하기
- 최단 경로 찾기
- 부분 배낭 문제
- 집합 커버 문제
- 작업 스케쥴링
- 허프만 압축
오늘은 이 중에서 집합 커버 문제까지 다뤄보겠습니다.
동전 거스름돈 문제
음료수 자판기가 있다고 해봅시다. 각 자판기는 현금을 받고 음료수를 줍니다. 거스름돈이 있다면 거스름돈을 어떻게 줄지에 대해서 결정해야합니다.
이 때, 그리디 알고리즘이 쓰입니다.
대한민국 기준으로 동전은 500원, 100원, 50원 10원이 있습니다.
우리가 1100원짜리 음료수를 사기 위해 2000원을 넣었다면 500원 1개, 100원 4개를 반환할 것입니다.
간단한 문제이므로 코드를 바로 소개하겠습니다.
class CoinChange{
int[] changeList = new int[]{500, 100, 50, 10};
public List<Integer> coinChange(int change){
List<Integer> numList = new ArrayList<>();
for (int i : changeList) {
int num = change/i; // 반환할 동전 개수
change -= num*i; // 아직 처리 안된 거스름돈
numList.add(num);
}
return numList;
}
}이러한 식으로 구현할 수 있습니다.
거스름돈 문제를 해결하기 위해 그리디 알고리즘을 사용한다면 모두 해결될까요??
만약 화폐 정책이 바뀌어 160원 동전이 생겼다고 해봅시다. 우리가 1800원짜리 음료수를 사기 위해 2000원을 넣습니다.
그럼 우리가 원하는 것은 100원짜리 2개를 받기 원할 것입니다.
하지만 그리디 알고리즘으로 구현된 이 자판기는 160원 1개와 10원 4개를 돌려주게 됩니다. 그리디 알고리즘은 직면한 상황에서 최적의 값을 찾기 떄문에 발생하는 문제입니다.
즉, 그리디 알고리즘은 동전 거스름돈 문제에서 항상 최적해를 보장하지 않습니다.
최소 신장 트리 구하기
한 그래프 내에서 최소 신장 트리를 찾기 위해 우리는 Kruskal, Prim, Sollin 알고리즘을 사용합니다. 이 중에서, Kruskal과 Prim 알고리즘은 그리디 알고리즘을 이용합니다.
이전 글에서 자세하게 다루었으므로 생략합니다.
최단 경로 찾기
한 그래프내에서 특정 정점에서 다른 정점으로 가기 위한 최단 거리를 구할 때, 우리는 Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘을 사용했습니다. 그 중, Dijkstra가 그리디 알고리즘에 속합니다.
이 또한 이전 글에서 자세히 다루었으므로 생략합니다.
부분 배낭 문제
배낭 문제는 n개의 물건이 1개씩 있고 해당 물건의 무게와 가치가 있습니다. 그리고 가방에 일정 무게까지 담을 수 있습니다. 그 때, 가장 높은 가치를 갖게되는 경우를 찾는 문제입니다.
부분 배낭 문제는 그 중에서 물건의 일부분만을 담을 수 있도록 허용하는 문제입니다.
우리는 그리디 알고리즘을 이용해서 이 문제를 풀 수 있습니다.
- 단위무게당 가치를 계산합니다.
- 단위무게당 가치가 가장 높은 물건부터 차례대로 넣습니다.
- 최대한 넣고 난 후, 배낭에 공간이 남았다면 부분적으로 다음 가치의 물건을 담아서 가방을 꽉 채웁니다.
아래와 같은 경우를 생각해봅시다.
가장 먼저 우리는 단위무게당 가치를 정해야합니다.
1g당 가치는 아래와 같습니다.
백금 : 6만원
금 : 5만원
은 : 4천원
주석 : 1천원
따라서 우리는 1g당 가치가 가장 높은 백금부터 가방에 담습니다. 백금 전체 10g을 가방에 모두 담을 수 있으므로, 가방에 백금부터 담습니다.
자, 이제 다음으로 가치가 높은 금을 담습니다. 금 15g을 모두 담을 수 있으니 담겠습니다.
이제 가방에 남은 공간은 15g입니다. 다음 가치가 높은 은을 봤는데 25g이 있으므로 부분적으로 담아야할 것을 인지했습니다.
그럼 이제 은 15g이 얼마의 가치를 갖는지 계산하고 15g만큼을 가방에 담습니다.
은 15g은 6만원이 될 것입니다.
이제 가방이 꽉차서 더 이상 넣을 수 없으므로 종료합니다.
가방에 담긴 물건의 총 가치는 141만원이 되고 이것이 최적해가 됩니다.
코드로 확인해보겠습니다.
public static class FractionalKnapsack{
static boolean[] visited = new boolean[weight.length];
public static double calculateValue() {
double[] unitValue = calculateUnitValue();
System.out.println(Arrays.toString(unitValue));
int x = findMaxUnitValueIdx(unitValue);
L = new ArrayList<>();
int w = 0;
double v = 0.0;
while((w + weight[x])<= capacity){ // 통째로 담을 수 있는만큼은 담기
L.add(new int[]{x, weight[x]});
w += weight[x];
v += value[x];
visited[x] = true;
x = findMaxUnitValueIdx(unitValue);
}
if((capacity - w)>0){ // 공간이 남으면 부분적으로 담기
L.add(new int[]{x, capacity-w});
v += (capacity-w)*unitValue[x];
}
return v;
}
private static int findMaxUnitValueIdx(double[] unitValue) {
// 가장 높은 가치인 인덱스 찾기
double max = -1;
int idx = -2;
for(int i=0; i<unitValue.length; i++){
if(visited[i]) continue;;
if(max < unitValue[i]) {
idx = i;
max = unitValue[i];
}
}
return idx;
}
private static double[] calculateUnitValue() {
// 단위그램당 가치 계산하기
double[] unitValue = new double[weight.length];
for(int i=0; i<weight.length; i++) unitValue[i] = (double)value[i]/weight[i];
return unitValue;
}
}
집합 커버 문제
집합 커버 문제란 n개의 원소를 가진 집합 U가 있고 U의 임의의 부분집합들을 원소로하는 집합 F가 있습니다. F의 원소들 중에서 어떤 원소들을 선택하여 합집합하여 집합 U와 같게 만들 때, 선택된 F의 원소의 개수를 최소화하는 문제가 집합 커버 문제입니다.
이러한 집합 커버 문제의 예로 신도시 학교 배치 문제를 예로 들어보겠습니다.
신도시 학교 배치 문제
현재 이 그래프는 각 10개의 마을에서 도보 15분 이내로 떨어진 거리를 하나의 간선으로 표시한 것입니다.
저희는 이 신도시에 학교를 신설하려고 합니다. 아래의 조건을 만족하는 최소의 학교 개수를 구하는 것이 이 문제의 핵심입니다.
- 학교는 마을에 위치해야한다.
- 등교 거리는 걸어서 15분 이내여야한다.
이 문제를 어떻게 해결하고 해답은 무엇일까요??
바로 분홍색으로 칠해진 곳에 학교를 배치한다면 초록색 구역과 파란색 구역으로 나뉘어서 등교가 가능하게 됩니다.
즉, 2개의 학교 수로 마을 전체를 커버할 수 있게 됩니다.
자, 이제 이 문제를 집합 커버 문제에 맞게 살짝 변경해봅시다.
신도시 0개가 있으므로 전체집합 U는 1부터 10까지를 원소로 갖는 집합이 되겠습니다.
또한 F에는 마을 i에 학교를 배치했을 때, 등교할 수 있는 마을의 집합들을 집합으로 가지는 집합이 되겠습니다. 어... 말이 조금 어려운데, 아래의 사진을 통해 확인해보죠.
이제 조금 아시겠나요??
그럼 우리는 이 집합 커서문제를 어떻게 코드로 구현해야할 지 고민해봅시다.
사실 가장 단순한 방법은 모든 경우의 수를 계산하는 것입니다. 즉, S1부터 S10으로 만들 수 있는 모든 집합을 고려해보면 될 것입니다.
즉, 원소가 10개인 집합의 부분집합의 수는 2^10-1(공집합 제외)이므로, 아마 여기서는 1023번의 경우의수를 찾으려고 할 것입니다.
따라서 이러한 문제풀이법의 시간복잡도는 O(2^n)이 됩니다. 이러한 시간복잡도는 n이 커질 경우 기하급수적으로 증가하기 때문에 알고리즘으로 사용하기는 쉽지 않습니다.
따라서 저희는 그리디 알고리즘을 이용해서 완전한 해는 아니지만 그와 가까운 근사해(Approximation Solution)를 찾습니다.
아래와 같은 과정으로 진행해볼 생각입니다.
1. U의 원소를 가장 많이 커버할 수 있는 Si를 선택해줍니다.
2. U에서Si가 커버하는 원소를 제거합니다.
3. F에서 Si를 제거합니다.
4. 결과에 쓰일 C 집합에 Si를 추가합니다.
이 과정을 U가 공집합일 때까지 반복해주면 될 것입니다.
앞서 설명한 신도시 학교 배치 문제를 다시 가져와서 생각해보죠.
가장 먼저 U의 원소를 최대한 많이 커버하는 Si를 찾아봅시다. 아마 S4가 될 것입니다.
그러면 우리는 이제 U에서 S4가 커버하는 원소를 제거하고, F에서도 S4를 제거해줍시다.
그리고 C에 S4를 추가해줍니다.
그리고 이제 남은 U의 원소에서 가장 많은 원소를 커버할 수 있는 Si를 찾아봅시다. S6이 될 것입니다. U의 전체 원소 4개 중 3개를 포함하고 있으니 말이죠.
U의 원소에서 S6에 해당하는 원소를 지우고
F에서 S6을 지운 후, C에 S6을 추가해줍시다.
자 이제, 1을 커버하는 집합을 아무거나 골라주면 되는데, 저는 S1을 골라보겠습니다.
마찬가지로 U에서 S1에 해당하는 원소를 지우고, F에서도 S1을 지우고 C에 S1을 추가해줍시다.
U가 공집합이 되었으므로 해당 알고리즘을 종료하고 C를 출력하면 되겠습니다.
이러한 흐름으로 흘러가기 위해 짜여진 코드를 확인해봅시다.
class SetCover{
public List<Integer> findSetCover(){ // 집합커버를 찾는 함수
List<Integer> C = new ArrayList<>();
while(!U.isEmpty()){
int si = findMostHaveElementInF();
removeElementInU(si);
C.add(si);
visited[si] = true;
}
return C;
}
private void removeElementInU(int si) { // Si의 원소를 U에서 제거
List<Integer> integers = F[si];
for (Integer integer : integers) {
if(U.contains(integer)) U.remove(integer);
}
}
// F 내에 있는 원소 중 U의 원소를 가장 많이 커버하는 집합 Si를 찾는 메서드
private int findMostHaveElementInF() {
int max = -1;
int idx = -1;
for(int i=0; i<F.length; i++){
if(visited[i]) continue;
int i1 = countNumberOfElementInUAtF(i);
if(max < i1){
max = i1;
idx = i;
}
}
return idx;
}
// 입력된 Si가 U에 있는 원소 중 몇개를 커버하는지 확인하는 메서드
private int countNumberOfElementInUAtF(int i) {
List<Integer> obj = F[i];
int cnt = 0;
for (Integer integer : obj) {
if(U.contains(integer)) cnt++;
}
return cnt;
}
}
이렇게 진행하게 되면 C는 다음과 같이 나오게 됩니다.
시간복잡도
이 알고리즘에서는 최악의 경우 while이 n번 반복될 수 있고, 루프 내에서 많은 집합을 cover하는 Si를 찾는데 n번, 또한 U에서 Si를 제거하는 연산 또한 n번이 소요되므로 총 O(n^3)입니다.
이로써 그리디 알고리즘에 해당하는 알고리즘 몇가지를 다뤄봤습니다. 감사합니다.
'CS > Algorithm' 카테고리의 다른 글
| [알고리즘] 분할 정복 - 최근접 점의 쌍 찾기 (1) | 2023.11.28 |
|---|---|
| [알고리즘] 선택 알고리즘이란? (1) | 2023.11.02 |
| [알고리즘] Floyd-Warshall 알고리즘이란? (0) | 2023.10.16 |
| [알고리즘] Bellman-Ford 알고리즘이란? (0) | 2023.10.16 |
| [알고리즘] Dijkstra 알고리즘이란? (3) | 2023.10.15 |