1. 개요
백준 문제를 풀며 다이나믹 프로그래밍이라는 알고리즘에 대해 공부하게 되었다.
1로 만드기 - 다이나믹 프로그래밍
연결된 링크에 보면 어떠한 문제인지 알 수 있다.
다이나믹 프로그래밍은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말하며 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
2. 예시
피보나치수열이 대표적인 예 이다.
피노바치 수를 구하고 싶을 때 재귀로 함수를 구성하게 된다면 f(n) = f(n-1) + f(n-2)이다
여기서 n의 숫자가 커질수록 계산해야하는 양은 기하급수적으로 증가하게 된다.
예를 들어 n이 4일 경우 f(4) = f(3) + f(2)가 되는데 이는 (f(2)+f(1)) + (f(1)+f(0))의 형태로 되며 n이 클수록 식은 늘어날 것이다.
이때 계산량을 줄이기 위해서는 한번 계산한 값을 저장해 두고 다음에 써야할 때 재사용 하는것이다.
3. 조건
DP를 사용하기 위해서는 2가지 조건을 만족해야한다
1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)
1) DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
2) 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다!
만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.
4. 사용
1. DP를 사용할 수 있는 문제인지 확인.
2. 점화식 만들기
3. 변수값 저장
4. 기저 상태 파악
5. 구현
여기서 구현을 할 때 방식은 두가지로 나뉜다.
1) Bottom-Up 방식
이름에서 보이듯이, 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.
메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자. Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.
왜 Tabulation?
사실 위에서 메모하기 부분에서 Memoization이라고 했는데 Bottom-up일 때는 Tabulation이라고 부른다.
왜냐면 반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling" 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다.
사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 메모하기(Memoization)와 크게 다르지 않다.
2) Top-Down 방식
이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.
피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.
이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.
마치며
출처 이며 공부하는데 많은 도움이 됐다. 글을 작성하며 내가 직접 정리한 부분도 있고 복사한 부분도 있지만 많은 공부가 됐다.
