이번 주 백준 문제 유형이 자료구조 수업 때 배우지 않은 DP이기에 이를 공부한 바탕으로 DP를 정리해보려 한다.
두괄식으로 먼저 DP를 정의한 문구들을 보고 가자.
DP란 ?
→ *메모이제이션(Memoization) 기법을 이용하며 '하나의 문제는 단 한 번만' 풀도록 하게 하는 알고리즘
* 계산했던 것을 메모리 공간에 기억해 두고, 같은 식을 써야한다면 앞에서 기억한 것을 재사용하는 기법
분할 정복 기법과 DP의 차이점
분할 정복 : 큰 문제를 작은 부분 문제로 나누고, 그 하위 문제를 독립적으로 해결하고 이를 합쳐서 원래 문제를 해결함
동적 계획법(DP) | 분할 정복 | |
중복되는 문제 | O | X |
메모이제이션 | O (중복 문제의 결과를 저장하고 재활용함) |
X |
문제 분할 방식 | 문제의 크기와 형태에 따라 다름 | 동일한 크기의 하위 문제로 나눔 |
예시 | 피보나치 수열, 최단 경로 문제, 배낭 문제.. | 퀵 정렬, 병합 정렬, 큰 수의 곱셈.. |
즉, 분할 정복 기법은 동일한 문제를 다시 푼다는 단점이 존재함. (퀵 정렬, 병합 정렬.. 제외)
- 정렬은 왜 위 단점에 해당되지 않는가?
-> 정렬의 경우, 피봇이 옮겨지며 나누어지는 부분을 "이전 문제와 같은 경우로 취급하는 것이 아닌 새로운 문제로 받아들이기 때문"
f(6) = f(5) + f(4)
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
이처럼 같은 계산이 여러 번 반복된다.
- 피보나치수열의 점화식
level 0 = 1
level 1 = 2
level 2 = 4
level 3 = 8
… 2^n 개씩 나누어진다.
일반적인 재귀함수로 피보나치 수열 계산
public class Main {
public static int dp(int x){
if(x == 1) return 1;
if(x == 2) return 1;
return dp(x-1) + dp(x-2);
}
public static void main(String[] args) {
System.out.println(dp(10));
}
}
동일한 문제를 계속 사용하게 되는데, 그때마다 또다시 계산하고 있다.
만약 10이 아닌, 46이 들어간다면? 50은 ?
2^46, 2^50..
수행시간 = O(2^n) = 완전 구데기
DP를 사용하여 풀기
먼저 DP를 쓰려면 ?
문제만 보고 어떻게 DP인지 알아내는가
입력 x가 return dfs(x-1) + dfs(x-2) + dfs(x-2);에서 1이 될때까지 계속 카운팅 되고 있음. ⇒ 비효율적
- 큰 문제를 작은 문제로 나눌 때(분할 정복)
- 작은 문제에서 구한 정답이 큰 문제에서도 동일하게 쓰일 때
두가지 조건을 충족해야 DP를 적용할 수 있다.
DP 문제 풀이를 위한 2가지의 접근 방법
- 탑다운 방식(Top - down) = 순환적 알고리즘
- 바텀업 방식(Bottom - up) = 반복적 알고리즘
탑다운 방식
public class Main {
static int[] cache = new int[100];
public static int dp(int x){
if(x == 1) return 1;
if(x == 2) return 1;
if(cache[x] != 0) return cache[x];
return cache[x] = dp(x-1) + dp(x-2);
}
public static void main(String[] args) {
System.out.println(dp(46));
}
}
일반적인 재귀함수 코드와 달리 계산했던 값을 저장하는 배열이 생긴 모습을 볼 수 있다.
바텀업 방식
public class Main {
static int[] cache = new int[100];
public static int dp(int x){
cache[0] = 0;
cache[1] = cache[2] = 1;
for(int i= 2; i<= x; i++){
cache[i] = cache[i-1] + cache[i-2];
}
return cache[x];
}
public static void main(String[] args) {
System.out.println(dp(10));
}
}
이처럼 코드를 작성하면, d[3] = 2, d[4] = 3… 이렇게 한 번 계산해두면, d[1] + d[2] 를 하지 않고 d[3] = 2 를 바로 기억하여 또다시 계산할 필요가 없음
더 내려가지 않고, 기억해 둔 값을 쓰면 됨.
수행시간 = O(n) = 높이에 비례
백준 11727번 (2×n 타일링 2)
별도의 문제에 대한 설명은 하지 않고 위 사진으로 설명을 마치겠습니다.
상기 문제의 경우 DFS를 이용하여 풀 수도 있다.
- DFS 방식
import java.util.Scanner;
public class Main {
public static int dfs(int x){
if(x<=1) return 1;
return dfs(x-1) + dfs(x-2) + dfs(x-2);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int val = sc.nextInt();
System.out.println(dfs(val));
}
}
범위가 (1 ≤ n ≤ 1000) 이기에 1000을 넣을 시 왕왕 오래 걸림.
- DP 방식
import java.util.Scanner;
public class Main {
static int[] d = new int[1001];
public static int dp(int x) {
if (x <= 1) return 1;
if (d[x] != 0) return d[x];
d[x] = (dp(x - 1) + 2 * dp(x - 2)) % 10007;
return d[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int val = sc.nextInt();
System.out.println(dp(val));
}
}
'Computer Science > Algorithm' 카테고리의 다른 글
[백준] 3151, 합이 0 (Swift) (2) | 2024.01.27 |
---|---|
[백준] 2644, 촌수계산(C++, BFS) (0) | 2023.09.02 |
[백준] 13414, 수강신청 (C++, 해시맵) (0) | 2023.08.10 |
[C언어] 표준 입력 함수, scanf() 함수의 오류 찾기 (0) | 2023.05.31 |
[백준] 2579번, 계단 오르기 (Java/자바) 동적 계획법 실습 (0) | 2023.05.26 |