[알고리즘] 3-4 Dynamic Programming

1. 동적 프로그래밍(Dynamic Programming / DP)

메모리를 사용해서 중복 연산을 줄이고 수행속도를 개선한다. 즉, 중복 연산해야하는 것을 메모리에 저장하기에 그걸 호출해서 이용하는 것이다. '기억하며 풀기'라고 부르는 사람도 있다는데, 이 표현이 굉장히 정확하고 쉬운 것 같다.

 

DP는 큐나 스택처럼 정해진 형태의 알고리즘이 아니다. 수행시간을 단축시키는 기법을 구현하는 것을 뜻하기에 사람마다 풀이법이 끝도 없이 달라질 수 있다. 

 

1-1 분할 정복과의 차이

주어진 문제를 작은 문제들로 나누어 푼다는 면에서 비슷하다. 하지만 DP에서는 분할된 문제들이 중복된다는 특징이 있다. 

 

1-2 어떤 문제를 DP를 통해 풀면 될까?

1) DFS / BFS로 풀 수 있지만 경우의 수가 너무 많은 문제

2) 중복적인 연산이 많은 경우

 

 

2. 메모이제이션과 태뷸레이션

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

메모이제이션은 함수의 호출 결과를 저장하고, 동일한 입력이 주어질 때 이전에 계산한 값을 반환하는 방식. 이를 통해 중복 계산을 피하고 실행 시간을 줄일 수 있다. 메모이제이션은 주로 재귀 함수와 함께 사용된다.

 

# 메모이제이션을 이용한 피보나치 수열 계산
def fibonacci_memoization(n, memo):
    if n <= 1:
        return n

    # 이미 계산한 값이 있는지 확인
    if memo[n] is not None:
        return memo[n]

    # 계산한 값을 메모에 저장
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
    return memo[n]

n = 10
memo = [None] * (n + 1)  # 초기화된 메모 배열

result = fibonacci_memoization(n, memo)
print(result)

 

 

2-2 태뷸레이션(Tabulation)

태뷸레이션은 반복적인 방식으로 동적 계획법을 구현하는 방법. 작은 하위 문제부터 시작하여 전체 문제를 해결하기 위해 반복적으로 계산다. 이를 통해 모든 하위 문제를 한 번만 계산하며 결과를 구할 수 있다.

# 태뷸레이션을 이용한 피보나치 수열 계산
def fibonacci_tabulation(n):
    if n <= 1:
        return n

    # 태뷸레이션을 위한 배열 초기화
    table = [None] * (n + 1)
    table[0] = 0
    table[1] = 1

    # 작은 하위 문제부터 전체 문제까지 반복적으로 계산
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]

    return table[n]

n = 10
result = fibonacci_tabulation(n)
print(result)

 

 

3. 탐욕(Greedy) 알고리즘

미래를 고려하지 않고 오직 현재 시점에 가장 좋은 선택을 하는 것. 이 방식은 미래를 따지지 않기에 항상 최선을 찾으리라는 보장은 없다. 그래서 현재의 가장 좋은 선택을 했을 때 최선이 보장될 때만 이 알고리즘을 써야한다. 현재의 선택이 미래의 선태에 영향을 주지 않는다라는 조건이다. 

그리디 알고리즘 관련 문제를 잘 풀려면 정렬을 잘 해야한다. DP보다도 더 빠른 알고리즘.