알고리즘 5주차 월요일 강의

Greedy Algorithm

 

Dynamic Programming is Blind

뭔가 잘 보이지 않는 상태에서 푸는 문제의 느낌이라는 것. matrix chain이나 LCS같은 경우의 Time Complexity는 다음과 같다. 세타라고 표현을 해야 한다. (정정 필요) LCS의 경우 M과 N이 order가 비슷하다고 하면 세타 M^2까지 가능할 수 도 있다. 비교적 차수가 높게 나온다. 왜 그런가? Optimal solution을 계산할 때 선택이 굉장히 여러가지가 존재한다. 그 선택이 어느게 옳은 선택인지 모든 경우의 수를 고려해야 하기 때문이다. 

 

Example: MCM

맨처음 (1,6)에 있는 것 중 최적의 값을 위해서 총 5번의 곱셈을 계산하게 된다. 그 중 최적의 값인 노란색이 채택이 된다. 어느 것이 최적의 값을 나타내는 지 모르기 때문에 Blind 하다고 표현을 한다. 색칠되어 있지 않은 것들도 다 계산하느라 시간 낭비를 하게 된다. MCM 문제는 물론 그렇게 적은 시간으로 풀 수 있다는 것은 아니지만 필요 없는 부분을 계산한다는 것을 보여주기 위한 사례로 가져온 것이다. DP 마저도 불필요한 측면이 존재하게 되기도 한다. 어떤 선택이 최고인지 최선의 선택인지 제약하는 조건이 있다면 필요없는 계산을 하지 않고도 선택을 할 수 있지 않을까? 라는 것으로 부터
출발을 한다. Greedy Algorithm은 어떤 것이 최적의 선택인지 찾기 위해 작업을 하는 것을 의미한다.

 

Greedy Algorithm

최적화 문제를 푸는데 어떤 성질을 가지고 있는 것들은 Greedy 방식으로 해결할 수 있다. 어떤 순간에  최적으로 보이는 선택들을 하게 된다. 최적의 선택을 계속해서 해나간다. local optimum이란 매 순간의 최선의 선택을 의미한다. 결국 마지막 순간에 갔을 때 Global하게 봤을 때 최적의 선택이었다고 말할 수 있는 문제들은 Greedy로 풀 수 있다. 

 

Coin change

잔돈을 줄 때 최소한의 개수로 주는 방법을 구하는 것. 760에서 가장 큰 denomination은 500원이다. 760에서 500을 뺀 260 이고 260에서 100원짜리 2개를 사용하면 60원이 남는다. 60에서 다음 것은 50원을 빼는 것이고 10원이 남으면 10원 하나를 이용하면 된다.

 

An activity-selection problem

여러 개의 스케줄을 관리하고 싶은 것이다. 하지만 공통의 자원을 필요로 하는 상황이다. maximum size set of mutually compatible activities 가장 많은 수의 activity를 사용하고 싶은 것이다. 시간이 겹치지 않도록 선택할 수 있는 여러 가지의 set이 존재한다. 만약 mutually exclusive한다고 하면 이 경우 4개가 maximum size가 된다. ai라는 activity를 [si, fi) 로 표현을 할 수 있다. sorting을 하는데 finish time을 가지고 sorting을 진행한다.

 

An activity selection problem
Mutually compatible하다는 것은 시작과 끝점을 기준으로 겹치지 않는 시간대의 set을 의미한다. 

 

The Structure of an Optimal Schedule
S중의 부분 집합. 끝난 후에 시작하고 시작하기 전에 끝나는 것. ai가 끝난 후 시작되고 aj가 시작하기 전에 끝나는 것들을 의미한다.

 

The Structure of an Optimal Schedule
DP로 푸는 것을 생각해보자. 

 

An activity selection problem
local optimum 이 global optimal 하게 접근하는 것을 의미한다. 

 

Theorem
Empty Set이 아니고 am을 가장 빨리 끝나는 activity라고 가정해보자.