7-0강 - Greedy Algorithm 0 (그리디 알고리즘)

0. Greedy Algorithm

(대부분의 문제는 일련의 선택으로 구성되어 있는데)

현재 상황에서 가장 좋은 것을 선택

=> 선택의 결과가 전체로 보았을 때 좋지 않을 수도 있습니다. 

 

1) Optimality

1> global optimal & 2> local optimal

2) (Combinatorial) Optimization Problem

0> combinatorial : solution이 discrete & finite set이다.

1> 구성

[1] input

[2] constraint

[3] objective

[4] output : [1]로 인해, [2]를 만족하는, [3]을 최소/최대화 하는 solution

 

2> solution

• feasible solution : constraint를 만족하는 solution
• optimal solution : object function을 최대/최소화 하는 solution

3) Greedy Algorithm

1> (대부분의 문제는 일련의 선택으로 구성되어 있는데) 현재 상황에서 가장 좋은 것을 선택

=> 선택의 결과가 전체로 보았을 때 좋지 않을 수도 있습니다. (local optimal일 수 있습니다.)

 

2> heuristic algorithm

global optimal임을 증명해야 하지만 증명이 어려울 수 있습니다. 

이러한 경우를 heuristic algorithm이라고 하고

실험을 통해 performance를 보여줘야 합니다.

=> 그래서 benchmark data로 증명합니다.

 

3> greedy algorithm의 generic procedure

4) Example : Coin Changing Problem

1> Definition

[1] input

- 가지고 있는 동전 집합 S

- 거슬러 줄 액수 C

[2] constraint

- 선택한 동전의 액수가 C여야 한다.

[3] objective 

- S에서 선택한 동전의 총 개수가 작아야 한다.

[4] output

 

2> Algorithm

 

5) Optimality

optimal임을 증명하기가 어렵습니다.

(동전 체계가 바뀌면 optimal이 아닐 수도 있습니다.)