그리디 개념.
- 그리디는 '탐욕스러운' 또는 '욕심이 많은' 이라는 뜻입니다.
그리디 알고리즘은 문제 해결과정에서 결정 순간만다 눈 앞에 보이는 최선의 선택을 하며 선택을 번복하지 않는 알고리즘 입니다.
이런 특성으로 그리디 알고리즘은 지역 최적해를 추구한다고 말하기도 합니다.
예시를 통해 설명을 이어나가 보겠습니다.
예시1) 거스름돈 내어주기
다음과 같은 문제를 보면 다음과 같은 생각이 떠오릅니다 .
01.큰 동전부터 주기
- 해당 방법으로 한다면 5원을 1개 주고 3원을 3개 주어야 하므로 총 4개의 동전을 주어야 합니다.
02. 4원의 동전을 2개만 준다면?
- 위의 방법보다 동전의 개수가 적게 거스름돈을 줄 수 있기 때문에 이것이 정답입니다.
다음과 같이 그리디 알고리즘을 처음 생각한다면 가장 큰 값인 5원을 주는 것 부터 생각하지만, 옳은 정답을 내지는 않습니다.
따라서 그리디 알고리즘이 항상 최적의 해를 보장하진 못한다고 설명할 수 있습니다.
그렇다면 그리디 알고리즘이 최적해를 보장하려면?
- 그리디 알고리즘은 특정한 상황에서 최적해를 보장하므로 이를 활용하면 문제를 잘 해결할 수 있습니다.
특정한 상황 2가지
- 최적 부분 구조(optimal substructure) : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
- 그리디 선택 속성( greedy selection property) : 선택 과정이 다른 과정에 영향을 주지 않음
그리디 알고리즘이 최적 부분 구조에 어긋나는 이유는 부분해를 푸는 것이 전체해를 푸는 데에 도움을 주지 않는다는 것입니다.
방금 거스름돈 문제에서 8원을 거스름돈으로 주는 상황에서 5원 동전을 먼저 선택하면 그 다음에는 4원 동전을 선택할 수 없습니다.
5원 동전을 먼저 선택한 것이 제약이 되어 동전 개수를 최소로 할 수 없기 때문입니다.
이렇게 그리디 선택은 선택에 제약을 주며 최적의 해를 구하지 못하기도 합니다.
그러나, 그리디 알고리즘이 무용지물은 아닙니다. 그리디 알고리즘은 빠른 시간 내에 근사해를 제공하는 효율적인 방법 중 하나이므로 문제의 특성과 알고리즘 선택 기준을 잘 이해하면 매우 유용하게 활용될 수 있습니다.
지금부터 그리디 알고리즘을 쓰면 좋은 상황을 하나씩 알아보겠습니다.
최소 신장 트리 문제
- 최소 신장 트리는 그리디 알고리즘을 사용하는 대표적인 트리 형태 자료구조 입니다.
우선 다음을 설명하기 위해 신장 트리란 무엇인지 부터 알아보겠습니다.
신장트리란?
- 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프를 말합니다.
신장 트리가 아닌 사진의 예시를 보면 왼쪽 그래프는 정점이 6개 간선이 5개지만 모든 정점이 연결되어 있지 않기 때문에 신장 트리가 아니며, 오른쪽 그림은 간선이 트리의 개수보다 많으므로 신장 트리라고 할 수 없습니다.
최소 신장 트리란?
- 신장 트리 중 가선의 가중치 합이 최소면 최소 신장 트리 (MST)라고 합니다.
경우에 따라서 최소 신장 트리는 하나가 아닐 수도 있습니다.
최소 신장 트리를 구하는 대표적인 그리디 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다.
다음 그림을 통해 설명을 이어나가겠습니다.
프림알고리즘으로 최소 신장 트리를 구하는 알고리즘은 다음과 같습니다.
1. 임의의 정점을 하나 선택해서 최소 신장 트리에 추가합니다.
2. 최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가 ( 이 부분이 그리디적 선택입니다.)
(단, 순환을 형성하지 않는 정점을 추가해야 합니다.)
3. 과정 2를 신장 트리 조건에 만족할 때까지 반복합니다.
크루스칼 알고리즘으로 최소 신장 트리 구하기
크루스칼 알고리즘은 다음과 같습니다.
1. 그래프의 모드 간선을 가중치 기준으로 오름차순 정렬합니다.
2. 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가합니다.( 이 부분이 그리디적 선택입니다.)
3. 과정 2를 신장 트리 조건에 만족할때 까지 반복합니다.
크루스칼 알고리즘은 모든 간선을 가중치 기준으로 오름차순 정렬하다는 점만 빼면 나머지 규칙은 프림 알고리즘과 같습니다.
바로 단계별 알고리즘 진행을 살펴봅시다.
프림 알고리즘 vs 크루스칼 알고리즘 비교
그림 자료 출처
( 코딩 테스트 합격자 되기 : C++ 편 )