1. 그리디 알고리즘 (Greedy Algorithm, 탐욕법)이란?
: 눈 앞의 이익만을 좇는 알고리즘. 매 선택마다 그 당시 가장 최적인 값을 선택한다.
2. 그리디 알고리즘 특징
1. 백트래킹으로 추가점검 X
- 백트래킹 : 해를 찾는 도중 해가 아니여서 막히면, 되돌아가서 다시 해를 찾아가는 기법
2. 최적해 ≠ 그리디 인 경우가 많다.
- 근데 안좋아보이는데 왜쓰냐? -> 정확하게 구하는 것보다 속도가 빠르다..! 따라서 정확한것 보단 근사값 구하는게 더 효율적일 때도 쓰임. (근사값 구하는 알고리즘에는 조합 탐색, 메타휴리스틱 알고리즘 등도 있음.)
3. 그리디 알고리즘을 사용해 최적해가 구해지기위한 조건 ( = 탐욕적 알고리즘의 정당성 증명)
a. 탐욕 선택 속성(Greedy Choice Property)
- 답의 모든 부분을 고려하지 않고(=백트래킹없이), 각 단계에서 탐욕적으로만 선택하더라도 최적해를 구할 수 있다. 즉, 이전의 선택이 이후에 영향을 주지 않음을 의미
- 증명 : 문제의 최적해 중, 탐욕적인 선택을 포함하지 않는 답이 있다고 가정
b. 최적부분 구조 (Optimal Substructure)
- 부분문제의 최적 결과가 전체에도 그대로 적용될 수 있어야함 (이부분은 DP랑 유사한 부분. 하지만 DP의 경우는 문제가 중복(overlapping)되기 때문에, 탐욕 선택 속성을 만족하지 못하게된다. 왜냐? 중복되면 다음에 풀 문제(이후)가 이전의 작은 문제의 결과에 영향을 받게 되기 때문이다.)
- 증명 : 대개 매우 자명
이 조건들을 증명하려면 수학적 증명이 동반되어야 하지만, 과정이 어려우므로 테스트 코드로 정상 작동하는지를 알아보는 방식으로 대체하는경우가 많음. 그리디가 아님을 증명하는 것은 그리디임을 증명하는것보단 쉬움. 그냥 반례 하나만 찾으면 끝이라서 그리고 이런 조건들 만족하지 않더라도 근사 알고리즘으로라도 이용가능 ~
3. 그리디 알고리즘 문제 예제
예제 1. 활동 선택 Action Selection
Question. N개의 활동이 있고 각 활동에는 시작시간 및 종료시간이 있다. 이때 한 사람이 최대한 많이 할 수 있는 활동의 수는?
- 활동들의 이름과 시작시간, 종료시간
Answer.
접근법 : 전체에서 가장 종료시간이 빠른 것 선택. → 선택한 활동과 시간이 겹치는 것을 제외. →처음부터 반복
1. 시작 시간은 종료 시간 이전이므로 고려 X → 종료 시간 기준으로 정렬.가장 종료시간이 빠른 건 찰흙공예.
2. 찰흙공예가 끝난 뒤, 현재 시간은 찰흙공예의 종료시간인 2이다. 이때 다른 활동들의 시작시간도 2 이상이므로 우선은 다 실행가능. 1과 동일하게 종료 시간 기준으로 정렬(찰흙공예 제외)가장 종료시간이 빠른 그림그리기 실행
3. 현재 시간 = 4. 종이접기와 수수깡공예는 시작시간이 4보다 작으므로 실행 불가. 따라서 남은 활동들 중 가장 종료시간이 빠른 과자 만들기 실행.
결과 : 찰흙공예 → 그림그리기 → 과자 만들기 총 3가지 활동 가능.
예제 2. 거스름돈 문제
Q. 거스름돈이 2770원인 경우, 화폐의 개수가 최소가 되도록 화폐를 선택하는 방법은?
A.
n = 2770
count = 0
coin_type = [1000, 500, 100, 50, 10]
for coin in coin_types:
count += n // coin
n %= coin
// 1000 2, 500 1 100 2 50 1 10 2 => 8
print(count)
참고자료
https://hongjw1938.tistory.com/172 : 이론
https://velog.io/@contea95/탐욕법그리디-알고리즘 : 이론
