다이나믹 프로그래밍 개념부터 활용까지 완벽 정리 - 메모이제이션, 반복문, C, Java, Python 예시코드

다이나믹 프로그래밍(Dynamic Programming, DP)

 

 다이나믹 프로그래밍(Dynamic Programming, DP)은 알고리즘 문제 풀이에서 매우 중요한 기법입니다. 많은 사람들이 처음에는 어려워하지만, 원리를 이해하면 복잡한 문제도 효율적으로 해결할 수 있습니다. 이번 글에서는 다이나믹 프로그래밍의 개념, 원리, 시간복잡도, 구현 방법(메모이제이션과 반복문 방식), 장단점, 대표적인 코딩테스트 문제, 그리고 C, Java, Python 예제 코드를 소개하겠습니다.

---

1. 다이나믹 프로그래밍의 개념

다이나믹 프로그래밍은 문제를 작은 하위 문제로 나누고, 이를 해결한 결과를 저장해두었다가 나중에 재사용하는 알고리즘 기법입니다. Overlapping Subproblems(중복되는 부분 문제)와 Optimal Substructure(최적 부분 구조)라는 두 가지 속성을 가진 문제에서 주로 사용됩니다.

적용 가능한 문제의 특징

1. 중복되는 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 여러 번 반복해서 나타남.
2. 최적 부분 구조(Optimal Substructure): 하위 문제의 최적해를 결합하여 전체 문제의 최적해를 구할 수 있음.

---

 

반응형

2. 다이나믹 프로그래밍의 원리

(1) 메모이제이션 (Memoization)

• Top-Down 방식으로, 재귀 호출을 통해 계산된 결과를 저장하여 동일한 계산을 반복하지 않도록 합니다.
• 계산이 필요할 때만 값을 구하며, 이미 계산된 값은 배열이나 맵에 저장하여 빠르게 접근합니다.

(2) 테이블 방식 (Tabulation)

• Bottom-Up 방식으로, 작은 하위 문제부터 해결해 나가면서 결과를 테이블에 저장합니다.
• 반복문을 사용하여 모든 하위 문제를 순차적으로 해결하며, 재귀 호출을 사용하지 않습니다.

(3) 메모이제이션 방식과 반복문 방식 비교

특징	메모이제이션 방식	테이블 방식
접근 방식	재귀 호출 기반 (Top-Down)	반복문 기반 (Bottom-Up)
메모리 사용량	호출 스택 추가 사용	테이블만 사용
직관성	수학적 점화식 구현에 적합	구현이 상대적으로 단순함
성능	동일	동일

---

 

3. 다이나믹 프로그래밍의 시간복잡도

• 일반적으로 다이나믹 프로그래밍의 시간복잡도는 테이블의 크기에 따라 결정됩니다.
• 하위 문제의 개수 × 각 하위 문제를 해결하는 데 걸리는 시간.
• 예를 들어, 피보나치 수열 문제에서는 O(n), 배낭 문제에서는 O(nW) (n: 아이템 수, W: 배낭의 용량)입니다.

---

 

4. 다이나믹 프로그래밍 구현 방법

1. 문제를 작은 부분 문제로 나누기

• 문제를 정의하고, 이를 해결하기 위한 상태(State)를 설계합니다.

2. 점화식(Recurrence Relation) 작성

• 현재 상태를 이전 상태와 연결하는 관계를 수식으로 나타냅니다.

3. 초기 조건 정의

• 가장 작은 하위 문제의 값을 설정합니다.

4. 메모이제이션 또는 테이블 작성

• 결과를 저장할 공간을 할당하고, 알고리즘을 구현합니다.

---

 

5. 다이나믹 프로그래밍 예제 코드

예제 문제: 피보나치 수열

문제 정의: n번째 피보나치 수를 구하라.

 

1) 메모이제이션 방식

Python 코드

def fibonacci_memo(n, memo):
    if n <= 1:
        return n
    if memo[n] is None:
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

n = 10
memo = [None] * (n + 1)
print("Fibonacci (Memoization):", fibonacci_memo(n, memo))

 

C 코드

#include <stdio.h>

int memo[100] = {0};

int fibonacci_memo(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);
    return memo[n];
}

int main() {
    int n = 10;
    printf("Fibonacci (Memoization): %d\n", fibonacci_memo(n));
    return 0;
}

 

Java 코드

import java.util.Arrays;

public class FibonacciMemo {
    public static int fibonacci(int n, int[] memo) {
        if (n <= 1) return n;
        if (memo[n] == 0) {
            memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
        }
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10;
        int[] memo = new int[n + 1];
        System.out.println("Fibonacci (Memoization): " + fibonacci(n, memo));
    }
}

 

 

2) 반복문 방식

Python 코드:

def fibonacci_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

n = 10
print("Fibonacci (Tabulation):", fibonacci_tab(n))

 

C 코드:

#include <stdio.h>

int fibonacci_tab(int n) {
    if (n <= 1) return n;
    int dp[100] = {0};
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n = 10;
    printf("Fibonacci (Tabulation): %d\n", fibonacci_tab(n));
    return 0;
}

 

Java 코드:

public class FibonacciTab {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci (Tabulation): " + fibonacci(n));
    }
}

---

 

 

다이나믹 프로그래밍은 알고리즘의 핵심 기법 중 하나로, 다양한 구현 방법이 있습니다. 메모이제이션과 반복문 방식을 모두 익히고 문제의 성격에 따라 적합한 방법을 선택하는게 좋습니다.

 

 

같이 보면 좋은 글

메모이제이션을 완전탐색 알고리즘에 적용하면 실행시간을 매우 단축시킬 수 있습니다. 자세한 내용은 아래 글들을 참고해주세요.

2024.12.21 - [알고리즘] - 메모이제이션(Memoization) 적용을 통한 성능 개선 (1) - 브루트포스

메모이제이션(Memoization) 적용을 통한 성능 개선 (1) - 브루트포스

2024.12.21 - [알고리즘] - 메모이제이션(Memoization) 적용을 통한 성능 개선 (2) - 백트래킹

메모이제이션(Memoization) 적용을 통한 성능 개선 (2) - 백트래킹

2024.12.21 - [알고리즘] - 메모이제이션을 통한 성능개선 (3) - DFS

메모이제이션을 통한 성능개선 (3) - DFS