[알고리즘] 탐욕/그리디 알고리즘(Greedy Algorithms)

초안: 2021년 1월 27일

1차 수정 : 2023년 4월 23일

 

 

이름의 뜻?

- 이름은 각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 붙여진 것. (탐욕에 눈이 멀어서 이렇게 [ 됐다고 붙여졌다고...)

- 탐욕 알고리즘은 특별한 코드가 있는 알고리즘이 아닌 '개념적인' 알고리즘.

- 어떠한 문제에도 적용할 수 있지만, 문제마다 적용하는 방식이 모두 다르다.

 

동적계획법(DP) 보다 효율적이긴 하지만, 동적계획법처럼 반드시 최적의 해를 구해준다는 보장 하지는 못한다. 최적의 해가 나오길 바랄 뿐이다. -> 빠른 의사결정이 가능. 괜찮은 해법인 경우가 많음.

 

 

탐욕알고리즘의 동작과정

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

 

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

 

3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인. 아직 전체 문제의 해가 완성되지 않았다면,

1번의 해 선택부터 다시 시작.

 

ex) 거스름돈 문제

1. 해 선택 : 거스름돈을 주어야 할 때 단위가 큰 동전으로만 거스름돈에 추가

2. 실행 가능성 검사 : 거스름돈이 손님에게 주어야 할 액수를 초과하는지 검사. 초과한다면 추가한 동전을 거스름돈에서 빼고, 1번으로 돌아가서 한 단계 작은 단위의 동전으로 거스름돈에 추가

3. 해 검사 : 주어야 할 거스름돈이 일치 한지 확인, 액수가 모자라면 다시 1번으로 돌아가서 거스름돈에 추가할 동전 선택

 

 

탐욕 알고리즘의 중요한 속성은 항상 최적의 결과를 보장하지는 못하고, 최종적을 최적인 해법을 못 찾을수도 있음. 하지만, 충분히 훌륭한 결정을 빨리 내릴 수 있음. (보통 랜덤으로 선택하는 것보다 나으니까)

 

 

그리디 알고리즘을 사용하기 적합한 경우

- 제대로 된 해법을 구하는 알고리즘의 복잡도가 너무 높은경우

- 적당히 좋은 해법도 상관없는 경우

- 동적 계획법을 사용할 수 없는 경우(즉, 중복되는 하위 문제가 없음)

 

그리디 알고리즘을 사용할 수 있는 경우

- 최적 부분 구조

- 그리디 선택 속성 : 한번 내린 결정은 다시 돌아보지 않음.

-

 

팁 

1. 보통 최소/최대 문제

2. 여러 그리디 선택이 가능하면, 모두 시도 혹은 반려를 통해 제거할 것

3. 정렬을 해야 속도가 빨라질 수도 있음.

 

 

 

크루스칼 알고리즘에서의 그리디(탐욕적인 방법)

hyo-ue4study.tistory.com/145?category=951082

[알고리즘]크루스칼 알고리즘(Kruskal's Algorithm)

크루스칼 알고리즘의 동작 순서는 다음과 같았다.

1. 그래프 내의 몯느 간선을 가중치의 오름차순으로 목록을 만듭니다.

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

 

여기서 탐욕적인 방법으로 처리되는 부분은 2번이다. 크루스칼 알고리즘에서 간선 목록을 돌면서 최소 신장 트리를 완성해 나가는 부분이 바로 '해 선택 -  실행 가능성 검사 - 해 검사'의 반복으로 이루어진 곳이다.

 

 

다익스트라 알고리즘에서의 그리디(탐욕적인 방법)

hyo-ue4study.tistory.com/193?category=951082

[알고리즘] 최단 경로찾기 ? 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라의 동작 순서에서도

 

1. 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화한다.

 

2. 시작 정점의 경로 길이를 0으로 초기화하고(시작에서 시작까지는 0이므로), 최단 경로에 추가한다.

 

3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가.

만약 추가하려는 인접 정점이 이미 최단 경로 안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우, 다른 선행 정점을 지나던 기존의 경로를 현해 정점을 경유하도록 수정.

 

4. 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 3번 과정 반복

 

 

1,2번은 알고리즘 초기화에 가깝고, 3,4번이 본격적으로 만드는 과정입니다. 3번은 해 선택과 실행 가능성 검사, 4번이 해검사를 맡고 있다. 이 알고리즘에서는 최단경로가 해 집합이고, 각 정점이 부분 문제에 대한 해입니다.