[COSE214] Dynamic Programming, Greedy Algorithm

Dynamic Programming으로 문제를 해결하기 위해 문제가 갖춰야 할 structural properties에 대해서 서술하고, DP로 해결할 수 있는 문제의 예시에 대해 서술하시오. 

 

Dynamic Programming으로 해결할 수 있는 문제의 예시에는 두 개 이상의 assembly line에서 여러 작업들을 수행하여 최소 시간 또는 비용으로 제품을 완성하는 문제인 Assembly line scheduling problem, 여러 개의 행렬을 곱하는 과정에서 최소한의 곱셈 연산을 수행하는 최적의 순서를 찾는 문제인 Matrix chain multiplication problem , 한정된 용량을 가진 배낭에 최대한 가치 있는 물건을 넣는 문제인 knapsack problem 등이 있다. 

DP가 적용되기 위해서는 큰 문제들을 작은 문제들로 나눌 수 있어야 하고, 작은 문제들의 최적해의 집합이 큰 문제의 최적해와 일치해야 하며, Divide and Conquer와 다르게 해당 작은 문제들 사이에 중복되는 문제가 존재하여 효율성을 개선할 수 있는 여지가 있어야 한다. 

 

 

Assembly line scheduling problem

1. Optimal Substructure Property : 큰 문제의 optimal solution이 작은 문제의 optimal solution으로 구해질 수 있는 성질을 말하는 것으로, 전체 문 제를 작은 부분 문제로 나누어 해결하는 방식이다. Assembly line scheduling problem이 optimal substructure property를 가지는 이유는 다음과 같이 증명할 수 있다. 

즉, assembly-line problem에서 subproblems에 대한 optimal solution을 build 함으로써 최종적인 optimal solution을 building 할 수 있다. 

 

2. Overlapping Subproblems Property :동일한 부분 문제가 여러 번 반복될 때, 그 문제를 반복 계산하는 대신 한 번만 계산하여 그 결과값을 저장하고 재사용할 수 있을 때 이를 overlapping subproblems property를 가진다고 한다. 

 

Matrix chain multiplication

 

• 행렬의 곱셈 시 두 행렬이 compatible 하다는 것은 앞 행렬의 열 수와 뒷 행렬의 행 수가 같아서 곱할 수 있는 것을 말한다. 

 

knapsack problem

Knapsack problem은 주어진 가방의 용량 W를 초과하지 않으면서 가치를 최대화하는 아이템의 선택을 찾는 문제이다. 이 때 각 아이템을 하나씩만 선택할 수 있고, 아이템을 자를 수 없어서 넣거나 안넣는 선택 중 하나만 해야 하는 것을 0/1 knapsack problem이라고 하고, 아이템을 자를 수 있어서 부분적으로 넣을 수 있는 문제를 fractional knapsack problem이라고 한다. 0/1 knapsack problem은 greedy algorithm으로 풀 수 없지만, fractional knapsack problem은 criterion인 value/weight을 기준으로 greedy algorithm으로 풀 수 있다. 

 

0/1 knapsack problem

 

P[i, W]란 i개의 보석이 있고 배낭의 무게 한도가 W일 때 최적의 이익을 의미한다. 다음 점화식은 1) i번째 보석이 배낭의 무게 한도보다 무거우면 배낭에 넣을수가 없으므로, i번째 보석을 뺀 i-1개의 보석들을 가지고 구한 전 단계의 최적값을 그대로 가져온다. 2) 그렇지 않은 경우, i번째 보석을 위해 i번째 보석만큼 무게를 비웠을 때 최적값에 i번째 보석 가격을 더한 값 OR i-1개의 보석들을 가지고 구한 전 단계의 최적 값 중 큰 것을 선택하는 것이다. 즉, 현 단계에서의 optimal solution을 구할 때 전 단계의 optimal solution을 활용하게 되므로 이는 optimal substructure property를 가진다고 할 수 있다. 

 

 

Activity selection problem

mutually compatible activities에서 maximum size의 subset을 찾는 문제를 말하며, 예시로는 한번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할 수 있는 스케줄을 짜는 문제를 들 수 있다. Greedy 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘으로, 순간마다 하는 선택은 locally optimal이지만, 그 선택들의 합이 globally optimal 하드는 보장은 없다. 

activity selection problem에서 greedy 알고리즘을 적용하는 방법은 제일 먼저 종료되는 활동을 선택하고, 해당 활동과 양립할 수 있는 활동들의 subproblem에서 또 다시 제일 먼저 종료되는 활동을 선택하는 것이다. 이런식으로 반복하면 최대한 많은 활동들을 선택할 수 있다. 왜냐하면 제일 먼저 끝나는 활동을 선택했을 때, 남은 subproblem에서 최대한 많은 활동을 고를 수 있기 때문이다.

 

 

 

Greedy 알고리즘으로 풀 수 있는 문제는 Dynamic Programming으로 풀 수 있지만, Dynamic Programming으로 풀 수 있는 문제는 Greedy 알고리즘으로 풀 수 없다. 그 이유를 서술하시오. 

 

Greedy 알고리즘은 각 단계에서 지금 당장 가장 이익이 큰 선택을 하는 것으로 문제를 해결합니다. 이 선택은 지역적으로는 최적일 수 있지만, 전역적으로는 항상 최적해를 보장하지는 않는다. 반면 Dynamic Programming은 작은 부분 문제들을 해결하고, 이를 조합하여 전체 문제의 최적해를 구하는 방식이다. Dynamic Programming으로 풀 수 있는 문제는 Optimal Substructure와 Overlapping Subproblems를 가지므로, 부분 문제의 해를 조합하여 전체 문제의 최적해를 구할 수 있다. 이러한 특징 때문에 Greedy 알고리즘으로는 해결할 수 없는 문제를 Dynamic Programming으로 효과적으로 해결할 수 있다.

 

따라서, Greedy 알고리즘이 항상 최적해를 보장하지 않고, Dynamic Programming은 최적 부분 구조와 중복 부분 문제를 가지는 문제에 적용할 수 있기 때문에, Dynamic Programming으로 풀 수 있는 문제를 Greedy 알고리즘으로 해결할 수 없는 경우가 많다.