다이나믹 프로그래밍

1. 다이나믹 프로그래밍 개념

Dynamic Programming

동적 계획법

 

하나의 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

특정한 알고리즘이 아닌 하나의 문제 해결 패러다임

 

🕊️ DP를 사용하기 위한 조건 2가지

1) Overlapping Subproblems (겹치는 부분 문제)

2) Optimal Substructure (최적 부분 구조)

 

💁‍♂️ Overlapping Subproblems 

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다.

그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

     👉 ex) 피보나치 수열

 

💁‍♂️ Optimal Substructure

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

 

A-B의 최단 경로를 찾아야 하는 경우, A-X, A-B가 최단 경로라면 , A-X-B가 전체 최단 경로가 되는 것!

 

 

 

2. 다이나믹 프로그래밍 적용하기

 

DP는 두 가지 방식으로 구현할 수 있다.

1) Bottom-Up (Tabulation 방식) - 반복문 사용

2) Top-Down (Memoization 방식) - 재귀 사용

 

💁‍♂️ Bottom-Up 방식

아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식

 

메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자.

Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

 

💁‍♂️ Top-Down 방식

dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

 

피보나치의 예시처럼 f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.

이때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어있던 내역을 꺼내서 활용하면 된다.