DP - Algorithm

DP는 복잡한 문제를 더 작은 하위 문제로 나누어 해결하고, 그 결과를 저장해두어 하위 문제가 반복될때 다시 계산하지 않고 저장된 값을 재사용하는 알고리즘 설계 기법

 

DP 특징

- 최적 부분 구조

큰 문제의 최적해는 작은 문제의 최적해로 구성할 수 있다 -> 문제를 여러 개의 더 작은 문제로 나누어 해결할 수 있다.

- 중복되는 하위 문제

동일한 하위 문제가 여러 번 반복해서 등장한다 -> 이미 계산한 결과를 저장하여 중복 계산을 피한다

- 점화식

주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식을 정의

 

DP와 재귀적 호출의 차이점은?

재귀적 호출은 주로 하향식 접근 방식을 사용 -> 큰 문제를 하위 문제로 나누어 해결하는 방식

동적 계획법(DP)은 주로 상향식 접근 방식을 사용 -> 작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 해를 구해나감

 

메모제이션

동적 계획법은 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용

이를 통해 이전에 계산한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용함

-> 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상

 

 

DP기법을 적용시킬 수 있는 조건?

1. 중복되는 부분 문제

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구함 그러므로 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능

 

2. 최적 부분 구조

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

 

A-B까지의 가장 짧은 경로를 찾고자 하는 경우, 중간에 X가 있을때 A-X / X-B가 많은 경로중 가장 짧은 경로라면 전체 최적 경로도 A-X-B가 정답이 됨

 

 

DP로 문제 푸는 방법

1. 메모하기

변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.

2. 변수간 관계식(점화식) 만들기

예를 들어 피보나치 수열의 f(n) = f(n-1) + f(n-2)라는 식

 

DP 문제 해결 방식

Bottom-Up 방식 - 반복문 사용

작은 부분 문제부터 차례대로 해결해서 전체 문제를 해결하는 방식

이를 위해 반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 결과를 배열 등에 저장

-> 일반적으로 더 직관적이고 이해하기 쉬움, 또한 모든 작은 부분 문제를 해결하므로 최적 부분 구조를 보장

 

Top-Down 방식 - 재귀 사용

큰 문제를 작은 부분 문제로 나누어 해결하는 방식

이를 위해 재귀 함수를 사용하여 문제를 작은 부분 문제들로 쪼개고 중복 계산을 피하기 위해 계산한 값을 저장하는 메모제이션을 활용

-> 메모제이션은 재귀를 사용하므로 구현이 더 간단할 수 있음, 또한 필요한 부분 문제만 해결하므로 계산 시간을 절약할 수 있음

하지만 재귀 호출의 오버헤드가 발생할 수 있으며, 모든 작은 부분 문제를 해결하지 않을 경우 최적 부분 구조를 보장하지 않을 수 있음

 

 

대표적인 DP문제

1. 피보나치 수열 - Top-Down 방식

두 항의 합으로 이루어지는 수열 -> DP를 사용하여 피보나치 수열을 구할 수 있음

작은 문제부터 시작하여 계산 결과를 저장하고 이를 이용하여 큰 문제의 해를 구하기