[알고리즘] Dynamic Programming

다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming), 동적 계획법이란
복잡한 문제를 간단한 여러 문제로 나누어 해결하는 방법
약간의 메모리 공간을 추가로 사용하여 연산 속도를 비약적으로 증가시킬 수 있다.

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
분할 정복(Divide and Conquer)와 차이는 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다.

한 번 해결했던 문제를 다시금 해결하는 경우
이미 해결된 부분 분제에 대한 답을 저장
이미 해결된 문제는 다시 해결하지 않고 저장된 값을 반환

점화식

인접한 항들 사이의 관계식
대표적인 예로 피보나치 수열이 있다.

n번째 피보나치 수 = (n - 1)번쨰 피보나치 수 + (n - 2)번째 피보나치 수
단, 1번째 피보나치수 = 1, 2번째 피보나치 수 = 1

수학적 점회식을 재귀함수로 구현

#피보나치 수열(재귀 함수)
def fibo(n):
  if n == 1 or n == 2:
    return 1
  return fibo(n-1) + fibo(n-2) #시간 복잡도 O(2^N)

print(fibo(4))

fibo(n) 함수에서 n이 커질수록 수행 시간이 기하급수적으로 증가
일반적인 빅오 표기법으로 O(2^N) 지수 시간 소요

다이나믹 프로그래밍 사용

다이나믹 프로그래밍 사용 조건

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

탑다운 방식

탑다운 (Top-Down) 방식, 하향식
메모이제이션(Memoization) 기법을 사용
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출

한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져온다.

메모이제이션은 값을 저장하는 방법으로 캐싱(Caching)이라고도 한다.
한 번 구한 정보를 리스트에 저장하는 방법으로 구현

#피보나치 수열(메모이제이션)
d = [0] *100 #한 번 계산된 결과를 캐싱하기 위한 리스트 초기화

#피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(n):
  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))

한 번 구한 결과는 다시 구해지지 않는다.
시간 복잡도 O(N)

재귀 함수 사용시 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정으로 오버헤드 발생 가능성 존재

메모이제이션

이전에 계산괸 결과를 일시적으로 기록해 놓는 넓은 개념
엄밀히 다이나믹 프로그래밍과 별도의 개념

때에 따라 수열처럼 연속적이지 않은 경우, 사전 자료형 dict() 이용 가능
모두가 아닌 일부의 작은 문제에 대한 해답만을 필요로 하는 경우

보텀업 방식

보텀업(Bottom-Up) 방식, 상향식
작은 문제부터 아래에서 위로 올라가는 방식
다이나믹 프로그래밍의 전형적인 형태

반복문을 통해 작은 문제부터 답을 도출하는 방법으로 구현

#피보나치 수열(바텀업)
d = [0] *100 #dp 테이블 초기화

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

n = 99 #계산할 피보나치 수 번호

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

print(d[n])

DP 테이블 : 보텀업 방식에서 사용되는 결과 저장용 리스트
시간 복잡도 O(N)

문제 해결 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악
해결하고자하는 부분 문제들의 중복 여부 파악

재귀 함수의 스택 크기의 한정으로 인해 보텀업 방식으로 구현 추천

참고

나동빈(2020).이것이 취업을 위한 코딩 테스트다 with 파이썬.한빛미디어