동적 프로그래밍
1.Dynamic Programming이란?
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용 한다.
2.동적 계획법의 조건
동적 계획법을 적용하려면 위 정의에서 본 것처럼 두 가지 속성을 만족 시켜야 한다.
- 부분 반복 문제(Overlapping Subproblem)
- 최적 부분 구조(Optimal Substructure)
2.1 부분 반복 문제
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우가 발생하는데
이러한 반복적인 연산을 부분 반복 문제라고 한다.
즉, DP는 부분 문제의 결과를 저장하여 재계산하지 않을 수 있어야 하는데, 행당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
2.2 최적 부분 구조
최적 부분 구조란, 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다.
3. 메모이제이션(Memoization)
반복되는 연산 과정을 줄이기 위해서는 메모이제이션이라는 동적 프로그래밍의 개념이 도입되었다.
메모이제이션은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.
4. 동적 계획법 접근 방법
4.1 Top-Down
Top-Down방법은 말 그대로 위에서 아래로 접근하는 방법으로 큰 문제에서 부분 문제로 쪼개가며, 재귀 호출을 이용하여 푸는 방법이다.
메모를 위해 dp라는 배열을 만들고 이것이 1차원이라 가정했을 때, dp[0]은 기저 상태이고 dp[n]을 목표 상태라고 했을 때, Top-Down은 dp[n]을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.
4.2 Button-Up
Button-Up방법은 말 그대로 아래에서 위로 접근하는 방법으로 부분 문제에서부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법이다.
Button-Up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.
5. DP 사용
- DP로 풀 수 있는 문제인지 확인한다.
동적계획법의 2가지 조건을 만족하는지 확인해 본다. - 문제의 변수 파악
DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다. 즉, 문제 내 변수의 개수를 알아내야 한다는 것이다.
예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과 값이 다르지만 그 결과를 재사용하고 있다. - 변수 간 관계식 만들기(점화식)
변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하다. 또한 우리는 그 결과값을 그대로 이용할 것이므로 그 관계식을 만들어낼 수 있어야 한다. 그런한 식을 점화식이라고 부르며 그를 통해 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다.
예를 들어 피보나치 수열에서는 $f(n) = f(n-1) + f(n-2)$이다. - 메모하기(memoization)
변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.
변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다. -
기저 상태 파악하기
가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다.
피보타치 수열을 예시로 들면, $f(0) = 0 f(1) = 1$과 같은 방식이다. 이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 저 2개로 볼 수 있다. - 구현하기
DP를 구현하는 2가지 방식은 위에 설명한 2가지 방식이 있다.
- Bottom-Up - 반복문 사용
- Top-Down - 재귀 사용