동적 프로그래밍 D

동적 프로그래밍

(브루트포스 + 이전 값 재활용)

분할정복 기법을 사용하는 경우가 많다.
큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서
푸는 기법이다. 작은 문제들을 풀다보면 같은 문제들을 반복해서
푸는 경우가 생기는데 그 문제들을 매번 재계산하지 않고 값을 저장
해두었다가 재사용하는 기법이 동적 프로그래밍이다.
즉, 이미 했던 연산이 반복되는 결점을 보완하기 위해 쓰여지기 시작함

메모이제이션이 동적 프로그래밍 중 하나이다.
메모이제이션이란 재귀 호출 시, 반복적으로 계산되는 것들의 계산
횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에
재사용하는 방법이다.

 

# 문제풀이 방식
문제풀이 방식으로는 TOP-DOWN, BOTTOM-UP 이 존재한다.
top-down은 대부분 재귀
bottom-up은 대부분 for문

 

# 팁
dp 점화식을 만들 때 특정한 상황을 가정해서 만들자
n개의 배열에서 특정한 i번째 일때의 상황

또는 맨 끝부분에서 나올 수 있는 경우의 수를 생각해서

어떤 순간인 i번째를 정하고 i번째가 되기 위한 경우를 생각한다
관계는 i와 관련짓고 예를 들어 i-1, i 한 단계씩 관련을 짓는다던가

장점과 단점
동적 프로그래밍은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘이다 

(브루트포스의 성격)

여기서 그리디 알고리즘과 대비된다
그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의
최적의 해를 찾는 방식이다 닥치는 순간만을 고려해서 해를 구하기
때문에 도출된 값이 항상 최적의 해라고 할 수는 없다 하지만
동적 프로그래밍은 모든 방법을 검토해 보고 결과적으로 최적의 해를 택한다.


문제를 풀기 위한 단계
1. dp로 풀 수 있을지 없을지부터 구분해라
dp로 분류될 수 있는 문제의 몇가지 특성이 있음.
문제의 해가 중복되는 하위문제, 해를 사용하여 풀 수 있는 특성이
있는 지 또는 문제의 최적 해가 그 하위 문제의 최적 해로부터 
얻을 수 있는 구조를 갖는 문제인지를 확인해라
보통 최적하부구조(하위 문제의 최적해로부터 얻을 수 있는 구조)
특성을 갖는 문제들은 일반적으로 어떤 조건이나 확률을 주고
특정 수량이나 카운팅을 최대, 최소화하라는 문제가 대부분이며
dp를 사용하여 풀 수 있다.

2. 하위문제를 구분하기 위한 매개변수 정의
dp를 풀다보면 하위문제들로 나눌 수 있고 각 하위 문제의 특정
위치를 고유하게 식별할 수 있는 매개변수가 필요하다
예를 들어 피보나치 수열에서 각 하위문제의 상태를 f(n), f(n-1)로 
구분하는데 n은 특정 하위문제를 고유하게 식별할 수 있는 매개변수
가 된다 dp는 이전 계산 하위문제들의 결과를 사용하여 최종결과의
해를 찾기위해 공식화하는 것이 전부인데 이전 상태들 사이의
관계를 발견하여 현재 상태에 도달하기 위해 유니크한 하위문제의
매개변수를 정의하는 것은 기본이 된다.

3. 하위문제의 패턴을 찾아 공식화 하기
문제를 푸는 단계 중 가장 어려운 부분이다. 하위문제의 패턴을
찾아 점화식을 세운다는 것이다.