그리디 알고리즘
: '최적인 답을 선택하여 적하반 결과를 도출하는 알고리즘
: 그 순간에 대해서는 최적이지만, 그것을 종합적으로 봤을 때는 최적이라는 보장은 없다는 것을 명심해야한다.
어떤 경우에 잘 동작하는가
✔ 탐욕 선택 속성
= 탐욕적으로 선택하더라도 최적해를 구할 수 있다는 것.
= 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것.
= (방법)
1. 우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정
2. 이것을 적절히 조작해 우리가 선택한 방법을 포함하는 최적해를 만듬.
✔ 최적 부분 구조
= 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보이는 것.
참조2
특성을 가지는 문제를 해결하는데 강점이 있다.
최적 부분 구조
: 서울에서 대구까지 가는 경로가 세가지가 있고, 부산까지도 세가지 경로가 있다고 보자. 이때 서울에서 부산까지 가는 최단 경로는 서울에서 대구까지 가는 최단 경로와 대구에서 부산까지 가는 최단 경로의 합이다. 따라서 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다.
근사 알고리즘
위의 조건이 성립하지 않는 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능하다. 그리디 알고리즘은 어느정도 적합한 수준의 해답을 알려준다. "적당한 괜찮은 방법"을 찾을 때 사용할 수 있따. 특시 계산 속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 떄문에 실용적으로 사용이 가능하다. 하지만 이게 정말로 적당히 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다.
문제 해결 방법
- 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사 : 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가서 위의 과정을 반복한다.
책 내용 정리
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
- 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답을 찾는 것으로 타협할 수 있따. 즉, 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 쓰인다.
예제
'활동 선택 문제'. 회의실이 한개밖에 없는데 n 팀의 각각 회의하고 싶은 시간을 제출했다고 한다. 두 팀이 회의실을 같이 쓸수는 없어서 서로 겹치지 않는 회의들만 골라서 진행해야 한다. 최대 몇 개나 선택할 수 있는가?
-> 무식하게 푸는 방법은 모든 부분 집합을 하나하나 만들어 보며 그중 회의들이 겁치지 않는 답들을 걸러내고 그 중 가장 큰 부분 집합을 찾아내는 것. 하지만 시간이 많이 걸린다.
-> 'greedy'하게 풀어내려면 길이가 짧은 회의부터 하나하나하나 순회하며 겹치지 않는 것들을 추가해나갈 수 있다.
-> 다른 방법은 길이와 상관없이 가장 먼저 끝나느 회의부터 선택하는 것.
-> 위의 알고리즘의 경우 '탐욕적 선택 속성'이 성립한다는 말은 "가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재한다"라는 조건이 성립한다는 뜻이다.
-> 구현을 하려면
1. 목록을 배열에 저장해서 종료 시간의 오름차순으로 정렬해둔다.
이때 젤 첫번째는 우리가 무조건 선택해도 된다.
2. 첫번째 회의와 겹치지 않는 회의를 찾는다.
3. 반복
