20240307_동적 계획법

오늘의 TIL은 동적 계획법(DP - Dynamic Programming)에 관한 간단한 정리이다.

 

 

동적 계획법(DP - Dynamic Programming)

동적 계획법(DP)는 최적화 이론의 한 기술로, 특정 범위까지의 값을 구하기 위해서

그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

 

즉, 단계를 나누고 각 단계마다 구한 값을 재활용하여 특정 범위까지 넓혀나가는 것이다.

이는 문제의 범위를 조금씩 줄여서 최소 단위를 만들어 풀어내는 분할 정복 알고리즘과 비슷한 느낌이다.

 

 

DP를 사용하는 이유

DP를 사용하는 가장 큰 이유는 반복되는 계산을 줄이기 위함이다.

 

예를 들어 피보나치 수열의 문제를 푸는 경우를 생각해보면

피보나치 수열은 f(n) = f(n-1) + f(n-2)의 방식으로 표현할 수 있는 식이다.

 

만약 DP를 사용하지 않고 n번째 항을 구한다면 n-1, n-2항을 구한 뒤에 더해주고

n+1번째 항을 구하는 경우에 또다시 n, n-1항을 구한 뒤에 더해주게된다.

즉, 구하려는 항의 이전 항까지의 값을 매번 새롭게 구하게된다.

 

만약 여기에서 DP를 사용하게 된다면 각 항은 1번씩만 구한 뒤에 이를 리스트 등에 저장하고

필요한 경우에 리스트에서 가져오는 방식으로 문제를 해결할 수 있다.

이런 경우에 시간복잡도가 O(n^2) 에서 O(f(n))으로 매우 효율적으로 개선할 수 있다.

 

 

DP를 사용할 수 있는 문제 유형

DP는 아래의 두 유형인 경우 사용할 수 있는 풀이 방법이다.

 

1. 중복되는 부분 문제(Overlapping Subproblems)

DP는 작은 부분의 문제를 해결하고 그 값을 저장하여 다시 활용하는 방식이므로

동일한 작은 문제들이 반복하여 나타나는 경우(위의 피보나치 수열)에 사용이 가능하다.

 

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

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

 

 

DP를 사용하는 방법

DP를 사용하는 방법은 크게 나눠서 1. 구한 데이터를 저장하는 공간을 만들고, 2. 각 항들의 관계(점화식)를 만들기

의 두 단계로 나눠진다고 할 수 있다.

 

어제 풀이했던 'N으로 표현하기'라는 문제에서 HashSet를 사용한 List를 만들고 초기값들을 저장한 뒤에

이 초기값들을 활용하여 각 단계에서 만들 수 있는 수들을 만들어 위의 List에 저장하면서

데이터베이스라고 할 수 있는 정보를 늘려나가며 원하는 수를 찾는 방식으로 풀이한 것이 좋은 예이다.

 

또, DP는 Bottom-Up과 Top-Down으로 두 방식으로 사용할 수 있는데,

 

Bottom-UP은 작은 부분부터 문제를 차례대로 해결하여 전체 문제를 해결하는 방식이다.

반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 그 결과를 저장하여 사용하는 방식이다.

(최단 경로 문제)

 

Top-Down은 큰 문제를 작은 부분 문제로 나누어 해결하는 방식으로,

재귀 함수를 사용하여 문제를 작은 부분 문제들로 나누고,

중복 계산을 피하기 위해 이전에 계산한 값을 저장하여 이를 가져오는 방식으로 중복 계산을 피한다.

(피보나치 수열)

 

 

DP의 장점과 단점

DP의 장점은 중간에 나타나는 값들을 저장하므로

중복 계산을 줄일 수 있다.

효율적인 시간 복잡도를 가질 수 있다.

 

DP의 단점은

중간에 나오는 값들을 모두 저장하므로 메모리 사용량이 크다.

따라서 문제의 크기에 따라서 적용할 수 없는 경우도 있다.