탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘 : 동적 계획법과 마찬가지로 최적화 문제의 답을 얻기 위해 사용한다.

각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 해서 붙여졌다.

-> 항상 최적의 결과를 보장하지는 못한다!!!

 

동적 계획법은 최적의 해를 구하긴 하지만 탐욕 알고리즘보다는 덜 효율적(대게 더 많은 수행 시간을 요구합니다) 입니다. 반면에 탐욕 알고리즘은 동적 계획법보다 효율적이긴 하지만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장은 하지 못한다. 최적의 해가 나오기를 바랄뿐이다.

 

탐욕 알고리즘으로 풀 수 있는 문제는, 동적 계획법처럼 대상 문제가 최적 부분 구조를 갖고 있어야한다.

< 탐욕 알고리즘 >

1) 해 선택 :  현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합에 추가한다.

2) 실행 가능성 검사 : 새로운 부분해 집합이 실행가능한지를 확인한다. 문제의 제약 조건을 위반하지 않는지를 검사한다.

3) 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1)의 해 선택부터 다시 시작한다.

 

- 편의점 점원의 거스름돈 줄이기

---

- 편의점 점원의 거스름돈 줄이기

Q : 어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

1) 해 선택 : 단위가 큰 동전으로 거스름돈 준다.

2) 실행 가능성 검사 : 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인. 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1)로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다.

3) 해 검사 : 거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야 하는 액수와 일치하는 것이다. 거스름돈을 확인해서 액수에 모자라면 다시 1)로 돌아가서 거스름돈에 추가할 동전을 고른다.

 

우리나라의 동전은 500원, 100원, 50원, 10원, 그리고 1원 이렇게 다섯가지가 있다.

이 다섯 가지 중 어느 두 개를 골라 두 동전 사이의 최대 공약수를 계산해도 항상 작은 값의 동전 단위가 나온다.

-> 이런 체계에서는 누구나 최소 개수의 동전으로 이루어진 거스름돈을 만들 수 있다.

---

- 크루수칼의 최소 신장 트리 알고리즘 다시 보기

<크루스칼 알고리즘>

1) 그래프 내의 모든 간선을 가중치의 오름차순으로 목록을 만든다.

2) 1)에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가한다. 단, 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안된다. 

 

크루스칼 알고리즘이 탐욕적인 방법으로 처리되는 부분은 2)이다. 

탐욕 알고리즘은 해 선택 -> 실행 가능성 검사 -> 해 검사의 반복으로 설계된다.

크루스칼 알고리즘에서 간선 목록을 돌면서 최소 신장 트리를 완성해 나가는 부분이

바로 해 선택 -> 실행 가능성 검사 -> 해 검사의 반복으로 이루어지는 곳이다.

 

해 선택은 가장 작은 가중치의 간선을 고름으로써 이루어진다. 이미 정렬되어 있으니 차례대로 선택하면 된다.

 

크루스칼 알고리즘에서 중요한 것은 실행 가능성 검사이다. 해 선택 단계에서 고른 간선이 신장 트리 내에 사이클을 형성한다면, 이 간선을 버리고 다음 가중치의 간선을 골라야 하기 때문이다.

크루스칼 알고리즘은 사이클 탐지를 위해 분리 집합을 이용한다. 크루스칼 알고리즘은 간선을 추가할 때마다 간선의 양 끝에 있는 정점들을 같은 집합에 추가시키는데, 이 두 개의 정점이 이미 같은 집합에 소속되어 있다면 이 간선이 사이클을 형성한다고 판단한다.

---

- 다익스트라의 최단 경로 알고리즘 다시 보기

// 추후 추가

---

- 허프만 코딩을 이용한 데이터 압축

// 추후 추가