[알고리즘] 다이나믹 프로그래밍

미남로그·2021년 12월 17일

algorithm datastructure python

📌 강의 바로가기

개념과 코드, 이미지는 해당 책과 강의를 참고하였습니다.

다이나믹 프로그래밍

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다.
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다.
다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식으로 구성됩니다.

탑다운 (Top-down) 방식

가장 큰 것부터 계획하여 세부적으로 들어가는 방식

바텀업(Bottom-up) 방식

작은 것부터 계획하여 하나씩 이어 붙이는 형식

출처: 문제 해결 방식의 두 방향! : 탑다운 과 바텀업 방식

다이나믹 프로그래밍은 동적 계획법이라고도 부릅니다.
일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요?
- 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미합니다.
- 반면에 알고리즘 개념 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미없이 사용된 단어입니다.

다이나믹 프로그래밍 조건

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있음

최적 부분 구조(Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
중복되는 부분 문제 (Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 합니다.

피보나치 수열

다이나믹 프로그래밍을 이해하고 적용할 수 있는 대표적인 문제로 피보나치 수열이 있습니다.

피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있습니다.

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

각각 앞의 항들의 합으로 이어지는 수열을 피보나치 수열이라 합니다.

1( $a_1$ ) + 1( $a_2$ ) = 2( $a_3$ )
1( $a_2$ ) + 2( $a_3$ ) = 3( $a_4$ )
2( $a_3$ ) + 3( $a_4$ ) = 5( $a_5$ )

...

점화식이란 인접한 항등 사이의 관계식을 의미합니다.
피보나치 수열을 점화식으로 표현하면 다음과 같습니다.

$a_n = a_{n-1} + a_{n-2}$ $, a_1 = 1, a_2 = 1$

피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있습니다.
- 프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현합니다.

피보나치 수열 계산 과정

피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있습니다.
- n번째 피보나치 수를 f(n)이라고 할 때, 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같습니다.

f(4)를 구하기 위해 호출했을 때 재귀적으로 f(3)와 f(2)를 알고 있어야 하며,

다만, f(3)은 f(2)와 f(1)을 알고 있어야 합니다.

이 각각의 값을 구하기 위해 어떤 값들을 필요로 하는지 확인할 수 있고, 점화식으로 표현할 수 있는 구조는 재귀 함수를 이용해 작성할 수 있습니다.

💻재귀함수 이용 소스코드

피보나치 함수를 재귀함수로 표현

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

실행결과
3

피보나치 수열의 시간 복잡도 분석

단순 재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 됨
다음과 같이 f(2)가 여러 번 호출되는 것을 확인할 수 있음
중복되는 부분의 문제!

트리 구조를 확인 했을 때 동일한 값이 반복적으로 호출되고 있습니다.

이처럼 f(6)을 호출하면서 불필요한 중복되는 문제가 발생하는 것을 확인했습니다.

이는 수행 시간의 비효율을 불러옵니다.

피보나치 수열의 시간 복잡도는 다음과 같습니다.
- 세타 표기법: $Θ(1.618^{...N}$ )
- 빅오 표기법: $O(2^N)$
빅오 표기법을 기준으로 f(30)을 계산하기 위해 약 10억 가량의 연산을 수행해야 합니다.
그렇다면 f(100)을 계산하기 위해 얼마나 많은 연산을 수행해야 할까요?

한 번 해결한 문제를 여러 번 호출되는 것을 막는 방법은 미리 값을 기록해두는 방법이 있는데요.

피보나치 수열의 효율적인 해법: 다이나믹 프로그래밍

다이나믹 프로그래밍의 사용 조건을 만족하는지 확인합니다.

최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있습니다.
중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결합니다.

피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족합니다.

맨앞에서 언급했듯이 다이나믹 프로그래밍을 구현하는 방법은 두 가지가 있다고 소개 드렸는데요!

첫 번째가 탑다운 방식, 두 번째가 바텀업 방식이었습니다.

이 방식을 이용해봅시다.

메모이제이션(Memoization)

메모이제이션은 탑다운 방식에서 사용되는 방법입니다.

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
한 번 계산한 겨로가를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.
- 값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 합니다.

탑다운 VS 바텀업

탑다운(메모이제이션) 방식은 하향식이라고도 하며, 바텀업 방식은 상향식이라고도 합니다.
다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식입니다.
- 결과 저장용 리스트는 DP 테이블이라고도 부릅니다.
엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미합니다.
- 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아닙니다.
- 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있습니다.

💻피보나치 수열: 탑다운 다이나믹 프로그래밍 소스코드

# 탑다운 다이나믹 프로그래밍 소스코드
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화

# 리스트의 크기를 100으로 설정해주기
d = [0] * 100

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

print(fib(99))

실행결과
218922995834555169026

💻피보나치 수열: 바텀업 다이나믹 프로그래밍 소스코드

# 바텀업 다이나믹 프로그래밍 소스코드
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

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

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
    
print(d[n])

실행결과
218922995834555169026

피보나치 수열: 메모이제이션 동작 분석

이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리합니다.

색칠된 값을 바로 호출하기 때문에 불필요한 연산을 줄여 시간 복잡도를 줄여줍니다.

실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문합니다.

메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 $O(N)$ 입니다.

# 메모이제이션 동작 분석
d = [0] * 100

def fib(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fib(x-1) + fib(x-2)
    return d[x]

print(fib(6))

실행결과
f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

f(6)을 호출하면 f(5) → f(4) → f(3) → f(2) → f(1) → f(2) → f(3) → f(4) 의 형태로 함수가 호출됩니다.

다이나믹 프로그래밍 vs 분할 정복

앞에서 배웠던 정렬 파트에서 공부했던 퀵 정렬처럼 분할 정복과 다이나믹 프로그래밍은 어떤 차이점이 있는지 살펴보겠습니다.

다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있습니다.
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복입니다.
- 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됩니다.
- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않습니다.

분할 정복의 대표적인 예시인 퀵 정렬을 살펴봅시다.
- 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않습니다.
- 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않습니다.

예를 들어, 피벗 값으로 5를 기준으로 잡으면 배열의 중간으로 들어가며 분할됩니다.

해당 5의 위치는 그 이후에도 바뀌지 않습니다.

퀵 정렬 동작 원리를 확인해보면, 분할이 이루어진 뒤에

왼쪽에 있는 모든 원소와 오른쪽에 있는 모든 원소에 대해서 다시 한 번 각각 재귀적으로 퀵 정렬을 수행하며,

재귀적으로 호출되는 과정이 모두 종료가 되었을 때, 전체 범위에 대해서 정렬이 수행됩니다.

이처럼 한 번 분할이 이루어지고 나면 더 이상 다른 부분 문제에 포함되지 않고 그 위치가 변경되지 않기 때문에 부분 문제가 중복되지 않는다고 표현할 수 있습니다.

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요합니다.
가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결 할 수 있는지 검토할 수 있습니다.
- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해 봅시다.
일단 재귀 함수로 비효율적인 오나전 탐색 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법 사용
- 메모이제이션 방법으로 바꾸기

새로 배운 개념

다이나믹 프로그래밍
탑다운, 바텀업 방식
메모이제이션(탑다운)
캐싱(Cashing)
DP 테이블(바텀업)
분할 정복

미남로그

미남이 귀엽죠

이전 포스트

[논문리뷰] RetinaNet: Focal Loss for Dense Object Detection

다음 포스트