그리디 알고리즘(Greedy Algorithm)
매 선택 단계에서 현재 상황에서 당장 최적의 선택을 하며, 전체적으로 최적의 결과를 얻기를 기대하는 방식이다.
각 단계에서의 최선의 선택이 최종 결과도 최적이라는 보장은 없다.
그리디 알고리즘 진행 방식
- 문제를 분석하여 최적해 구조와 선택 기준을 결정한다.
- 문제의 구조에 맞게 선택 절차를 정의한다. - 선택 절차(Selection Procedure)
- 선택 절차에 따라 선택을 수행한다.
- 선택된 해가 문제의 조건을 만족하는지 검사한다. - 적절성 검사(Feasibility Check)
- 모든 선택이 완료되면 해답을 검사한다. - 해답 검사(Solution Check)
- 조건을 만족하지 않으면 해답으로 인정되지 않는다.
그리디 알고리즘 특징
- 지역 최적 선택(Local Optimal Choices): 각 단계에서 지역적으로 최적인 선택을 함으로써, 전체 문제의 해답을 구성한다.
- 탐욕적 속성(Greedy Property): 한 번 선택된 해는 재검토하지 않는다. 이전의 선택을 되돌아보거나 변경하지 않는다.
- 해 선택의 순차적 진행(Sequential Selection): 해를 구성하는 요소들을 하나씩 순차적으로 선택한다.
그리디 알고리즘과 동적 계획법의 차이점
- 그리디 알고리즘은 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 반면, 동적 계획법은 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결한다.
- 그리디 알고리즘은 동적 계획법과 달리 중복 부분 문제를 해결하지 않는다.
- 그리디 알고리즘은 각 단계의 상황에서 최선의 선택으로 최적의 경로를 구하기 때문에, 최적이 아닌 경우가 되거나, 풀리지 않는 문제가 될 수 있다. 하지만 동적 계획법은 모든 상황을 계산하여 최적의 경로를 구하는 방식이기 때문에 시간이 오래 걸린다.
그리디 알고리즘 예시
1. 동전 거스름돈 문제
가장 큰 단위의 동전부터 최대한 사용하여 거스름돈을 주는 문제다.
거스름돈을 줄 때 사용되는 동전의 수를 최소화하는 것을 목표로 한다.
시간복잡도는 O(n) 이다. n은 동전의 종류 수
2. 최소 신장 트리(Minimum Spanning Tree)
주어진 그래프의 모든 정점을 최소한의 비용으로 연결하는 트리를 찾는 문제다.
- 크루스칼 알고리즘(Kruskal's Algorithm)
- 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
- 가장 가중치가 낮은 간선부터 선택하여 신장 트리에 추가하되, 사이클이 형성되지 않도록 한다.
- 이 과정을 정점의 수 - 1개의 간선이 선택될 때까지 반복한다.
- 프림 알고리즘(Prim's Algorithm)
- 시작 정점을 선택하고, 해당 정점과 인접한 간선 중 가장 낮은 가중치를 가진 간선을 선택한다.
- 선택된 간선과 연결된 새로운 정점을 신장 트리에 추가하고, 이 정점에서 다시 가장 낮은 가중치를 가진 간선을 선택하는 과정을 반복한다.
- 이 과정은 모든 정점이 트리에 포함될 때까지 계속된다.
3. 작업 스케줄링 문제
여러 작업이 주어졌을 때, 종료 시간에 따라 오름차순으로 정렬한 다음, 가장 빨리 끝나는 작업부터 차례로 스케줄에 추가하여 작업을 처리하는 알고리즘이다.
작업을 정렬하는 데 O(nlogn) 시간이 소요되고, 각 작업을 검토하고 스케줄에 추가하는 데 상수 시간이 걸리므로 전체 시간 복잡도는 O(nlogn)이다.
안녕하세요