DP 알고리즘
DP(Dynamic Programming) 알고리즘은 큰 문제를 작은 부분 문제로 나누어 푸는 기법입니다. 작은 부분 문제들의 결과를 저장하고 활용하여 중복 계산을 피하면서 효율적으로 문제를 해결합니다. DP는 최적화 문제나 조합 문제를 해결하는 데에 주로 사용되며, 다음과 같은 특징을 가지고 있습니다.
장점:
1. 중복 계산을 피할 수 있습니다: 작은 부분 문제의 결과를 저장해두고 재사용함으로써 중복 계산을 피할 수 있습니다. 이로써 계산 시간을 줄이고 효율적인 알고리즘을 구현할 수 있습니다.
2. 문제를 작은 부분으로 나누어 해결할 수 있습니다: 큰 문제를 작은 부분 문제로 분할하여 해결하는 방식으로 문제를 더 이해하기 쉽게 만들 수 있습니다. 이로써 복잡한 문제를 단순화하고 해결할 수 있습니다.
3. 최적 부분 구조를 가집니다: DP는 최적 부분 구조(Optimal Substructure)를 가지는 문제에 적용할 수 있습니다. 최적 부분 구조는 문제의 최적해가 부분 문제의 최적해로 구성되는 특성을 의미합니다.
단점:
1. 모든 경우의 수를 탐색하는 것이 아니기 때문에 최적해를 보장하지 않을 수 있습니다. 때로는 최적해가 아닌 부분해를 구할 수도 있습니다. 따라서 DP를 사용할 때에는 문제의 특성과 제약사항을 잘 파악하여 해답이 최적해임을 검증해야 합니다.
2. 메모리 사용량이 크게 증가할 수 있습니다. DP는 부분 문제의 결과를 저장하기 위해 메모리를 사용하는데, 문제의 크기나 연산량에 따라 메모리 사용량이 상당히 증가할 수 있습니다. 이를 개선하기 위해 메모이제이션(Memoization) 기법을 사용하기도 합니다.
DP는 문제의 특성과 구현 방식에 따라 다양한 형태로 적용될 수 있으며, 최적화 문제, 최단 경로 문제, 배낭 문제 등 다양한 문제 유형에 활용됩니다. 효율적인 알고리즘 설계를 위해 DP 기법을 익히고 응용할 수 있는 것이 중요합니다.
프로그래머스 - 숫자 변환하기
class Solution {
int min = Integer.MAX_VALUE;
public int solution(int x, int y, int n) {
dfs(x, n, y, 0);
if(min == Integer.MAX_VALUE) {
return -1;
}
return min;
}
public void dfs(int x, int n, int y, int count) {
if(x > y) {
return;
}
if(x==y) {
min = Math.min(min, count);
}
dfs(x+n, n, y, count+1);
dfs(x*2, n, y, count+1);
dfs(x*3, n, y, count+1);
}
}
처음에 위 코드로 했는데 실패했다. 생각해보니 시간 복잡도를 계산해보니 O(3^n)이라는 말도 안돼는 비효율적인 코드라는 걸 알게되었다. n 크기가 100만 정도 넘어가면 O(n^2)도 보통 사용하질 않는데 사람들이 대부분 DP로 풀어서 다시 풀었다.
class Solution {
public int solution(int x, int y, int n) {
int[] dp = new int[y+1];
for(int i=0; i<=y; i++){
dp[i] = Integer.MAX_VALUE;
}
dp[x] = 0;
for(int i=x; i<=y; i++) {
if(dp[i] == Integer.MAX_VALUE) {
continue;
}
if(i+n <= y) {
dp[i+n] = Math.min(dp[i+n], dp[i]+1);
}
if(i*2 <= y) {
dp[i*2] = Math.min(dp[i*2], dp[i]+1);
}
if(i*3 <= y) {
dp[i*3] = Math.min(dp[i*3], dp[i]+1);
}
}
if(dp[y] == Integer.MAX_VALUE) {
return -1;
}
return dp[y];
}
}
프로그래머스 - 땅따먹기
class Solution {
int solution(int[][] land) {
int sum = 0;
for(int i=1; i<land.length; i++) {
land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
land[i][2] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][3]));
land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
}
for(int i=0; i<4; i++) {
sum = Math.max(sum, land[land.length-1][i]);
}
return sum;
}
}
백준 - 퇴사
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] t = new int[n];
int[] p = new int[n];
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
t[i] = Integer.parseInt(st.nextToken());
p[i] = Integer.parseInt(st.nextToken());
}
int[] dp = new int[n+1];
for (int i=0; i<n; i++) {
if (i + t[i] <= n) {
dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
}
dp[i+1] = Math.max(dp[i+1], dp[i]);
}
System.out.println(dp[n]);
}
}