다이나믹 프로그래밍 Dynamic Programming

정의

1) 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가(중복허용)
2) 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘

• 병합 정렬, 퀵 정렬과 같은 분할 정복 알고리즘: ‘중복된 하위 문제들’을 푸는 것이 아니기 때문에 다이나믹 프로그래밍으로 분류하지 않는다.

다익스트라 알고리즘: 다이나믹 프로그래밍과 그리디 알고리즘 둘다 해당

• BFS(너비 우선 탐색): 항상 최단 경로를 찾고 탐욕 선택 속성을 갖는 그리디 알고리즘이면서
• 이미 계산한 경로는 저장해두었다가 활용하며 중복된 하위 문제들을 푸는 다이나믹 알고리즘이기도 하다.
• 즉 다익스트라 알고리즘은 ‘최적 부분 구조’, ‘중복된 하위 문제들’, ‘탐욕 선택 속성’을 모두 갖는 알고리즘이다.

최적 부분 구조

최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 것

서울에서 부산까지 가는 최단 경로를 찾는 간단한 예

• 서울에서 대구까지 가는 경로는 3가지가 있으며, 부산까지도 마찬가지로 3가지 경로 존재
• 서울에서 부산까지 가는 최단 경로는 200km + 80km = 280km임
  • 이 경로는 서울에서 대구까지 가는 최단 경로(200km)
  • 대구에서 부산까지 가는 최단 경로(80km)로 구성됨

즉 서울에서 부산까지 가는 최단 경로는 각각의 부분 문제인,
1)서울에서 대구까지 가는 최단 경로 문제와
2)대구에서 부산까지 가는 최단 경로 문제의 해결 방법의 합

• 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되어 있음

[분할정복0]
이런 유형의 문제는 분할 정복으로 풀기 가능
또한 다이나믹 프로그래밍 또는 그리디 알고리즘으로 접근해볼 수 있는 문제의 후보가 된다.

[분할정복X]
그러나 만약 서울에서 부산까지 바로 연결되는 고속도로가 새롭게 개통되어 더 이상 대구를 거칠 필요가 없다면,

• 최적 부분 구조 가 아님
• 더는 분할 정복 으로 풀 수 없음
• 다이나믹 프로그래밍이나 그리디 알고리즘으로도 풀이할 수 없음

중복된 하위 문제들

다이나믹 알고리즘으로 풀 수 있는 문제들과 다른 문제들의 결정적인 차이

• 중복된 하위 문제들을 갖음
• ex) 피보나치 수열
  • 이처럼 피보나치 수열을 재귀로 풀면 반복적으로 동일한 하위 문제들이 발생
• 분할 정복: 중복 문제가 발생하지 않는 병합 정렬(독립됨)
• 다이나믹 프로그래밍: 피보나치 수열을 풀이하는 알고리즘과 깉이 중복문제 발생

다이나믹 프로그래밍 방법론

상향식 Bottom-Up (타뷸레이션 Tabulation)

• 일반적으로 이 방식만을 다이나믹 프로그래밍으로 지칭하기도 함
• 데이터를 테이블 형태로 만들면서 Tablulate 문제를 풀이한다고 하여 타뷸레이션 방식이라고 부른다
• 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나감(차례대로 정답을 풀어나가며 큰 문제의 정답을 만듦)
• 상향식 피보나치 수열

def fib(n):
  dp[0] = 0
  dp[1] = 1
  for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2] 
  return dp[n]

하향식 Top-Down (메모이제이션 Memoization )

• 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나간다.
• 하향식 피보나치 수열

def fib(n):
  if n <= 1:
    return n

  if dp[n]:
    return dp[n] 
  dp[n] = fib(n - 1) + fib(n - 2) 
  return dp[n]

하향식 방법론은 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스럽게 재귀로 풀어나간다.
기존 재귀 풀이와 거의 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 효율적인 방식으로, 메모이제이션 방식이라고 부른다.

피보나치 수. 난이도 | ★ 리트코드 509. Fibonacci Number https://leetcode.com/problems/fibonacci-number/ 피보나치 수를 구하라. 3 참고 피보나치 수의 정의 13세기 초기의 수학자인 레오나르도 피보나치(Leonardo Fibonacci)는 “토끼가 한 쌍 있다면 몇 달이 지난 후에 토끼는 몇 쌍으로 늘어날까?”라는 문제를 냈다. 피보나치는 문제를 단순화시키기 위해 몇 가지 가정을 덧붙였다. 처음에 토끼 한 쌍이 있으면 모든 쌍은 항상 한 배에 암수 한 쌍을 낳는다. 토끼 암컷은 태어난 지 한 달이면 새끼를 낳을 수 있으며 그 후로 계속해서 한 달에 암수 한쌍씩 낳는다. 그리고 토끼는 죽지 않는다. 처음에는 토끼가 한 쌍 있다. 둘째 달이 시작될 때 그 토끼들이 짝짓기를 하지만 아직 토끼는 한 쌍뿐이다. 셋째 달이 시작되면 암컷이 새끼들을 낳아서 토끼는 두 쌍이 된다. 넷째 달이 시작될 때 처음부터 있던 암컷이 또 암수 한 쌍의 새끼를 낳아서 토끼는 총 세 쌍이 된다. 다섯째 달이 시작되면 처음부터 있던 암컷이 새끼 한 쌍을 더 낳는 것 외에 셋째 달에 태어난 암컷도 새끼 한 쌍을 낳는다. 따라서 토끼는 총 다섯 쌍이 된다. 0번째 달(실험이 시작되기 전 달)에 토끼가 0쌍 있다고 한다면 매달 초 토끼가 몇 쌍 있는지를 적어보면 다음과 같은 수열이 만들어진다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … 이를 일컬어 ‘피보나치 수열’이라고 하며, 여기서 각 요소를 ‘피보나치 수’라고 부른다. 피보나치 수의 정의는 다음과 같다. “수학에서 피보나치 수는 Fn으로 표기하며, 피보나치 수열이라는 수열을 형성한다. 각 수는 0과 1에서부터 시작된 앞 두 숫자의 합이 된다.” 4 즉 F 0 =0, F 1 =1이며 n>1에 대해 F n =F n-1 +F n-2 이 된다. 피보나치 수를 구하는 가장 기본적인 풀이 알고리즘의 수도코드는 다음 리스트 23-2와 같다.