Dynamic Programming (동적 계획법)

문제 해결 방법의 종류

• brute-force approach : 모든 경우에 대해서 다 계산하고 가장 좋은것을 택하는 방법. n이 커지면 너무 오래걸려 실행 불가능하다. 
• divide and conquer approach
• dynamic programming approach
• greedy approach

 

Dynamic Programming(DP)

• 주어진 문제를 하위문제로 나누어서 해결한다. 
• 하위 문제가 서로 연관이 있을 때 사용 (divide and conquer은 서로 연관이 없을 때 사용)
• optimization problem(최적해를 구할 때) 를 풀 때 사용 (최적화문제 : 답이 여러개인 문제에서 가장 좋은 답을 찾는 문제 ex. 최단경로 문제)
• 모든 하위 문제를 풀고 그 결과를 저장해두어 그 결과를 다음 단계의 문제를 풀 때 사용한다. (bottom-up 방식) 

Dynamic Programming vs Divide-and-Conquer

• divide and conquer은 하위문제를 계속 계산해야해서 서로 연관이 있는 문제를 풀 때 비효율적이다. 
• dynamic programming은 각각의 하위 문제를 풀고 저장해두고 나중 문제에 사용한다. 즉 연관이 있는 문제에 효율적이다. ex. 피보나치 수열을 DP로 풀면 선형시간내에 풀 수 있다. 

 

 

Dynamic Programming를 푸는 방법

1. 최적해에 대한 구조적 특징 파악 (optimal substructure)
2. 최적해의 값을 재귀적으로 정의한다. 
3. 하위문제로부터 최적해를 계산한다. 
4. 최적해 방법을 구축한다.

 

 

Assembly line scheduling

제품을 조립하여 완성하는 과정.

다음과 같은 assembly line 이 주어졌을 때 어떤 방법으로 해야 가장 단시간에 물건이 조립되는가?

• n stations: Si
• i번째 sation에서의 조립 시간 : aj
• entry time : e
• exit time : x

만약 이 문제를 brute force로 푼다면? 2^n번의 경우의 수가 나온다. n이 커진다면 풀기 불가능

-> Dynamic programming으로 풀자!

 

1. 최적해의 구조적 특징 파악

• S1,4를 구하려면 S1,3 or S2,3을 거쳐가야함. -> Si,j는 S1,j-1 or S2,j-1을 거쳐가야함

2. 재귀적 정의가 가능한지 확인

• f* : 모든 station에 도달하는 가장 빠른 시간
• fi[j] : Si,j에 도달하는 가장 빠른 시간 (f1[4]는 1번라인 4번째 station에 도달하는 가장 빠른 시간)

3. 최적해를 계산한다. 

시간이 가장 적게 걸리는 최적의 경로를 따라간다. 

최적의 값은 35라는 최종 답이 나온다. 

Runnimg time : O(n)

값 뿐만 아니라 값을 구하기 위해 어떤 경로를 거쳐 왔는지도 알아야한다. 

 

4. 최적해 방법을 구축한다. (최적해 일 때의 경로를 구한다.)

 

 

Coin Collecting Problem by Robot

 

Rod Cutting Problem

 

Matrix-Chain Multiplication

• Matrix A와 B의 곱을 구하는 방법.
• 행렬은 A행과 B행의 숫자가 같아야 곱셈이 가능하다. 
• Matrix 곱셈을 할 때 곱셈 순서에 따라 연산 횟수가 달라진다. 예를들어 A: 10x100, B:100x5, C: 5x50일 때 (AB)C : 7500번, A(BC) : 75000번 이다.
• 이렇게 주어진 matrix 곱셈에 대해 곱셈의 횟수를 최소화하는 순서를 찾는 문제를 Matrix-Chain Multiplication이라고 한다. 

만약 이를 Brute-force approach로 푼다면? n이 커질수록 연산 횟수가 너무 많아져 비효율적이다. 

-> Dynamic programming으로 풀자!

 

1. 최적해의 구조적 특징 파악

Notation : Ai...j =Ai * A(i+1) * ... * Aj 

다음과 같이 부분 행렬 곱셈으로 쪼갤 수 있다. 

 

2. 재귀적 정의가 가능한지 확인

m[i,j] : i번쨰 행렬부터 j번쨰 행렬을 곱할 때 필요한 최소 연산 갯수

p : 행렬의 차원(dimension)

i=j이면 행렬이 1개 뿐이므로 곱셈의 횟수가 0이다. 

j>i이면 행렬을 두 그룹으로 나누어서 생각한다. 즉,

앞쪽 행렬의 최소연산횟수 + 뒷쪽 행렬의 최소 연산 횟수 + 두 행렬을 곱할 때의 연산횟수 = 전체 행렬 최소 연산횟수

이다. 

 

3. 최적해를 계산한다. 

괄호를 넣을 수 있는 위치 k에 대해 i<=k<j 이다. 

다음 표는 예시입니다. 

i   /  j	1	2	3	4	5	6
1	0	15750	7875	9375
2		0	2625	4375	7125
3			0	750	2500
4				0	1000	3500
5					0	5000
6						0

                           <최솟값을 저장>

 

 

4. 최적해 방법을 구축한다. (최적해 일 때의 경로를 구한다.)

	1	2	3	4	5	6
1	-	1	1	3	3	3
2		-	2	3	3	3
3			-	3	3	3
4				-	4	5
5					-	5
6						-

                              <k값을 저장>

 

Runnung time : O(n^3), subproblem : O(n^2)

 

Longest Common Subsequence(LCS problem)

what ia LCS?

• <bcdb>는 <abcbdab>의 subsequence이다. 
• <bca>는 <abcbdab>와 <bdcaba>의 common subsequence이다. 
• Longest common subsequence? common subsequence들 중 가장 긴것. 
• <bcba>는 <abcbdab>와 <bdcaba>의 LCS이다. 

만약 이를 Brute-force approach로 푼다면? n이 커질수록 연산 횟수가 너무 많아져 비효율적이다.

-> Dynamic programming으로 풀자!

 

1. optimal substructure

x=<x1,x2,...,xi>, yj=<y1,y2,...yj>, LCS z에 대해서 마지막 부분에 대응하는 값을 떼고 생각할 수 있다. 이런식으로 작은 문제로 쪼갤 수 있다.

 

2. recursive

LCS

x1

x2

...

xi-1

xi

y1

y2

y3

...

yj-1

yj

 

case1. xi=yi 이므로 그 이전 문자들의 LCS에 마지막 문자의 길이 1을 더해준다. 

case2. xi와 yi 가 다르면 xi 와 yj 모두가 LCS에 들어갈 수 없다. 즉 둘중 하나는 버려야하므로 각각을 버릴때 경우에서 큰 값을 택한다. 

 

3. 최적해를 계산한다. 

X / Y	0	B	D	C	A	B
0	0	0	0	0	0	0
A	0	0	0	0	1	1
B	0	1	1	1	1	2
C	0	1	1	2	2	2
B	0	1	1	2	2	3
D	0	1	2	2	2	3
A	0	1	2	2	3	LCS(6,5) = 3

점화식대로 문자가 같을때와 다를때로 나누어서 값을 채워넣는다. 

 

4. 최적해 방법을 구축한다. (최적해 일 때의 경로를 구한다.)

X / Y	0	B	D	C	A	B
0	0	0	0	0	0	0
A	0	0	0	0	1	1
B	0	1	1	1	1	2
C	0	1	1	2	2	2
B	0	1  ↖	1	2	2	3
D	0	1	2  ↖	2  ←	2	3
A	0	1	2	2	3  ↖	LCS(6,5) = 3  ←

 

Running time : O(mn)

 

 

LCS 문제 코딩하기

2020/12/20 - [알고리즘] - [동적계획법/Dynamic Programming]LCS 문제(최장 공통 부분 수열) 파이썬 코드