알고리즘 03 - (기본 패턴 03) 유형 - 3. 피보나치 수열, 동적 프로그래밍(Dynamic Programming)?

5 분 소요

동적 프로그래밍(Dynamic Programming)란?

동적 프로그래밍(DP) 은 큰 문제를 작은 하위 문제로 나누어 해결하며, 중복 계산을 줄이는 최적화 기법입니다.
특히 점화식과 피보나치 수열 같은 문제에 적합한 알고리즘 설계 방식입니다.

“동적”이 의미하는 것

동적 프로그래밍(Dynamic Programming)의 반대말 은 정적 프로그래밍(Static Programming) 이 아닙니다.

동적 프로그래밍에서의 “동적”은 문제를 푸는 방식에서 동적인 변화와 의사결정을 포함한다는 뜻이지, 프로그래밍 언어의 정적/동적 특성과는 무관합니다.

동적 프로그래밍에서 “동적”이라는 말은 다음과 같은 두 가지 특징을 의미합니다:

1. 문제를 나누고 변화하는 방식

큰 문제를 작은 하위 문제로 나누고, 각 하위 문제를 해결한 결과를 사용해 큰 문제를 해결합니다.
예를 들어, 피보나치 수열 계산에서:
- ( F(5) = F(4) + F(3) )
- ( F(4) = F(3) + F(2) )
- 작은 문제를 해결한 결과(( F(3), F(2) ))를 저장해 큰 문제를 해결하는 과정이 “동적”입니다.

2. 최적의 의사결정 과정

동적 프로그래밍은 문제의 각 단계에서 최적의 선택을 반복적으로 수행합니다.
현재 상태에서 필요한 값을 계산하여 다음 상태를 변화시킵니다.
이는 하위 문제의 결과를 기반으로 큰 문제의 결과를 동적으로 결정한다는 뜻입니다.

“동적”이 와닿지 않을 때의 비유

1. 조립식 건물

큰 건물을 짓는다고 생각해 봅시다.
동적 프로그래밍은 작은 벽돌(하위 문제)을 쌓아 큰 건물(최종 문제)을 짓는 과정과 유사합니다.
각 벽돌이 이미 쌓인 상태를 기반으로 다음 벽돌을 쌓으므로, 이전 결과를 동적으로 활용합니다.

2. 도미노 효과

도미노를 하나씩 쓰러뜨리는 과정이라고 생각할 수 있습니다.
첫 도미노가 쓰러지면 그 다음 도미노의 상태를 결정하며, 이는 순차적으로 전체 문제를 해결하는 과정과 유사합니다.

동적 프로그래밍의 본질

동적 프로그래밍은 문제 해결 과정을 동적으로 변화시키며 하위 문제를 이용하는 기법입니다.
“동적”이란 단어는
1. 문제를 쪼개고 중복 계산을 피하기 위해 저장된 값을 재활용하는 과정.
2. 최적의 결과를 도출하기 위해 상태를 점진적으로 갱신하는 과정.
이는 반복적이고 재귀적인 구조를 가진 문제에서 매우 유용하며, 이를 통해 효율적인 계산이 가능해집니다.

1. 동적 프로그래밍의 특징

1.1 Overlapping Subproblems (중복되는 하위 문제)

동적 프로그래밍 문제는 동일한 하위 문제가 여러 번 반복됩니다.
예: 피보나치 수열 계산에서 ( F(n) = F(n-1) + F(n-2) )는 동일한 ( F(n-1), F(n-2) )를 여러 번 계산합니다.

1.2 Optimal Substructure (최적 부분 구조)

문제의 최적 해결 방법은 하위 문제의 최적 해결 방법으로 구성됩니다.
예: 피보나치 수열에서 ( F(n) )는 ( F(n-1) )과 ( F(n-2) )의 합으로 구할 수 있습니다.

1.3 Memoization (메모이제이션)

중복 계산을 방지하기 위해, 하위 문제의 결과를 저장하여 재사용합니다.
재귀 방식과 결합하면 효율적인 계산이 가능합니다.

1.4 Tabulation (테이블 방식)

작은 문제부터 점진적으로 큰 문제를 해결하는 반복적 방식입니다.
계산 결과를 테이블(배열)에 저장하며, 하향식(Top-Down)인 메모이제이션과는 반대로 상향식(Bottom-Up)으로 동작합니다.

2. 피보나치 수열과 동적 프로그래밍

2.1 피보나치 수열의 점화식

[ F(n) = F(n-1) + F(n-2), \quad \text{(n ≥ 2)} ]

초기 조건: ( F(0) = 0, F(1) = 1 ).

2.2 비효율적인 재귀 방식

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

문제점
- 중복 계산이 많아 ( F(n-1) )과 ( F(n-2) )를 반복적으로 호출.
- 시간 복잡도: ( O(2^n) ).

2.3 메모이제이션 (재귀 + 캐싱)

메모이제이션은 이전에 계산한 값을 저장하여 재사용합니다.

def fibonacci_memoization(n, memo={}):
    """
    피보나치 수열의 n번째 값을 계산하는 함수
    - 메모이제이션 기법을 사용하여 중복 계산을 방지
    - 이전에 계산된 값을 memo 딕셔너리에 저장
    """

    # 1. 이미 계산된 값이 memo 딕셔너리에 있는 경우, 저장된 값을 반환
    if n in memo:
        return memo[n]  # 저장된 값을 바로 반환하여 중복 계산을 방지

    # 2. 기저 조건: n이 0 또는 1이면 그 값을 그대로 반환
    #    피보나치 수열의 정의에 따라 F(0) = 0, F(1) = 1
    if n <= 1:
        return n

    # 3. n번째 피보나치 값 계산
    #    F(n) = F(n-1) + F(n-2)
    #    계산된 값을 memo 딕셔너리에 저장
    memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)

    # 4. 계산된 값을 반환
    return memo[n]


# 테스트: 피보나치 수열의 5번째 값을 계산
n = 5
result = fibonacci_memoization(n)  # F(5) = 5
print(f"Fibonacci({n}) = {result}")

장점
- 계산 결과를 저장하므로, 동일한 하위 문제를 다시 계산하지 않음.
- 시간 복잡도: ( O(n) ).

2.4 테이블 방식 (Tabulation)

테이블 방식은 작은 문제부터 차례로 계산하며, 반복문으로 구현합니다.

def fibonacci_tabulation(n):
    """
    피보나치 수열의 n번째 값을 계산하는 함수
    - Tabulation(테이블 방식)을 사용하여 동적 프로그래밍 구현
    - 작은 문제부터 순차적으로 계산하며 결과를 테이블(dp 배열)에 저장
    """

    # 1. 기저 조건: n이 0 또는 1인 경우 해당 값을 바로 반환
    if n <= 1:
        return n

    # 2. 테이블(dp 배열) 초기화
    #    dp[i]는 피보나치 수열의 i번째 값을 저장
    dp = [0] * (n + 1)  # n+1 크기의 배열 생성 (0부터 n까지 포함)
    dp[0], dp[1] = 0, 1  # 초기 조건: F(0) = 0, F(1) = 1

    # 3. 작은 문제부터 순차적으로 계산
    #    F(i) = F(i-1) + F(i-2)
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 점화식을 사용해 dp 배열에 저장

    # 4. 결과 반환: dp[n]에 n번째 피보나치 값이 저장되어 있음
    return dp[n]


# 테스트: 피보나치 수열의 10번째 값을 계산
n = 10
result = fibonacci_tabulation(n)
print(f"Fibonacci({n}) = {result}")

장점
- 하위 문제를 순서대로 해결하므로 재귀 호출이 없어 스택 오버플로우 걱정이 없음.
- 시간 복잡도: ( O(n) ).
- 공간 복잡도: ( O(n) ) (단, 저장 공간을 줄일 수도 있음).

2.5 공간 최적화

피보나치 수열은 두 개의 이전 항만 사용하므로, 배열 대신 변수를 활용하여 공간을 절약할 수 있습니다.

def fibonacci_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

공간 복잡도 ( O(1) ).

3. 예시 문제: 계단 오르기

문제 설명:

한 번에 1칸 또는 2칸씩 계단을 오를 수 있을 때, ( n )개의 계단을 오르는 방법의 수를 구하시오.

점화식 유도:

( f(n) ): ( n )개의 계단을 오르는 방법의 수.
관찰
- 마지막에 1칸을 오른 경우: ( f(n-1) )가지 경우.
- 마지막에 2칸을 오른 경우: ( f(n-2) )가지 경우.
따라서 점화식은: [ f(n) = f(n-1) + f(n-2) ]
초기 조건:
- ( f(0) = 1 ) (0칸은 아무것도 안 하면 1가지 방법).
- ( f(1) = 1 ) (1칸을 한 번에 오르는 방법 1가지).

해결 방법 1: 메모이제이션

def climb_stairs_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    memo[n] = climb_stairs_memo(n-1, memo) + climb_stairs_memo(n-2, memo)
    return memo[n]

해결 방법 2: 테이블 방식

def climb_stairs_tabulation(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

해결 방법 3: 공간 최적화

def climb_stairs_optimized(n):
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

동적 프로그래밍을 통해 배울 수 있는 것

문제 구조 이해
- 큰 문제를 작은 문제로 나누는 사고방식.
- 하위 문제의 중복성과 최적 구조를 파악하는 능력.
효율성 개선
- 메모이제이션과 테이블 방식을 통해 계산 속도를 획기적으로 향상.
일반화 가능성
- 점화식을 정의하고 이를 구현함으로써 다양한 문제에 응용 가능.

Twitter Facebook LinkedIn

amiro