[알고리즘] Greedy algorithm

(2021.11.04)

알고리즘 수업들으면서 정리하기 17탄

 

w10-1 실시간 강의

greedy algorithm에 관한 내용과 huffman code 설명 조금(huffman은 다음 동영상정리에)

activity selection 내용 전에 greedy 알고리즘 설명해주신 부분의 연장선 같음

---

 

Greedy algorithm

 

greedy algorithm은 언제나 optimal solution을 도출해내는 것은 아니다. 

greedy algorithm으로 해결했을 때, 그 결과가 optimal solution이 아닐 수도 있다는 것이다.

어떠한 상황에서 greedy로 풀면 optimal한 결과가 나온다 라는 general한 접근법이 없기 때문에 greedy algorithm은 해봐야 알 수 있다.

 

• greedy-choice property
• optimal substructure

 

greedy-choice property: locally optimal choice를 통해서 globally choice를 도출해낼 수 있다.

DP와는 다르게 top-down 방식으로 문제를 해결한다.

 

optimal substructure: problem에 대한 optimal solution이 subproblem에 대한 optimal solution을 포함한다.

 

 

 

 

DP vs Greedy 비교

 

--> 여기서 가장 키포인트는 DP는 sub-problem을 모두 solve 한 후에 choice하는 것이고, Greedy는 먼저 choice 한 후에 sub-problem을 solve 한다는 것이다.

 

 

greedy algorithm으로 optimal solution을 도출할 수 없는 문제가 있는데 knapsack problem이 그 중 하나이다.

 

출처: 교수님 강의노트

 

value값이 큰 순서대로 greedy 알고리즘을 적용하면, value가 10인 A item만 가능하게 된다.

(A의 무게가 25인데 한계가 30이므로 B나 C를 담을 수 가 없음)

그러나 optimal solution은 B, C item을 고르는 것이다.

따라서, 이는 greedy algorithm이 optimal solution을 도출해내지 못하는 반례가 된다.

 

 

 

출처: 교수님 강의노트

 

이번에는 weight 값이 작은 순서대로 greedy 알고리즘을 적용해본다.

그러면, C,B,A 순서로 고려해보는데 value 합이 8인 C,B가 선택된다.

(C와 B를 선택하면, 무게가 24인데 한계가 30이므로 A를 더 담을 수 가 없음)

그러나 optimal solution 은 value가 10인 A를 선택하는 것이다.

따라서, 이는 greedy algorithm이 optimal solution을 도출해내지 못하는 반례가 된다.

 

 

결국 knapsack 문제에서 greedy algorithm을 사용하여 optimal solution을 도출해낼 수 없다.

knapsack 문제에서 weight와 value를 모두 고려해야하는데 weight와 value가 비례관계가 아니기 때문에 두가지 사항 모두 고려하는 것은 어렵다.