[공부][알고리즘] 다이내믹 프로그래밍(Dynamic Programing)과 행렬 연쇄 곱셈(Matrix-Chain Multiplication)

1. 다이내믹 프로그래밍(DP)이란 무엇인가?

알고리즘을 설계할 때 가장 경계해야 할 것 중 하나는 '똑같은 연산을 반복하는 것'이다.

 

다이내믹 프로그래밍은 공간을 투자해 속도를 얻는(Trade space for speed) 최적화 기법이다.

즉, 하위 문제들의 해답을 매번 다시 계산하지 않고 메모리에 저장해 두었다가 재사용하는 전략이다.

 

📌 DP의 핵심 작동 원리

1. 하위 문제(Subproblem)의 해답을 찾으면, 이를 장부(Dictionary 또는 Array, 예: soln)에 기록한다.
2. 새로운 하위 문제에 직면했을 때, 재귀 호출을 하기 전 먼저 기록 장부(soln)를 확인한다.
3. 이미 계산된 결과가 있다면 재귀 호출을 과감히 생략하고 저장된 값을 꺼내 쓴다.
4. 결과가 없을 때만 재귀 호출을 수행하고, 리턴하기 직전에 결과를 장부에 업데이트한다.

 

1-1. 피보나치 수열로 보는 하향식(Top-Down) DP 의사코드

아래 코드는 장부(soln)가 채워져 있는지 매번 검사하며

위에서부터 아래로 내려가는 하향식(메모이제이션) 방식의 정석을 보여준다.

fibDPwrap(n) {
    Dict soln = create(n); // 메모이제이션을 위한 장부 생성
    return fibDP(soln, n);
}

fibDP(soln, k) {
    int fib, f1, f2;
    if (k < 2) fib = k;
    else {
        // k-1이 장부에 없다면 재귀 호출, 있다면 기존 값 조회
        if (member(soln, k-1) == false) f1 = fibDP(soln, k-1);
        else f1 = retrieve(soln, k-1);
        
        // k-2가 장부에 없다면 재귀 호출, 있다면 기존 값 조회
        if (member(soln, k-2) == false) f2 = fibDP(soln, k-2);
        else f2 = retrieve(soln, k-2);
        
        fib = f1 + f2;
    }
    store(soln, k, fib); // 구한 값을 장부에 저장
    return fib;
}

---

2. 행렬 연쇄 곱셈(Matrix-Chain Multiplication) 문제

행렬 연쇄 곱셈 문제는 크기가 다른 여러 행렬을 연속으로 곱할 때,

곱하는 '순서'(결합법칙)에 따라 전체 스칼라 곱셈 연산 횟수가 극적으로 달라지는 현상을 최적화하는 문제다.

 

두 행렬 A (크기 p X q)와 B (크기 q X r)를 곱할 때 필요한 스칼라 곱셈 횟수는 p X q X r 번이다.

행렬 여러 개를 곱할 때 순서에 따라 연산량이 어떻게 바뀌는지 구체적인 예시로 확인해 본다.

2-1. 결합 순서에 따른 연산 횟수 비교

주어진 행렬의 크기가 다음과 같다고 가정한다.

• A1: 30 X 1
• A2: 1 X 40
• A3: 40 X 10
• A4: 10 X 25

괄호 묶기 방식 (연산 순서)	스칼라 곱셈 연산 과정	총 연산 횟수
((A₁A₂)A₃)A₄	(30 x 1 x 40) + (30 x 40 x 10) + (30 x 10 x 25)	20,700번
A₁(A₂(A₃A₄))	(40 x 10 x 25) + (1 x 40 x 25) + (30 x 1 x 25)	11,750번
(A₁A₂)(A₃A₄)	(30 x 1 x 40) + (40 x 10 x 25) + (30 x 40 x 25)	41,200번
A₁((A₂A₃)A₄) ★ 최적안	(1 x 40 x 10) + (1 x 10 x 25) + (30 x 1 x 25)	1,400번

순서를 잘못 고르면 41,200번 연산해야 하지만

최적의 순서를 찾으면 단 1,400번으로 연산량이 약 30분의 1로 줄어든다.

 

행렬의 개수가 많아질수록 이 차이는 기하급수적으로 벌어진다.

---

3. DP로 행렬 연쇄 곱셈 해결하기 (4단계 개발 프로세스)

다이내믹 프로그래밍의 정석인 4단계 흐름을 이 문제에 그대로 대입해 설계해 본다.

1단계: 최적해의 구조적 특징 정의하기

행렬 A_i부터 A_j까지의 곱을 구하려 할 때, 최적의 순서는 결국 어느 한 지점 k (i <= k < j)에서 두 덩어리로 쪼개질 것이다.

즉, (A_i ... A_k) 부분과 (A_k+1 ... A_j) 부분으로 나뉜다.

전체 비용이 최소가 되려면 분할된 두 부분 문제 역시 각각 최적의 상태여야 한다.

2단계: 최적해의 값을 점화식으로 재귀적 정의하기

m[i, j]를 행렬 A_i부터 A_j까지 곱하는 데 드는 최소 스칼라 곱셈 횟수라고 정의한다. 행렬 A_i의 크기는 p_i-1 x p_i 이다.

• i = j 인 경우 (행렬이 1개일 때 연산 불필요): m[i, j] = 0
• i < j 인 경우 (행렬이 2개 이상일 때 최솟값 찾기): m[i, j] = min( m[i, k] + m[k+1, j] + (p_i-1 * p_k * p_j) )

이때 최소 비용을 만드는 최적의 분할 지점 k의 값을 나중에 추적하기 위해 s[i, j] 테이블에 함께 기록해 둔다.

3단계: 상향식(Bottom-Up)으로 최적 비용 계산하기

이 문제를 단순 재귀로 풀면 중복 계산이 너무 많아진다.

따라서 길이가 작은 하위 문제(행렬 2개 짜리 곱셈)부터 시작하여 점진적으로 큰 문제의 정답을 채워나가는 타뷸레이션(Tabulation, 상향식) 방식을 채택한다.

연산을 마치고 나면 최소 비용이 담긴 m 테이블과 분할 지점이 담긴 s 테이블이 완성된다.

4단계: 계산된 정보로 최적의 괄호 구조 출력하기

마지막으로 완성된 s[i, j] 테이블을 바탕으로 재귀적 함수를 호출해 실제 괄호가 묶인 형태를 화면에 깔끔하게 출력한다.

PRINT-OPTIMAL-PARENS(s, i, j) {
    if (i == j) {
        print "A" + i;
    } else {
        print "(";
        PRINT-OPTIMAL-PARENS(s, i, s[i, j]);      // 왼쪽 덩어리 추적
        PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j);  // 오른쪽 덩어리 추적
        print ")";
    }
}

---

마무리

다이내믹 프로그래밍의 핵심은 언제나 하나다.

"큰 문제를 작은 문제로 쪼개고, 한 번 구한 답은 절대 두 번 계산하지 않는다"

 

오늘 다룬 행렬 연쇄 곱셈 문제는 DP의 기본 조건인 '최적 부분 구조'와 '부분 문제 반복'을 시각적으로 가장 잘 보여주는 예제다.