[알고리즘] 그리디 알고리즘이란?

그리디 알고리즘이란?

그리디 알고리즘은 매 순간 최선으로 보이는 선택을 하고, 그 선택을 번복하지 않는다 는 전략이다. 그리디는 한번 결정하면 되돌아가지 않는다는 백트래킹이 없는 방식이다. 

항상 지금 최선 == 전체 최선 이 아니다. 

 

그리디 알고리즘을 적용하려면

1. 탐욕적 선택 속성 
   • 각 단계에서 국소 최적 선택을 해도, 그게 전체 최적해로 이어진다.
2. 최적 부분 구조
   • 전체 문제의 최적해가 부분 문제의 최적해로 구성된다.

 

ex) 분수 배낭 문제에서, 배낭 용량은 50kg. 물건은 쪼갤 수 있다.

물건 A: 무게 10kg, 가치 60  → kg당 가치 6
물건 B: 무게 20kg, 가치 100 → kg당 가치 5
물건 C: 무게 30kg, 가치 120 → kg당 가치 4

 

1. 탐욕적 선택 속성 확인 : kg 당 가치 기준으로 정렬 A > B > C 순서이다. 같은 1kg 을 쓴다면 어디에 쓰는게 이득이냐는 관점으로 봤을 때 성립하면 된다.

2. 최적 부분 구조 확인 : A 를 전부 넣음을 결정하면, 남은 부분에는 B 와 C 만 가지고 최적으로 채우는 문제로 줄어든다. 원 문제가 A 를 넣은 가치 + 부분 문제의 최적해로 표현된다. 

 

 

 

DP (동적 프로그래밍) 과의 차이점

동적 프로그래밍과의 차이점은, DP는 탐욕적 선택 속성이 성립하지 않을 때 사용 가능한 방법이라는 것이다.

다이나믹 프로그래밍 (DP) 정리