취업 리부트 코스 4주차(4) - 다이나믹 프로그래밍(DP)

동적 계획법이라고도 하는 다이나믹 프로그래밍은 divide-and-conquer(분할 정복)처럼 문제를 풀긴 하는데 하위 문제들에 대한 솔루션들을 결합해 가면서 문제를 풀어나가는 알고리즘을 말한다.

다이나믹 프로그래밍 개념

• 큰 문제를 작은 문제로 나눠 푸는 알고리즘 방식.
• 작은 문제들의 해를 저장하고 재활용하여 전체 문제의 해를 구함.
• 핵심은 문제 풀이의 핵심은 규칙을 찾는 것
• 작은 문제의 해를 저장하여 재사용하는 메모이제이션(캐싱) 기법을 활용.

대표적인 문제가 피보나치 수열 문제이다. 여기에 DP의 특징을 더하자면 단순히 재귀함수로 구현하면 연산 수행시간이 기하급수적으로 늘어나기에 초기값을 설정하고 한번 수행한 결과를 메모리에 저장해서 재사용 한다는 점이다. 이러한 점을 메모제이션(캐싱) 기법이라고도 한다.

def fibonacci(n):
    if n <= 1:
        return n
    
    if memo[n] != 0:
        return memo[n]
    
    memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

# 초기화 및 메모 배열
memo = [0] * (n+1)

다이나믹 프로그래밍 방식

1. 탑다운 (하향식)

• 한번 계산한 결과를 메모이제이션한다.
• 같은 문제를 다시 호출하면 메모한 결과를 가져온다.

# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0] * 100

def fibo(x):
    # 종료 조건
    if x == 1 or x == 2:
        return 1
        
    # 이미 계산한 적 있으면 그대로 반환
    if d[x] != 0:
        return d[x]
        
    # 아직 계산하지 않은 문제는 점화식에 따라서 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

2. 바텀업(상향식)

• 작은 문제 + 작은 문제 => 큰 문제가 되는 형식
• 반복문 이용

# 앞서 계산된 결과를 저장할 테이블 초기화
dp = [0] * 100

# 첫 번째와 두 번째 피보나치 수는 1
dp[1] = 1
dp[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

아직 배운 것 중에선 DP 문제가 제일 헷갈린다.
참고 할 문제와 풀이들

이것이 코딩 테스트다 - 개미 전사
DP 알고리즘 문제와 풀이 2개