방송대/알고리즘

11강. 동적 프로그래밍

monimoni 2025. 5. 16. 20:57

1. 동적 프로그래밍

  • 문제의 크기가 작은 소문제에 대한 해를 테이블에 저장해 놓고, 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법
    • 각 소문제는 원래 주어진 문제와 동일한 문제 ➝ 입력 크기만 작아진 문제
    • 소문제들은 서로 독립일 필요는 없음
    • 동적 “프로그래밍” ➝ “동적 계획법”
      • 컴퓨터 프로그램과는 무관, 해를 구축하는 데 테이블을 이용한다는 의미
    • 최소값 / 최댓값을 구하는 최적화 문제에 주로 사용
      • "최적성의 원리 ( principle of optimality )"를 반드시 만족하는 문제에만 적용 가능
  • 최적성의 원리란?
    • 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성
  • 동적 프로그래밍 방법의 처리 과정
    • (0) 최적성의 원리가 주어진 문제에 성립하는 지 확인
    • (1) 주어진 문제에 대해서 최적해를 제공하는 점화식 도출
    • (2) 가장 작은 소문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장
    • (3) 테이블에 저장된 소문제의 해를 이용하여 점차적으로 입력의 크기가 큰 상위 문제의 해를 구해 나감

2. 피보나치 수열

  • 정의
    • f(n) = f(n-1) + f(n-2) (n ≥ 2)
    • f(n) = 1 (n = 1)
    • f(n) = 0 (n = 0)
  • 알고리즘
Fibo(n) {
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    return f[n];
}
  • 성능 : O(n)

3. 분할정복 방법을 적용한 피보나치 수열

f(n) {
    if (n <= 0) return (0);
    if (n == 1) return (1);
    else return( f(n-1) + f(n-2) );
}
  • 소문제가 독립이 아니므로 중복된 계산이 필요 ➝ 매우 비효율적
    • 그렇기에 동적 프로그래밍 방법을 적용해야 함

4. 행렬의 연쇄적 곱셈

  • n개의 행렬 (M₁, M₂, ⋯, Mₙ)을 연쇄적으로 곱하는 경우
    • 결합법칙 성립
      • M₁ · M₂ · M₃ ➝ ((M₁ · M₂) · M₃) = (M₁ · (M₂ · M₃))
      • 여러 가지 다른 곱셈 순서가 존재 ➝ 곱셈의 횟수가 달라짐
  • 행렬의 연쇄적 곱셈 문제란?
    • n개의 행렬을 연쇄적으로 곱할 때 최소의 기본 곱셈 횟수를 갖는 행렬의 곱셈 순서를 구하는 문제
      • 기본 곱셈 횟수를 최소화할 수 있는 방법을 찾는 것
  • 기본 곱셈
    • 행렬 원소끼리의 곱셈
      • Mᵢ : m×n
      • Mⱼ : n×r
      • Mᵢ × Mⱼ → 결과: m×r
      • 기본 곱셈 횟수 = m × n × r

5. 최적성의 원리

  • n개의 행렬을 곱하는 최적의 순서는 n개 행렬의 연쇄적 곱셈 중 일부 부분에서도 최적의 곱셈 순서를 포함함
  • 예시
    • 7개 행렬을 곱하는 최적의 순서 : (M₁M₂)((((M₃M₄)M₅)M₆)M₇)
    • 그 중 일부인 M₃, M₄, M₅를 곱하는 최적의 순서 : ((M₃M₄)M₅)
  • 부분 문제들의 최적해로 n개 행렬을 곱하는 최적의 순서를 구할 수 있음
  • → 최적성의 원리 성립
  • → 동적 프로그래밍 방법으로 해결 가능

6. 연쇄 행렬 곱셈 문제의 점화식

  • n개의 행렬 Mᵢ ( dᵢ₋₁ × dᵢ 차원 ) ( 1 ≤ i ≤ n )
    • M₁ × M₂ × M₃ × ... × Mₙ₋₁ × Mₙ d₀×d₁ d₁×d₂ d₂×d₃ dₙ₋₁×dₙ
    • 최적해를 저장하는 테이블 : C(i, j) ( 1 ≤ i ≤ j ≤ n )
      • Mᵢ × Mᵢ₊₁ × ... × Mⱼ 을 수행하는 데 필요한 기본 곱셈의 최소 횟수
      • 최종 목표 : C(1, n) = ?
      • 초기 조건: C(i, i) = 0
      • C(i, j) = minᵢ≤k<j { C(i, k) + C(k+1, j) + dᵢ₋₁ * dₖ * dⱼ } ( i < j )
        • dᵢ₋₁ * dₖ * dⱼ( 결합 비용 )은 Mᵢ~Mₖ과 Mₖ₊₁~Mⱼ를 곱할 때의 연산 수
        • C(i, k)는 Mᵢ x … xMₖ
        • C(k+1, j)는 Mₖ₊₁~Mⱼ
      • 가장 적은 비용이 나오는 k를 저장 : P(i, j) = k

7. 행렬의 연쇄적 곱셈 알고리즘

MinMatMult(n, d[ ]) {
    int i, j, k, s;
    int C[n+1][n+1];

    for (i = 1; i <= n; i++) 
        C[i][i] = 0;

    for (s = 1; s <= n - 1; s++) {
        for (i = 1; i <= n - s; i++) {
            j = i + s;
            C[i][j] = minᵢ≤k<j ( C[i][k] + C[k+1][j] + d[i-1] * d[k] * d[j] );
            P[i][j] = 최소값이 되는 k의 값;
        }
    }

    return (C[1][n], P[1..n][1..n]);
}
  • 입력
    • n: 행렬의 개수
    • d[0..n]: 각 행렬의 크기 (i번째 행렬의 크기는 d[i-1] × d[i])
  • 출력
    • C[1][n]: n개의 행렬을 곱하는 데 필요한 기본 곱셈 횟수의 최소값
    • P[1..n][1..n]: 최적의 곱셈 순서를 구할 수 있는 분할 위치 정보 배열

8. 행렬의 연쇄적 곱셈 알고리즘 성능과 특징

  • 시간 복잡도 → O(n³)
  • 최적의 행렬 곱셈 순서를 구하는 알고리즘 → O(n)
    • P[i][j]를 이용할 때마다 나눌 부분이 하나씩 줄어듦
      • n개 행렬의 곱셈 순서에서는 n - 2번의 분할 지점이 필요 → O(n)

9. 최장 공통 부분 수열

  • LCS, Longest Common Subsequence
  • 두 스트링의 공통된 부분 수열 중 가장 긴 수열을 구하는 것
    • 부분 수열 : 문자열( 스트링 )에서 연속일 필요는 없지만, 순서는 유지되는 문자열( 스트링 )의 일부분
      • ex. "KNOU" → 부분 수열 : O, KO, KU, NO, KOU, KNOU …
  • X = x₁x₂⋯xₙ 과 Y = y₁y₂⋯yₘ 사이의 공통 부분 수열 l₁l₂⋯lₛ
    • 1 ≤ k ≤ s 인 모든 lₖ가 스트링 X와 Y에 존재
    • k가 커질수록 X와 Y에 존재하는 위치도 커짐( 뒤쪽에 위치 )

10. LCS에서의 최적성의 원리

  • 두 스트링 X와 Y 사이의 LCS는 이들의 어떤 서브스트링 사이의 LCS를 포함
    • (1) X의 마지막 글자가 Y의 마지막 글자와 같은 경우
      • x₁⋯xₙ₋₁ 과 y₁⋯yₘ₋₁ 의 LCS에 마지막 글자를 추가한 경우
    • (2) X의 마지막 글자가 Y의 마지막 글자와 다르며 LCS에 사용되지 않은 경우
      • x₁⋯xₙ₋₁ 과 y₁⋯yₘ 의 LCS와 동일
    • (3) X의 마지막 글자가 Y의 마지막 글자와 다르며 LCS에 사용된 경우 (이 경우 X의 마지막 글자는 Y의 마지막 글자 이전의 다른 글자와 일치)
      • x₁⋯xₙ 과 y₁⋯yₘ₋₁ 의 LCS와 동일

11. LCS의 점화식

  • 𝑋 = x₁x₂⋯xₙ 과 𝑌 = y₁y₂⋯yₘ 간의 LCS 점화식
    • LCS(i, j) = ε( 빈 스트링 ) ( i = 0 또는 j = 0인 경우 )
    • LCS(i, j) = LCS(i−1, j−1) + xᵢ ( xᵢ = yⱼ 인 경우 )
    • LCS(i, j) = max{ LCS(i, j−1), LCS(i−1, j) } ( xᵢ ≠ yⱼ 인 경우 )
  • 최종목표 : LCS(n, m) = ?

12. LCS 알고리즘 – LCS 길이와 관련 정보

LCS(n, X[ ], m, Y[ ]){
    int LCS[n+1][m+1];   // LCS 길이 테이블
    int i, j;

    LCS[0][0] = 0;

    for (i = 1; i <= n; i++) 
        LCS[i][0] = 0;   // 첫 열의 초기화

    for (j = 1; j <= m; j++) 
        LCS[0][j] = 0;   // 첫 행의 초기화

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (X[i] == Y[j]) 
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else 
                LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);

    return (LCS[n][m], LCS[0..n][0..m]);
}
  • 입력
    • X[1..n], Y[1..m] : 두 문자열
    • n, m: 문자열 길이
  • 출력
    • LCS[n][m]: LCS의 길이
    • LCS[0..n][0..m]: LCS 길이 테이블 전체 ( 문자열 재구성에 사용 가능 )

13. LCS 알고리즘 – LCS 출력

GetLCS(n, X, m, Y, LCS[ ][ ]) {
    int i = n, j = m, idx = LCS[n][m];
    char L[idx + 1];          // LCS를 저장할 배열

    while (idx > 0)           // LCS 길이만큼 공통 문자 찾을 때까지 반복
    {
        if (X[i] == Y[j]) {
            L[idx] = X[i];    // 공통 문자를 LCS로 추가
            idx--; i--; j--;
        }
        else if (LCS[i][j - 1] > LCS[i - 1][j])
            j--;              // LCS[i][j]와 일치하는 큰 값 쪽으로 j를 1 줄임
        else
            i--;              // 또는 i를 1 줄임
    }

    return L[1..LCS[n][m]];
}
  • 입력
    • X[1..n], Y[1..m]: 두 문자열
    • LCS[0..n][0..m]: LCS 길이 테이블
  • 출력
    • L[1..LCS[n][m]]: 최장 공통 부분 수열 (LCS) 문자열

14. LCS 알고리즘 성능 및 특징

  • 길이 n과 m인 두 스트링의 LCS 길이 → O(nm)
    • 각각 길이 n과 m을 사용하는 중첩된 이중 루프
  • 테이블 LCS[ ][ ]로부터 LCS를 구하는 알고리즘 → O(n + m)
    • idx가 LCS 길이만큼 줄어들 때까지 반복하는 형태의 루프로 구성
      • 실제로는 i = n, j = m부터 최대 i = 0, j = 0까지 도달 가능

15. 정리하기

  • 기본 개념
    • 상향식 접근 방법, 소문제는 서로 독립일 필요 없음 (중첩 가능)
    • 최적성의 원리, 적용 단계, 피보나치 수열
  • 행렬의 연쇄적 곱셈
    • n개 행렬의 연쇄적 곱셈에서 최소의 기본 곱셈 횟수를 가진 곱셈 순서를 구하는 문제
    • C(i, j) = minᵢ≤k<j { C(i, k) + C(k+1, j) + dᵢ₋₁ × dₖ × dⱼ } (i < j)
    • 시간 복잡도 : O(n³)
    • 최적의 곱셈 순서는 P(i, j) = k 정보를 활용해서 구함
  • 최장 공통 부분 수열
    • 두 스트링의 공통된 부분 수열 중 가장 긴 수열을 구하는 문제
    • LCS(i, j) = ε( 빈 스트링 ) (i = 0 또는 j = 0인 경우)
    • LCS(i, j) = LCS(i−1, j−1) + xᵢ (xᵢ = yⱼ 인 경우)
    • LCS(i, j) = max{ LCS(i, j−1), LCS(i−1, j) } (xᵢ ≠ yⱼ 인 경우)
    • 시간 복잡도: O(nm) (n = |X|, m = |Y|)
728x90