동적 계획법(DP,Dynamic Programing)

동적 계획법(DP,Dynamic Programing)

다이나믹 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다.

 

문제를 해결하기 위해 사용되는 정차적인 방법 또는 계획으로

정렬 알고리즘, 검색 알고리즘, 그래프 탐색 등을 사용한다.

 

DP와 재귀적 호출의 차이점

1. 하향씩 ,  상향식 접근

재귀적 호출은 주로 하향식 접근 방식을 사용하며, 큰 문제를 작은 하위 문제로 나누어 해결하는 방식이다.

반면 동적 계획법은 주로 상향식 접근 방식을 사용하며, 작은 하위 문제들로부터 시작해 그 결과를 저장하고 이를 이용해 점진적으로 큰 문제의 해를 구한다.

 

 

2. 메모이제이션(Memoization)

 

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

이를 통하여 이전에 계산한 값을 캐시하고, 다시 필요할 떄 해당 값을 가져와 재사용하는 방식으로,

재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킬 수 있다.

 

DP 기법 적용 조건

중복되는 부분 문제

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

 

최적 부분 구조

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

 

DP 문제를 푸는 방법

1. 변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고

그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.

 

2. 변수 간 관계식 만들기

 

방식

상향식(Bottom-Up) -  반복문 사용

상향식 방식은 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식으로,

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

- 일반적으로 직관적이고 이해하기 쉬우며, 모든 작은 부분에 대한 문제를 해결하기에 최적 부분 구조를 보장한다.

 

Top-Down, 메모리제이션(Memoization) 방식 - 재귀 사용

큰 문제를 작은 부분 문제로 나누어 해결하는 방식으로, 이를 위해 재귀 함수를 사용하여 문제를 작은 부분 문제들로 쪼개, 중복 계산을 피하기 위해 이전에 계산한 값을 저장하는 Memoization을 활용합니다.

- 재귀를 사용하기에 구현이 더 간단할 수 있으며, 필요한 부분 문제만 해결하므로 계산 시간을 절약할 수 있습다.

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

 

대표 문제 예시

DP는 다양한 문제에서 사용될 수 있으며, 위의 2가지  조건을 참고하여 DP로 해결할 수 있는 문제인지 파악할 수 있다.

특정 데이터 내의 최대화/최소화 계산을 하거나 특정 조건 내 데이터를 세야하거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.

 

피보나치(Fibonacci) 수열 -> Top-Down방식 ,Memoization

 

피보나치 수열은 이전 두 항의 합으로 이루어지는 수열로, 동적 계획법을 사용하여 피보나치 수열을 구할 수 있습니다.

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

 

 

최단 경로 문제 - 하향식(Bottem-Up) 방식

주어진 그래프에서 시작 노드부터 도작 노드까지의 최단 경로를 찾는 문제로

각 노드까지의 최단 거리를 저장하고, 이를 이용해 최단 경로를 찾을 수 있다.

 

배낭 문제(Knapsack Problem) - Bottom-Up방식

배낭에 담을 수 있는 무게의 최대값이 정해져있어, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법

 

 

DP 장단점

중복 계산을 줄일 수 있으며, 효율적인 시간 복잡도를 가질 수 있다.

 

DP는 중간 결과를 저장하기 위해 추가적인 메모리를 사용하기에 문제의 크기가 커질 수록 필요한 메모리가 증가할 수 있다.