알고리즘 11강 (동적 프로그래밍)

학습개요

1. 이번 시간에는 대표적인 알고리즘 설계기법 중 하나인 동적 프로그래밍 방법의 개념과 이를 적용한 알고리즘에 대해서 살펴본다. 우선 동적 프로그래밍 방법의 개념을 학습한 후, 이를 적용한 행렬의 연쇄적 곱셈 문제와 최장 공통 부분 수열 문제에 대해서 학습한다.

 학습목표

1. 동적 프로그래밍 방법의 개념, 특징 및 적용 단계를 이해할 수 있다.
2. 행렬의 연쇄적 곱셈 문제의 개념, 동작, 그리고 특징을 이해할 수 있다.
3. 최장 공통 부분 수열 문제의 개념, 동작, 그리고 특징을 이해할 수 있다.

 주요용어

1. 최적성의 원리(principle of optimality)
   - 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다는 원리
2. 점화식(recurrence relation)
   - 어떤 하나의 값이 자신을 포함한 수식으로 표현되는 식
3. 피보나치 수열(Fibonacci sequence)
   - 첫 번째 항과 두 번째 항이 1이며 그 뒤의 항은 바로 앞 두 항의 합으로 이루어지는 수열
4. 행렬의 연쇄적 곱셈
   - n개의 행렬을 연속적으로 곱할 때 최소의 기본 곱셈 횟수를 가진 행렬의 곱셈 순서를 구하는 문제
5. 최장 공통 부분 수열(LCS, Longest Common Subsequence)
   - 두 스트링의 공통된 부분 수열 중에서 가장 긴 수열
   - 부분 수열 → 스트링에서 연속일 필요는 없지만 순서는 유지되는 스트링의 일부분

정리하기

1. 기본 개념
    ⦁ 동적 프로그래밍 → 문제의 크기가 작은 소문제에 대한 해를 테이블에 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법
   - 분할정복 방법과 달리 소문제들은 서로 독립일 필요가 없음
   - 최적화 문제(최솟값 또는 최댓값을 구하는 문제)에 주로 사용
   - 최적성의 원리(“주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다”)가 반드시 만족되어야만 적용 가능
    ⦁ 처리 과정
   ① 문제의 특성을 분석하여 최적성의 원리가 성립되는지 확인
   ② 주어진 문제에 대해서 최적해를 제공하는 점화식 도출
   ③ 가장 작은 소문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장
   ④ 테이블에 저장된 해를 이용하여 점차적으로 입력 크기가 보다 큰 문제의 해를 구해 나감
    ⦁ 피보나치 수열
   - 점화식 → f(n) = f(n-1) + f(n-2) n>=2, f(1)=1, f(0)=0
   - 피보나치 수열에서 소문제는 독립이 아니므로 분할정복 방법을 적용하면 중복된 계산으로 인해 비효율적
2. 행렬의 연쇄적 곱셈
    ⦁ n개의 행렬을 연쇄적으로 곱할 때 기본 곱셈 횟수(“행렬 원소끼리의 곱셈 횟수”)가 최소가 되는 행렬의 곱셈 순서를 구하는 문제
   - i×j 행렬과 j×k 행렬을 곱하는 경우 → i×j×k번의 곱셈이 필요하며, 결과 행렬의 크기는 i×k 
    ⦁ 점화식 → C(i,j)=min i<=k< j { C(i,k)+C(k+1,j)+di-1dkdj } (i<j)
   - C(i,j) → Mi×Mi+1×…×Mj-1×Mj를 수행하는 데 필요한 기본 곱셈의 최소 횟수 → 이때 행렬 Mi의 크기는 di-1×di 차원
   - 최적해 → C(1,n) → s=j-i를 0부터 n-1까지 증가시키면서 계산
    ⦁ 성능 → O(n3)
    ⦁ 최적의 곱셈 순서는 별도의 테이블 P(i,j) 활용 → C(i,j)를 계산할 때 찾은 분리 위치 k를 P(i,j)에 저장 → P(i,j)=k의 의미는 (MiMi+1…Mk)(Mk+1…Mj)
3. 최장 공통 부분 수열
    ⦁ 최장 공통 부분 수열(LCS) → 두 스트링의 공통된 부분 수열 중 가장 긴 수열
   - 부분 수열 → 스트링에서 연속일 필요는 없지만 순서는 유지되는 스트링의 일부분
    ⦁ 점화식 → LCS(i,j) =[ ① i=0 또는 j=0인 경우 ε (빈 스트링),
            ② 마지막 문자가 같은 경우 LCS(i-1,j-1) | 마지막 문자,
            ③ 마지막 문자가 다른 경우 max{LCS(i,j-1), LCS(i-1,j)} ]
   - 최적해 → LCS(n,m) → LCS(i,j)를 i와 j가 작은 값에서부터 큰 값의 순으로 계산
    ⦁ 시간 복잡도 → O(nm) (n=|X|, m=|Y|)
   - 두 스트링의 LCS 길이를 구하는 알고리즘 → O(nm)
   - 앞서 구한 테이블 LCS[][]로부터 LCS 자체를 구하는 알고리즘 → O(n+m)