About dynamic programming
예시) Fibonacci number
일반적으로 F(5)를 찾는다고 하면 recursive하게 구하는 것이 보통 f(n) = f(n-1) + f(n-2)
F(5)를 찾기 위해서는, F2만 해도 3번 재호출되고 뭐 그런건데, O(n^2)
만약 F(2) 값을 저장해놓는다면, 계산을 많이 아낄 수 있음. DP 기술을 활용하면 시간복잡도가 훨씬 떨어진다
Sub-Problem으로 나누었을 때 각 요소가 중첩되어 존재. (f(n)이 이쪽 저쪽 subproblem에서 같이 호출됨 → overlapping, D & CQ와 차이)
Matrix chain multiplication 보충 설명
https://www.youtube.com/watch?v=n_3E2-UhLeU
행렬A가 p x q 사이즈고, 행렬 B가 q x r 사이즈면, 결과 행렬 C는 p x r 이됨
- C_ij = ∑(k=1 to q) a_ik * b_kj // 대충 쓰면 아래와 같은 구조
void product(int A[][], int B[][], int C[][]){ for (int i = 0; i < p; i++){ for (int j = 0; j < r; j++){ C[i][j] = 0; for (int k = 0; k < q; k++) C[i][j] += A[i][k] * B[k][j]; } } }이 때 곱셈연산의 개수는 i,j,k loop를 다 돌아야 되니까, pqr임
다시 말해서, p x q이랑 q x r 행렬 내적하는데 필요한건 pqr이라는 것
- 행렬의 교환법칙 성립하는가? 안된다. AB ≠ BA (심지어 벡터 사이즈에 따라 정의되지 않을 수도 있음)
- 그러나 결합법칙은 성립한다. (AB)C = A(BC)
[예시]
자 그럼 이 때, 행렬 A가 10x100, 행렬 B는 100x5, 행렬 C는 5x50 이라고 해보자.
ABC는 결합법칙으로 인해, 두 가지 방법으로 계산할 수 있다. ①(AB)C or ②A(BC)
①의 첫번째 연산
연산횟수 = 10x100x5 (5,000) / 사이즈 = 10x5
①의 두번째 연산
- 연산횟수 = 10x5x50 (2,500) / 사이즈 = 10 x 50
→ total 7,500의 Multiplication 필요
②의 첫번째 연산
연산횟수 = 100x5x50 (25,000) / 사이즈 = 100x50
②의 두번째 연산
- 연산횟수 = 10x100x50 (50,000) / 사이즈 = 10 x 50
→ total 75,000의 Multiplication 필요
결과적으로 ①(AB)C의 형태로 하는 것이 좋다. 어떤 순서로 곱해야 연산량이 최소가 될까?
n개의 행렬의 곱 A1A2A3…An을 계산하는 최적의 순서는? (이 때, A_i = p_k-1 x p_k 라고 가정 → 인접한 행렬은 Multiplication 가능)
먼저 DP로 접근하니, Subproblem의 최적해를 통해 전체 최적해를 구할 수 있는 구조(Optimal Structure)인지 접근해보자
교환법칙은 안되니 순서가 바뀌진 않고, 아래와 같이 영역으로 짤라서 구분할 수 있다.
아래와 같이 recursive한 형태로 표현 가능
- 어쨋든 임의의 구간에서 최적해가 있는 것인데, 그 구간을 k라고 하자
- AiAi+1…Aj 까지의 행렬에서, m[i,j] = m[i,k] + m[k+1,j] 형태인데, 곱셈 cost를 더해야함. pqr 형태이므로 p(i-1)*p(k)*p(j)
- 근데 k는 모르니까, 순환식으로 다 계산해야됨
- 순환식은 항상 base case가 필요함, k를 구하는 m[i,j]에서 k는 결국 계속 움직이게 되니까 i=j가 되는 지점이 생김. base는 그 때고 0이죠(곱 0번)
순환식 세웠으면 거의 다 된거임. 이제 memorization이나 bottom-up 방식으로 procedure를 설계하면 됨
- i < j만 보면되니, 회색 부분은 다 버리면 되고
- 우리가 원하는 최종 해는 무엇인가? m[i, n]일 것이다. 따라서 최우측 최상단 값을 알고 싶은 것
- bottom-up: 오른쪽 항이 왼쪽 항보다 먼저 계산되는 순서 →그림의 화살표 방향 (행단위 좌에서 우로, 열단위 하에서 상으로, 좌하단 방향 대각선)
int matrixChain(int n) { // i=j인 case, table의 대각선 방향은 다 0으로 채운다 for (int i = 1; i <= n; i++){ m[i][i] = 0; } // 좌하단 방향 대각선으로 해결하는 형태 for (int r = 1; r <= n-1; r++) // 대각선 한 줄 채웠으니, for문은 n-1회 하면됨. 테이블에서 맨 윗줄 8까지지만, 7번만 더 채운다고 { for (int i = 1; i <= n - r; i++) // r이 늘어날 수록, 채워야되는 칸은 적어지는 것 반영한 { int j = i + r; // m[i,j] format에서, 행 인덱스를 i라고 할 때, 열 index는 i+r이다. 대각선 방향으로 진행되는 걸 고려하면 m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]; for (int k = i + 1; k <= j-1; k++) { if (m[i][j] > m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]) m[i][j] = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; } } } return m[1][n]; // 우리의 최종 goal }
- 이런 형태로 programming을 할 수 있고, 시간복잡도는 Θ(n^3)
- 계산해서 풀 때는 k=1,2,3… 거리별 케이스 다 비교하면서 결국 계산해야되는 듯? 다만 이미 계산된 값을 활용할 수 있다 정도
예시 LCS: Longest Common Sequence
LCS 보충설명
L[i][j] 점화식
첫번째 문자열의 1~i번째까지 문자 까지,
두번째 문자열의 1~j번째까지 문자 비교할 때, 공통 부분 문자열의 최대 길이를 L이라고 할 때 점화식은 아래와 같다.
점화식만 보면 복잡한데, Table로 그려서 찾을 수 있다.
x 문자열 = A B C B D A B라고 하고, y문자열 = B D C A B A 라고 할 때 L을 구해보자.
아래와 같이 테이블을 그린다. 첫 행과 첫 열은 별도로 추가하고 0으로 padding한다.
이제 행 단위로 오른쪽으로 순차로 값을 채워가는데, 채우는 기준은 아래와 같다.
- 다른 문자를 만난 일반 경우 : 왼쪽 칸과 위에 칸 중에서 큰 수를 취한다.
- 같은 문자를 만난 경우 : 좌상단 대각선 값에 ++을 취해준다.
여기서 최우측최하단 값이 Longest length이다.
Sequence를 찾으려면 역추적을 해야되는데 아래와 같은 조건으로 따라간다
- 다른 문자를 만난 일반 경우 : 좌측 칸과 위쪽 칸 중에 큰 쪽으로 간다.
- 만약 같은 값이 있다면 취사선택하면 되는데, 그럼 Sequence 경우의 수가 늘어난다는 뜻이다.
- 같은 문자를 만난 경우 : 좌측 상단 대각선 방향으로 이동한다.
첫 열에 다다르면 끝나는데, 그 때 대각선으로 떨어지는 문자들을 모아본다.
- 이렇게 가장 긴 Common Sequence를 구할 수 있다.
// pseudo code function LCS(x[1,.m], y[1,.n]): // 2차원 배열 L[m+1][n+1] 초기화 declare int L[0..m][0..n] // Step 1: LCS Table 채우기 for i from 0 to m: for j from 0 to n: if i == 0 or j == 0: // 첫번째 행,열 0 padding L[i][j] = 0 else if x[i-1] == y[j-1]: // 문자열이 같으면 이전 대각선 값에 ++ L[i][j] = L[i-1][j-1] + 1; else: // 다르면 좌측이나 상단 중 같은 값 선택 L[i][j] = max(L[i-1][j], L[i][j-1]) // Step 3: LCS 역추적 ...
아마 이미 Libarary에서 제공하는 것도 많을거고.
메모리에 저장한 값을 재사용함으로써 직접적인 연산량은 줄어들었는데 cost는 Memory 사이즈
추가
