DP 문제를 풀다가 DP에 대한 이해가 부족한 것 같아서 글로 정리해본다.
Dynamic Programming
동적 프로그래밍이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 이 용어는 리처드 벨만이 처음 사용했는데, 이름에 큰 의미는 없다. 그냥 멋있어서 사용했다. 아무튼간에 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다.
import java.io.BufferedReader; | |
import java.io.IOException; | |
import java.io.InputStreamReader; | |
public class Main { | |
public static int sum(int n) { | |
int sum = 0; | |
for(int i = 1; i <= n; i++) { | |
sum += i; | |
} | |
return sum; | |
} | |
public static void main(String[] args) throws IOException { | |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
int n = Integer.parseInt(br.readLine()); | |
br.close(); | |
for(int i = 1; i <= n; i++) { | |
System.out.println(sum(i)); | |
} | |
} | |
} |
위의 코드를 한 번 읽어보자.
1 = 1
2 = 2 + 1
3 = 3 + 2 + 1
...
100 = 100 + 99 + 98 + ... + 3 + 2 + 1
이런 식으로 구하는데, 잘 보면 3 = 3 + 2 + 1을 구할 때, 여기서 2 + 1은 sum(2)와 동일하므로 이미 풀었던 문제에 해당한다. 그런데 sum(3)을 풀 때, sum(2)를 처음부터 다시 구해서 쓰므로 sum(n)의 시간복잡도는 $O(n) $이 된다.
import java.io.BufferedReader; | |
import java.io.IOException; | |
import java.io.InputStreamReader; | |
public class Main { | |
static int d[]; | |
public static int sum(int n) { | |
int sum = 0; | |
if(d[n] != 0) { | |
return d[n]; | |
} | |
for(int i = 1; i <= n; i++) { | |
sum += i; | |
} | |
d[n] = sum; //문제를 푼 정답을 배열에 저장해둔다. | |
return sum; | |
} | |
public static void main(String[] args) throws IOException { | |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
int n = Integer.parseInt(br.readLine()); | |
d = new int[n+1]; | |
br.close(); | |
for(int i = 1; i <= n; i++) { | |
System.out.println(sum(i)); | |
} | |
} | |
} |
하지만 위의 코드에서는 문제를 푼 후에, 정답을 따로 저장해둬서
sum(n) = n + d[n-1]이 된다. 따라 sum(n-1)을 미리 구했다면 sum(n)을 $O(1) $만에 답을 구할 수 있으므로 효율적이다.
이런식으로 DP는 큰 문제 안에 작은 문제가 포함되어있을 때, 작은 문제의 정답으로 큰 문제의 정답을 구할 수 있다.
DP로 풀기 위한 조건
1. 큰 문제를 작은 문제로 분할할 수 있다.
2. 작은 문제의 정답을 이용하여 큰 문제를 해결할 수 있다.
따라서 DP 문제를 풀 때는, 무작정 DP를 쓸 게 아니라 이 문제를 어떻게 더 작은 문제로
분할할 수 있을지를 생각해야한다!
'Algorithm Theory > Dynamic Programming' 카테고리의 다른 글
[DP] [BOJ 11726] 2 x n 타일링 (0) | 2020.03.19 |
---|---|
[DP] [BOJ 9095] 1, 2, 3 더하기 (0) | 2020.03.18 |
[DP] [BOJ 1463] 1로 만들기 (0) | 2020.03.18 |
DP 백준 문제 풀이 (0) | 2020.03.18 |
[백준] 9251번 LCS (Longest Common Subsequence) (0) | 2019.10.06 |
댓글