[DP] 다이나믹 프로그래밍 (1) 개념

다이나믹 프로그래밍 개요

• 주요 컨셉: 중복되는 연산을 줄이자!
• 컴퓨터 연산 속도에는 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적임 ➡️ 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘 작성 필요
• 다이나믹 프로그래밍과 같은 방법을 적용하면 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 증가시켜 시간을 단축할 수 있음
• 대표적인 예시 - 피보나치 수열

피보나치 수열

• 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열
• 점화식으로 표현하면 a(n) = a(n - 1) + a(n - 2), a(1) = 1, a(2) =1
  • 즉, n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수
  • 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
• 이러한 수열을 배열이나 리스트로 표현 가능
  • 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하기 때문
  • 파이썬에서는 리스트 자료형으로 표현 가능
• 재귀함수를 사용하여 피보나치 수열을 소스코드로 나타낼 수 있음

def fib(x):
  if x == 1 or x == 2:
    return 1
  return fib(x - 1) + fib(x - 2)

print(fib(4))

• 그러나, 위와 같이 구현할 경우 n의 값이 커질 수록 f(n)의 수행 시간이 기하급수적으로 증가함
  • 시간복잡도가 O(2^n)으로, 지수 시간이 소요됨
  • 동일한 함수가 반복적으로 호출되기 때문. 예를 들어 fib(6)을 계산하기 위해 fib(5)와 fib(4)를 계산해야 하는데, 각기 함수를 따로, 중복으로 호출함
• 다이나믹 프로그래밍을 사용하여 효율적으로 해결 가능

다이나믹 프로그래밍

• 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용 가능
  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 피보나치 수열은 위 조건을 만족하는 대표 문제
• 메모이제이션 기법을 사용해서 DP 구현 가능
  
  • 다이나믹 프로그래밍을 구현하는 방법 중 하나
  • 한 번 구한 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출할 경우 메모한 결과를 그대로 가져오는 기법
  • 값을 저장하는 방법이므로 '캐싱'이라고도 함
  • 리스트 대신 사전 자료형을 이용할 수도 있음
    • 수열처럼 연속적이지 않은 경우에 유용
    • ex) a(n)을 계산할 때, a(0) ~ a(n - 1) 전부가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우 유용 
  • 한 번 구한 정보를 리스트에 저장함으로써 메모이제이션 구현 가능
    •  
  • DP를 재귀적으로 수행하다가 같은 정보가 필요할 경우 이미 구한 정답을 그대로 리스트에서 읽어오기
  • 피보나치 수열에 메모이제이션 기법을 적용한 소스코드
    • 시간 복잡도는 O(N) ⬅️ 한 번 구한 결과는 다시 구해지지 않기 때문.

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

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

• 정리하자면 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어서 문제를 효율적으로 해결하는 알고리즘 기법
• 다이나믹 프로그래밍과 분할 정복의 차이점
  • 분할 정복
    • 대표적으로 퀵 정렬 존재 - 정렬을 수행할 때 정렬할 리스트를 분할
  • 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있음
    • DP는 한 번 해결했던 문제를 다시 해결함
    • 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 나중에 다시 해결할 필요 없이 그대로 반환

다이나믹 프로그래밍 2가지 방식

1. 탑다운 방식
   • 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법
   • 큰 문제를 해결하기 위해 작은 문제를 호출
   • 하향식
   • 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현
   • 메모이제션 != 다이나믹 프로그래밍
     • 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념
     • 메모이제이션 기법을 쓰더라도 DP를 위해 활용하지 않을 수 있음
2. 바텀업 방식
   • 반복문을 이용하여 소스코드를 작성하는 방법
   • 작은 문제부터 차근차근 답을 도출
   • 상향식
   • 다이나믹 프로그래밍을 반복문으로 구현할 경우, 재귀함수로 구현할 경우보다 오버헤드를 줄이고 성능을 높일 수 있음
   • 다이나믹 프로그래밍의 전형적 형태
   • 바텀업 방식에서 사용되는 결과 저장용 리스트를 DP 테이블이라고 함
   • 피보나치 수열을 바텀업 방식으로 구현한 예시

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

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
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를 적용할 수 있는지, 해결하고자 하는 부분 문제들의 중복 여부 확인
• 우선 재귀함수로 비효율적인 프로그램을 작성한 뒤, 메모이제이션을 적용할 수 있으면 코드 개선
• 보통 바텀업 방식으로 구현하는 것을 권장
  • 시스템상 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문
  • recursion depth와 관련된 오류가 발생할 수 있음
    • 이 경우 sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있음