-
[알고리즘 개념] 탐욕 알고리즘알고리즘 공부/알고리즘 개념 2020. 8. 16. 18:52
탐욕 알고리즘
탐욕 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.
즉, 동적 프로그래밍을 보완하는 알고리즘인 것이다.
탐욕 알고리즘은 각 단계에서 조건에 맞는 최선의 선택을 하는 기법이다.
그렇기 때문에 모든 문제에 대해서 탐욕 알고리즘이 통하지 않는다.
예를 들면, 지금 선택하면 1개의 마시멜로우를 받고, 1분을 기다리면 2개의 마시멜로우를 준다고 했을 때
탐욕 알고리즘은 1개의 마시멜로우를 받는 선택을 내린다.
따라서 어떤 문제가 탐욕 알고리즘이 통하는지 잘 판단하여야 한다.
탐욕 알고리즘은 다음과 같은 과정을 거친다.
1. 해 선택 : 현재 가장 최적인 해를 구하여, 이를 부분해 집합에 추가한다.
2. 적절성 검사 : 새로운 부분해 집합이 적절한지 검사한다.
3. 해검사 : 새로운 부분해 집합이 문제의 해가 되는지 검사한다.
문제의 해가 완성되지 않았다면, 1부터 다시 반복한다.
탐욕 알고리즘을 사용하여 문제를 풀이하는 대표적인 문제들을 살펴보자.
최소수의 동전으로 거스름돈 거슬러 주기
-> 가장 가치가 높은 동전부터 고려한다. 총 거스름돈을 만족하면 해를 출력하고
만족하지 않는다면 가치가 낮은 동전을 추가한다.
최소 비용 신장트리 (Minimum spanning Trees)
: 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리
-> 이 문제는 프림 알고리즘, 크루스칼 알고리즘이 존재한다. 이 두 알고리즘은 탐욕 알고리즘 중 하나이다.
*크루스칼 알고리즘은 가중치가 작은 간선을 추가하며, 트리구조를 만족하는지 확인하는 방식이다.
다익스트라 알고리즘
: 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘
-> 시작 정점에 인접한 간선 중 최소 비용 간선을 추가한다. 추가된 정점과 인접한 간선들을 갱신하며 그 중 최소 비용 간선을 추가하며 반복한다.
허프만 코딩
: 데이터를 압축하는 방법 중의 하나로 쓰이는 알고리즘
-> 허프만 트리와 비교하여 잎 노드이면 바로 변환하고, 잎 노드가 아니라면 다음 비트를 읽는다.
출처 : https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
'알고리즘 공부 > 알고리즘 개념' 카테고리의 다른 글
[알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS) (0) 2020.08.25 [알고리즘 개념] 동적계획법 (1) 2020.08.22 [알고리즘 개념] 완전 탐색 (1) 2020.08.14 [알고리즘 개념] 힙 (heap) (1) 2020.08.11 [알고리즘 개념] 스택/큐 (1) 2020.08.09