참고 출처) ChatGPT와 블로그
https://hongjw1938.tistory.com/47
알고리즘 - Dynamic Programming(동적 계획법)
1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로
hongjw1938.tistory.com
DP(Dynamic Progragmming; 동적 계획법, 동적 프로그래밍)
복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 기법
알고리즘이라기보다는 문제해결 방식이라고 할 수 있다
문제 푸는 순서는 아니지만 개념을 쉽게 생각하면 다음과 같다
1. 전체 문제를 작은 문제로 쪼개기
2. 작은 문제를 풀고 그 결과를 저장하기
3. 작은 문제에서 저장한 결과를 재사용하여 다음 작은 문제 풀기
4. 최종 결과 계산하기
DP로 풀 수 있는 문제는 재귀함수를 활용하여 풀 수 있는 경우가 많다.
다만, 재귀함수를 사용할 경우 시간복잡도가 기하급수적으로 커지는 경우가 대부분이다.
( ∵ 재귀함수로 뻗어나가는 트리의 깊이가 100만 되어도 2^100이 되어 시간복잡도 O(2^N)이 되기 때문 )
DP는 이런 유형의 문제를 효율적으로 해결하기 위해 등장한 방법론이다.
DP의 핵심 개념
1. 분할 정복
분할 정복은 문제를 더 작은 하위 문제로 나누어 풀고 연계하는 전략을 말한다
DP는 분할 정복과 유사하나, 큰 차이점이 존재한다.
분할 정복은 분할된 하위 문제가 서로 독립적이고, 동일한 하위 문제를 공유하지 않는다.
반면, DP는 하위 문제를 해결하기 위해 그 하위 문제로 파고들어야 하여 하위 문제끼리의 중복이 발생하게 되고, 그 결과를 저장해두었다가 꺼낼 수 있도록 만든 상태에서 재사용한다는 점에서 차이가 있다.
2. 메모이제이션(Memoization)
하향식(Top-down) 접근 방식에 사용하는 개념
이미 계산된 하위 문제의 결과를 메모리에 저장하여 중복 계산을 피하고 불러올 수 있도록 하는 방법
재귀적 구조를 가지며, 필요할 때 계산을 수행하는 개념이다
구현 방법)
dp[n]의 값을 찾기 위해 재귀를 통해 dp[0] 상태까지 내려가도록 한다
하지만 단순 재귀함수로 들어간다면 계산을 중복해서 수행할 것을 메모이제이션은 이미 계산된 기록은 재사용할 수 있도록 그 값을 기록해두는 과정이 수행된다.
메모이제이션을 위해서는 리스트나, 딕셔너리에 저장하는 방식이 일반적이다.
저장된 값이 있으면 도중에 확인할 수 있도록 재귀함수의 맨 처음에 해당 조건을 추가하여 return 하도록 한다
저장된 값이 없으면 계산을 이어가도록 조건을 추가하고, 맨 처음 인덱스에 해당하는 값이 나오면 초기값을 저장 혹은 return 하도록 한다
피보나치 수열로 예를 들자면 다음과 같다
def fib_memo_list(n):
memo = [None] * (n + 1)
def helper(n):
if memo[n] is not None:
return memo[n]
if n <= 1:
memo[n] = n
else:
memo[n] = helper(n-1) + helper(n-2)
return memo[n]
return helper(n)
print(fib_memo_list(10)) # Output: 55
3. 타뷸레이션(Tabulation)
상향식(Bottom-up) 접근 방식에 사용하는 개념
쪼개진 작은 하위 문제부터 해결하여 결과를 테이블(1차원 배열, 2차원 배열 등)에 저장하는 방법
반복 구조를 가지며, 테이블 값이 채워질 때마다 다음 문제를 해결하게 된다
구현 방법)
반복문을 통해 점화식으로 결과를 내서 그 값을 전이시켜 재활용함
예를 들어, 문제를 쪼갰을 때 n단계의 작은 문제로 쪼갤 수 있어서 결과를 dp라는 배열에 저장한다고 하자.
가장 먼저, dp[0] 값을 구한다
그 다음 점화식을 활용해, dp[0]로 dp[1]을 구한다
그리고 dp[1]로 dp[2]를 구한다.
...
최종적으로, dp[n-1]로 dp[n]을 구하는 방식이다.
이전 상태의 값을 현재 상태로 전이시켜(재활용하여) 푸는 방식이라고 할 수 있다.
DP 사용 조건
DP를 활용할 수 있는 문제인지 판단하는 조건은 두 가지가 있다.
1. 최적 부분 구조(Optimal Substructure)
하위 문제의 최적 해결 방법을 사용하여 전체 문제의 최적 해결 방법을 찾을 수 있어야 함
예를 들어, 만약에
쪼개진 하위 문제에서 계산된 결과가 그 다음 하위 문제의 조건에 따라 최적의 결과가 아니게 될 경우에는 최적 부분 구조에 해당하지 않게 된다
2. 중복 하위 문제(Overlapping Subproblems)
동일한 하위 문제가 여러 번 반복적으로 계산되어야 함 (= 하위 문제가 중복되어야 함)
하위 문제의 결과를 저장하여 이후에 재계산하지 않을 수 있도록 해야 함
어렵게 느껴져서 DP를 활용하기 위해서는 여러 문제를 접하고 스스로 깨닫는 과정이 필요할 것 같다
