[알고리즘🧩] 다이나믹 프로그래밍(DP)

CS 및 알고리즘 공부/알고리즘

[알고리즘🧩] 다이나믹 프로그래밍(DP)

Gogumiing 2024. 9. 25. 12:30

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

큰 문제를 작게 나누고 같은 문제라면 한 번씩만 연산하여 문제를 효율적으로 해결하는 알고리즘 기법으로, '동적 계획법'이라고도 한다. 컴퓨터의 제약 사항(연산 속도의 한계, 한정된 메모리 공간)을 극복하기 위해 메모리 공간을 조금 더 사용하여 연산 속도를 비약적으로 증가시킴으로써 문제를 해결하는 방법이다.

▷ 프로그래밍에서 '다이나믹(Dynamic)'은 '프로그램이 실행되는 도중에'를 의미한다. 따라서 자료구조의 동적 할당(Dynamic Allocation)은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법을 의미한다. DP의 Dynamic과는 다른 의미임을 기억하자.

참고로 다이나믹 프로그래밍(DP)을 사용할 수 있는 조건은 아래와 같다.

큰 문제를 작은 문제로 나눌 수 있다.
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

💡 다이나믹 프로그래밍과 분할 정복(Divide and Conquer)의 차이점

▷ 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있으나 분할 정복은 그렇지 않다.

✅ DP로 해결 가능한 대표 문제: 피보나치 수열

이전의 두 항의 합을 현재 항으로 설정하는 특징을 가진 피보나치 수열은 점화식을 이용해 간결하게 표현할 수 있다.

점화식: 인접한 항들 사이의 관계식

예를 들어 첫 번째 항과 두 번째 항의 값이 모두 1인 피보나치 수열의 경우, 아래와 같이 수열이 이어진다.

1 1 2 3 5 8 13 21 34 55 89 ...

이것을 점화식으로 나타내면 아래와 같다.

점화식을 재귀 함수를 사용해 표현해본다.

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

print(fibo(4))      # 4번째 항을 구해보자.

▶ 그러나 위와 같이 재귀 형식으로 표현하면, 입력하는 N의 값이 커질수록 수행 시간이 기하급수적으로 늘어난다는 문제점이 있다. 위 소스코드의 시간복잡도는 일반적으로는 O(2^N)라고 표현하지만, 엄밀히 말하자면 θ(1.618...^N)로 표현될 수 있다. 따라서 x = 26인 경우 이미 1억번의 연산이 필요하게 된다.

이것은 함수를 반복적으로 호출하기 때문인데, fibo(6)을 위해 호출하는 과정을 표현한 그림을 살펴보자.

이미지 출처: <이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음>

함수를 반복적으로 호출하면, 이미 한 번 계산한 것을 호출할 때마다 새롭게 계산하게 된다. 위 그림에서 fibo(3)이 호출된 횟수는 총 3번이다. 따라서 입력하는 N 값이 커질수록 반복하여 호출하는 수가 많아지게 된다.

예를 들어, fibo(100)을 계산한다면 1,000,000,000,000,000,000,000,000,000,000,000번의 연산이 필요하다. 일반적인 컴퓨터가 1초에 1억 번의 연산을 한다고 가정할 때, 수백억 년을 필요로 하는 연산 횟수이다.

이것을 다이나믹 프로그래밍(DP) 기법을 활용해 효율적으로 해결해보자.

# 피보나치 수열 소스코드 (Top-Down 방식 -> Memoization 기법 사용)

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

# 탑다운 다이나믹 프로그래밍 (Top-Down DP)
def fibo(n):
    # 종료 조건 (1 혹은 2일 때 1을 반환함)
    if n == 1 or n == 2:
        return 1
    
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[n] != 0:
        return d[n]
    
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(n - 1) + fibo(n - 2)
    return d[n]


print(fibo(6))     # 6번째 항을 구해본다.

위와 같이 다이나믹 프로그래밍(DP) 기법을 적용한다면 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이 된다. → 왜냐하면 fibo(1)을 구한 후 그 값이 fibo(2)를 구하는 데 사용되고, fibo(2)의 값이 fibo(3)의 값을 구하는 데 사용되는 방식으로 이어지기 때문임

따라서 실제로 호출되는 함수에 대해 확인해보면 위와 같이 방문하는 것을 알 수 있다.

▷ 하지만 위와 같이 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신 반복문을 사용해 구현한다면 오버헤드를 줄일 수 있다.(일반적으로 반복문을 이용한 다이나믹 프로그래밍이 성능이 더 좋다.)

## 피보나치 수열 소스코드 (Bottom-Up 방식 -> 반복문 사용)

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

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

# 피보나치 함수(Fibonacci Function) 반복문으로 구현 -> Bottom-Up DP
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

✅ DP 구현 방식 (Top-Down / Bottom-Up)

탑다운(Top-Down) 방식
큰 문제를 해결하기 위해 작은 문제를 호출함을 의미하며, 재귀 함수를 이용해 DP 소스코드를 작성함
- '하향식'이라고도 하며, 메모이제이션(Memoization) 방식을 사용한다.
  - 메모이제이션(Memoization) → 캐싱(cashing)이라고도 함

# 피보나치 수열 소스코드 (Top-Down 방식 -> Memoization 기법 사용)

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

# 탑다운 다이나믹 프로그래밍 (Top-Down DP)
def fibo(n):
    # 종료 조건 (1 혹은 2일 때 1을 반환함)
    if n == 1 or n == 2:
        return 1
    
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[n] != 0:
        return d[n]
    
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[n] = fibo(n - 1) + fibo(n - 2)
    return d[n]


print(fibo(99))     # 99번째 항을 구해본다.

바텀업(Bottom-Up) 방식
작은 문제부터 차근차근 답을 도출하는 것을 의미하며, 반복문을 이용해 DP 소스코드를 작성함
- '상향식'이라고도 하며, 마찬가지로 메모이제이션(Memoization) 방식을 사용한다.
  - 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 한다.
- DP의 전형적인 형태는 바텀업(Bottom-Up) 방식이다.

## 피보나치 수열 소스코드 (Bottom-Up 방식 -> 반복문 사용)

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

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

# 피보나치 함수(Fibonacci Function) 반복문으로 구현 -> Bottom-Up DP
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

✅ 예제 문제

📌 알고리즘 문제에 적용할 때에는, 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 다이나믹 프로그래밍(DP)을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자. 그리고 DP를 적용할 수 있다면 아래의 과정을 거쳐 문제를 풀어본다.

1. 함수가 호출되는 과정을 그림으로 그려보고, 동일하게 여러 번 호출되는 함수를 확인한다.
2. 문제에서 요구하는 내용을 점화식으로 표현해본다.
3. 점화식을 토대로 바텀업(Bottom-Up) DP로 소스코드를 작성해본다.

티스토리

[알고리즘🧩] 다이나믹 프로그래밍(DP)

[알고리즘🧩] 다이나믹 프로그래밍(DP)

목차