[개념정리] DP 동적프로그래밍

Dynamic Programing, DP, 동적프로그래밍, 동적계획법 으로 중요한 알고리즘 중 하나이다.

DP란

큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다. 그러나 동적프로그래밍에서는 계산한부분을 남겨놓고 계속해서 필요할때 끌어다 쓴다.

동작방식

1. 구하고자 하는 큰 문제를 작은 문제들로 나눈다. (점화식을 세운다.)
2. 가장 작은 부분문제를 푼 뒤 값을 저장한다. = 메모이제이션
3. 메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다.
4. 가장 큰 문제를 풀이할때까지 반복한다.
☆무엇을 어떻게 저장할지 정하는게 중요하다.

적용방법

1. Botton-Up 방식 : 반복문을 이용

ex)
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

4를 1,2,3으로 나눈다고 가정해보자
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
로 실행할 수 있을것이다. 총 7가지의 경우

만약 1이라면 1가지의 경우
2라면 2가지의 경우
3이라면 4가지의 경우
4라면 7의 경우
5라면 13가지의 경우가 생길것이다.

여기서 d[n] = d[n-1]+d[n-2]+d[n-3] 이라는 점화식을 도출할 수 있다.

이처럼 직관적으로 구할 수 있는 작은 해를 구한 후 이를 이용하여 더 큰문제를 풀 수 있다.
이 방법을 Bottom-up 방식이라고 부른다.



2. Top-Down 방식 : 재귀함수 사용

Bottom-up 문제를 Top-Down 으로 풀어보자.

만약 d[7]을 구하려면 d[6] d[5] d[4]를 알아야 하고
d[6]을 구하려먼 d[5] d[4] d[3] 을 알아야 할것이다.
일일히 다 구해주기에는 d[5] 와 d[4] 를 겹치는 일이 중복되어 시간복잡도의 낭비가 생길것이다.
이에 이미 구한 값을 기록해두고 불필요한 재귀호출을 방지하는 메모이제이션 작업을 한다.

dfs로 재귀를 구현할것이다.

dfs (몇번째) { 만약 테이블(몇번째)가 이미 방문되었다면 테이블(몇번째)를 리턴한다. 만약 '몇번째'가 1,2,3 이라면 1,2,4를 반환한다. (계산안되는 초기값이기때문) 아니라면 테이블(몇번째) 를 구해준다. dfs(몇번째-1)+dfs(몇번째-2)+dfs(몇번째-3) } => int dfs( int n) { if(table[n]) return table[n]; if(n==1||n==2) return n; else if(n==3) return 4; else return table[n] = dfs(n-1)+dfs(n-2)+dfs(n-3); }

추가자료 (DP문제풀이)

dbstndi6316.tistory.com/72

[백준문제풀이] 11726 2xn 타일링

추가자료 (DFS)

dbstndi6316.tistory.com/64?category=953968

[기본문제풀이] DFS 깊이우선탐색