[Algorithm] Dynamic Programming(동적 계획법) 설명

Dynamic Programming

다이나믹 프로그래밍이란 복잡한 문제를 여러개의 작은 문제로 나누고 값을 저장하여 푸는 방법을 말한다. 일반적으로 재귀 함수를 통해 이전 함수의 결과 값을 이용해 문제를 풀어나간다.

동적계획법 사용하는 이유

동적계획법은 재귀(Naive Recursion)함수와 비슷하다. 일반적인 재귀 함수는 같은 조건의 작은 문제들이 여러번 반복되어서 효율성이 낮다. 가장 대표적인 문제 중 하나인 피보나치 수열을 예시로 들어보자면

피보나치의 점화식은 f(n) = f(n-1)+f(n-2) 이다. 만약 f(n-1)과 f(n-2) 함수를 각각 호출할 시 겹치는 식이 많아 지는 것을 볼 수 있다. n이 크면 클 수록 겹치는 식이 기하급수적으로 늘어날 것이 분명하다. 이렇듯 재귀함수는 문제의 크기가 클수록 효율성이 매우 떨어진다.

동적계획법은 재귀함수하지만 이미 한번 구한 결과 값을 저장하고 다음에 같은 조건의 식이 발생하면 저장해 놓은 값을 재사용함으로 써 불필요한 연산을 줄여 속도를 매우 높일 수 있다.

사용조건

Overlapping Subproblems(겹치는 부분 구조)

DP는 기본적으로 겹치는 문제가 발생할 시에 사용할 수 있다.

피보나치 수열과 같이 겹치는 식의 경우 값을 저장했다가 다음번에 같은 식이 발생하면 다시 재사용한다.

---

Optimal Substructure(최적 부분 구조)

부분 문제의 최적의 결과 값이 전체 문제의 최적의 결과를 낼 수 있는 경우를 뜻한다. 이러한 구조를 가진다면 문제는 여러 작은 부분 문제로 나뉠 수 있고 작은 문제의 값을 이용해 큰 문제의 값도 구할 수 있다.

피보나치 수열도 이런 최적 부분 구조를 지녔는데 f(n) = f(n-1)+f(n-2) 와 같이 작은 부분인 f(n-1)와 f(n-2)를 이용해 f(n)을 구할 수 있다.

DP 적용하기

1. DP문제인지 확인하기

dp를 사용하기 위해선 당연하게도 해당 문제가 DP를 이용하는 문제인지 파악 해야 한다.

파악하는 방법은 위에서 말했던 대로 큰 문제를 작은 문제로 나눌 수 있는지 확인하고 작은 문제의 결과 값이 큰 문제의 최적 값을 낼 수 있는지 확인한다.

---

2. 점화식 파악하기

DP문제임을 확인 했다면 점화식을 알아야 한다.
점화식이란 DP문제를 푸는데 사용하는 재귀식을 말한다. 즉 하위 문제와 상위 문제식간의 상관 관계를 뜻한다.

점화식을 구하는 것이 DP문제의 핵심으로 이를 구해야 재귀 함수를 구현할 수 있다. 점화식은 문제마다 다르기에 문제에 맞는 점화식을 찾아야한다.

---

3. Memoization 방법 구상하기

점화식을 이용해 구현한 함수의 값을 저장할 방법을 구상 해야 한다. 이렇게 작은 문제에서 사용한 값을 다음에도 쓰기 위해 저장하는 방법을 Memoization이라고 한다.

배열에 값을 저장하고 후에 사용하는 문제에서 같은 조건의 문제가 이미 있었을 경우 저장된 값을 불러와 재사용 해야한다.

---

4. 기저 상태 확인하기

가장 많이 실수 하는 부분 중 하나다. 더 이상 쪼갤 수 없는 문제 즉 가장 작은 문제의 경우의 상황을 확인 해야 한다.

예를 들어 가장 작은 상태일 경우에만 특정 값을 반환하는 등 조건 식을 만드는데 문제의 상황에 따라 다르다.

힘들게 점화식을 풀어도 미처 생각지도 못한 부분에서 오류가 발생할 수 있으니 여러 경우의 수들을 생각하며 조건을 알아야 한다.

---

5. 구현하기

마지막으로 구상한 내용들을 토대로 코드를 작성하면 된다.

사용방법

Bottom-Up 방식 - 반복문

작은 문제를 계산하고 그 값들을 누적 해서 큰 값을 구하는 방식이다. 결과 값을 저장하는 배열 dp가 있다고 했을 때 작은 문제에서 사용하던 결과 값을 저장해 놓은 다음 큰 문제에서 하위 문제에서 저장한 값을 가져다 사용한다.

이 방식을 Tabulation 방식이라고 하는 이유는 반복문을 통해 테이블의 처음부터 끝까지 채우는 과정을 table-filling 이라고 부르기 때문이다.

결과 값을 저장하고 기억한다는 점에선 Memoization과 비슷하다.

---

Top-Down 방식 - 재귀

n값을 구하기 위해 가장 작은 문제인 기저 상태에서 시작하는 대신 가장 큰 문제인 dp[n]부터 시작하는 방식을 말하며, 내려갈 식까지 간 후 결과 값을 반환하는 방식으로 재귀를 통해 푸는 방식이다.

이전에 계산을 완료 했을 경우 저장 된 값을 불려와 이용하는 Memoization 방식을 쓴다.

분할정복(Divide and Conquer)과의 차이점

• 분할 정복과 큰 문제를 작은 문제로 나눠 계산하는 방식을 같다.
• 그러나 하위 문제 중복 여부에 따라 다르다
  • 분할 정복은 하위 문제가 중복이 일어나지 않을 때 사용
  • DP는 하위 문제가 중복이 될 경우에 사용

관련 문제

• 1003번: 피보나치 함수 - 기본적인 피보나치 함수

• 1149번: RGB거리 - 조금 더 복잡한 DP 문제

• 12865번: 평범한 배낭 - 대표적인 DP 문제중 하나인 냅색(Knapsack) 문제

• 2098번: 외판원 순회 - 유명한 DP문제중 하나인 TSP 문제

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95 https://80000coding.oopy.io/60c3d4d3-f569-4b47-bdde-9a65d30f3bc5 https://syujisu.tistory.com/entry/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95-Dynamic-Programming%EA%B3%BC-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5-Divide-and-Conquer-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98