탐욕알고리즘(greedy) 나만의 정리

탐욕알고리즘(greedy)

• 탐욕 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법
• 각 선택 시점에서 이루어지는 결정은 지역적으로는최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다
  • 쉬운예) 지금 선택하면 사탕 10개를 주고, 1분뒤 선택하면 사탕 20개를 준다고할때, 탐욕알고리즘은 지금 선택하지만 이 선택이 최선은 아니다.

1. 탐욕알고리즘 동작과정

• 해 선택
  • 현재 상태에서 부분 문제의 최적해를 구한뒤, 이를 부분해 집합에 추가한다.
• 실행 가능성 검사
  • 새로운 부분해 집합이 실행가능한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검색한다.
• 해 검사: 새로운 부분 해 집합이 문제의 해가 되는지를 확인한다.

ex) 2370원을 거슬러주자!( 결정할때, 최선의 결정을함)
1000원 => 2000원 => 3000천원 (실행가능성에서 걸림 -1000원)
2000원 =>2500원(실행가능성에서 걸림 -500)
=>2100원 => 2200원 ............ => 2370원

2. 탐욕알고리즘 문제유형

단위로 분할하여 푸는문제

(1) 배낭짐싸기

	무게	값	값/kg
물건1	5kg	50만원	10만원/kg
물건2	10kg	60만원	6만원/kg
물건3	20kg	140만원	7만원/kg

탐욕알고리즘에 따르면, 가성비가 좋은물건인 물건1부터 배낭넣으면 된다.
하지만, 조건에서 제한된 무게와 값이 분명 존재하기때문에, 함부로 담을수 없다.
그래서 탐욕알고리즘으로 문제를 풀기란 사실상 어렵다.

(2) 회의실 배정하기

• 회의실을 잡기위해 회의실의 시간이 아래처럼 잡혀있다.

이러한 문제를 탐욕기법으로 푼다면,

• 종료시간이 빠른순서대로 활동들을 정렬한다.
• 첫번째 활동을 선택한다.
• 선택할 활동의 종료시간보다 빠른 시작시간을 갖는 활동을 모두 저장한다.
• 남들 활동들에 대해서 위 과정을 반복

가능한 활동 집합을 찾아보면

{a1,a4,a8,a10}, {a2,a4,a8,a10}, {a3,a7,a10}, {a4,a8,a10}

개념 정리

원문제의 최적해 = 탐욕적선택 + 하위문제의 최적해

• 탐욕적선택
  • 탐욕적 선택은 최적해로 갈수있음을 증명해라!
• 하위문제의 최적해
  • 최적화 문제를 정형화!

프로그램을 구현하면서 잘 안풀릴경우 완전검색으로 하는게 일반적이지만 완전검색조차 어렵다면, 
머릿속에 생각나는대로 ( 2730원을 주려는데 천원부터 주는것처럼) 풀자!! => 
이러한 생각이 탐욕알고리즘을 머릿속에 깔고가는것!
대신 탐욕알고리즘에 빗나가는 예외사항을 꼼꼼하게 찾아내야한다.