5. 그리디 알고리즘

2021.07.22 - [Coding Test/SWEA] - [Advanced] 3. 탐욕 알고리즘 - 이론편

 

그리디 알고리즘

여러 경우 중 하나를 선택 → 최적이라고 생각되는 것을 선택 → 최종 해답에 도달

1. 해 선택
   현재 상태에서 부분 문제의 최적해를 구한 뒤, 부분 해 집합에 추가
2. 실행가능성 검사
   새로운 부분 해 집합의 실행가능 여부 확인, 문제의 제약 조건 위반 검사
3. 해 검사
   새로운 부분 해 집합이 문제의 해가 되는지 확인 
   전체 문제의 해가 완성되지 않았다면 1로 돌아가 다시 시작
   

• 최적화 문제를 해결할 수 있음
• 각 선택 시점에서의 결정은 지역적으로 최적의 값임
• But, 최종적 해답이 최적이라는 보장은 없음! 따라서 문제 풀 때 오래 고민하고 선택해야함

 

탐욕 알고리즘과 동적 계획법의 비교

탐욕 알고리즘	동적 계획법
매 단계에서, 가장 좋아 보이는 것을 빠르게 선택 - 지역 최적 선택	매 단계의 선택은 해결한 하위 문제의 해를 기반으로 함
하위 문제를 풀기 전에 (탐욕적)선택이 먼저	하위 문제가 우선 해결되어야 함
Top-Down 방식	Bottom-Up 방식
일반적으로 빠르고 간결	좀더 느리고 복잡

 

대표적인 탐욕 기법의 알고리즘들

알고리즘	목적	설명
Prim	N개의 정점으로 구성된 최소 신장 트리(MST)를 찾음	정점을 하나씩 선택하는 과정에서 트리를 확장하면서 MST를 찾음	그래프
Kruskal		싸이클이 없는 서브 그래프들을 확장하면서 MST를 찾음	그래프
Dijkstra	주어진 정점에서 다른 정점들에 대한 최단 경로를 찾음	주어진 정점에서 가장 가까운 정점을 선택하면서 출발점에서 다른 모든 정점들의 최단경로를 찾음	그래프
Huffman coding	문서의 압축을 위해 문자들의 빈도수에 따라 코드 값을 부여함	출현 빈도가 낮은 문자부터 선택해서 이진 트리를 완성하고 코드값을 부여함	문자열

 

 

동전 거스름돈 문제

- 각 선택 시점에서 거스름돈이 제일 적게 남은 경우를 선택

활동 선택 문제

- 종료 시간이 가장 빠른 활동을 선택