yeonuel-tech
# DP1. DP 기초 개념과 좋은 백준 문제들 본문
안녕 칭구들~~(^_^) (_ _)꾸벅
위의 사진은 DP 알고리즘을 생각할 때 쉽게 연상되는 그림이거든~ 왜 그럴까??
바로 분할관점에서 바라보면 이해하기 쉬울꺼양?!? 이해 안돼도 괜찮아 밑에서 핵심 부분을 말해줄껭
오늘은 DP 알고리즘을 소개해볼까해!!
해당 글을 보기 쉽게 3가지 분류로 나눴엉
- 📌 1. DP 알고리즘의 핵심
- 📌 2. DP 알고리즘 문제
- 📌 3. 느낀점
📌 1. DP 알고리즘의 핵심
음,,, 중요한건 두 가지야!! 분할과 중복
분할은 "문제를 하위 문제들로 분할할 수 있고, 분할된 하위 문제의 결과를 통해서 상위 문제를 해결해 나갈 수 있음"을 의미해!!
중복은 "분할된 하위 문제들이 서로 중복적으로 나타나는 것"을 의미하징
그럼 일단 분할 관점에서 DP 알고리즘이 어떻게 문제에 적용되는지 간략하게 보자
위의 사진을 보면 최단 경로를 구하는 문제인데, 그 문제는 그 하위 3문제로 분할이 되는 것을 볼 수 있고 그 하위문제의 결과 값이 그 상위 문제의 결과값을 결정하는 것을 볼수 있어
더 자세히 말해볼게!!
- dp[x, y] : x -> y까지의 최단 경로 비용
- cost[start, i] : start -> i 까지 걸리는 비용
- dp[i, goal] : i -> goal 까지의 최단 경로 비용
따라서 점화식을 dp[start, goal] = min(cost[start, i] + dp[i, goal])(i => i1, i2, i3)이고
결과는 dp[start, goal] = cost[start, i1] + dp[i1, goal] = 5 + 20 = 25
자아~ 고러면 중복 관점에서 DP 알고리즘이 어떻게 적용되는지 보자규~
위에 보면 특정 식이 중복되는게 보여?!? 잘 봐바 f(1)이 여러번 나오고 f(2)도 f(3)도,,, 중복되는게 보이지??
그러면 우리는 이전에 해당 값들을 구했다면 앞으로 그 문제들을 또 계산해서 구할 필요가 있을까??!?
그치 굳이 구할 필요없지
DP 알고리즘에서는 memozation이라는 것도 있는데 하위 문제들의 결과값을 저장해 두었다가 추후에 상위 문제를 풀어갈 때 그 저장된 값들을 활용해서 해당 상위 문제를 구해!!
DP 알고리즘을 통해서 문제에서 중복이 발생하면 그 부분은 이미 이전에 구했기 때문에 계산하지않고 기록해 둔 곳에서 해당 값을 바로 사용하는 거야
그러면 위의 사진은 밑에 처럼돼~~
크흡 참 깔끔하고 효율적이당ㅋㅋㅋ!!
문제 리스트
1. 1, 2, 3 더하기
2. 1, 2, 3 더하기 5
3. 가장 긴 바이토닉 수열
4. 타일 채우기
5. RGB 거리
6. RGB 거리 2
7. 합분해
해당 글 읽기전 참고 사항
- 노트 필기 사진을 첨부했음
- 세 가지 관점에서 파악하자
1. 문제 분석 > 해당 문제에 대해 읽고 중요한 문구를 작성하면서 문제를 파악하는 과정
2. 접근법 > 예제,,,을 기반으로 문제를 어떻게 풀어나가야 하는지 생각하는 부분
3. 구현 > 코드를 구현을 하는 과정
📌 2. DP 알고리즘 문제
내가 백준 강의 들으면서 풀어본 좋은 문제들을 가지고 왔어
6가지 문제를 소개할까해(사실 내가 좀 풀이하는데 애먹은 문제들도 더러 있뎌,,,그래서 알린이 입장에서는 어려울 수도 있엉🥲🥲 고래도 어떡해 풀어야징!!🫵)
### 1. 1, 2, 3 더하기(https://www.acmicpc.net/problem/9095) ###
- 문제 분석 & 접근법
이 문제에서 중요한 포인트 2가지다
> 예제를 통해 N이 1, 2, 3으로 분할된다는 것과 중복이 나타난다는 것을 파악하는 것이다 예를 들어서 d[3]가 중복된다든지,,,
> 일반적인 관점에서 dp 점화식 정의 세워야 한다는 것
- 구현
import java.util.*;
import java.io.*;
public class Main {
static int[] d = new int[11];
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
// 초기 세팅값 0을 1, 2, 3으로 분할 하는 경우는 없는 경우 1
d[0] = 1;
for (int i=1; i<11; i++) {
if (i >= 1) {
d[i] += d[i-1];
// i가 1일 때, 밑에 코드 건너뛰기
if (i==1) continue;
}
if (i >= 2) {
d[i] += d[i-2];
// i가 2일 때, 밑에 코드 건너뛰기
if (i==2) continue;
}
if (i >= 3) {
d[i] += d[i-3];
}
}
while (t-- != 0) {
int n = Integer.parseInt(br.readLine());
sb.append(d[n]).append("\n");
}
System.out.println(sb);
}
}
### 2. 1, 2, 3 더하기 5(https://www.acmicpc.net/problem/15990) ###
- 문제 분석 & 접근법
- 구현
import java.util.*;
import java.io.*;
public class Main {
static final int limit = 100000;
static final int mod = 1000000009;
static long[][] d = new long[3+1][limit+1];
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
// 초기 세팅값
d[1][1] = 1; d[2][2] = 1; d[1][3] = 1; d[2][3] = 1; d[3][3] =1;
// dp 알고리즘 적용
for (int i=4; i<=limit; i++) {
d[1][i] = d[2][i-1] + d[3][i-1];
d[2][i] = d[1][i-2] + d[3][i-2];
d[3][i] = d[1][i-3] + d[2][i-3];
for (int l=1; l<=3; l++) d[l][i] %= mod;
}
while (t-- != 0) {
int n = Integer.parseInt(br.readLine());
long sum = d[1][n] + d[2][n] + d[3][n];
sb.append(sum%mod).append("\n");
}
System.out.println(sb);
}
}
위의 문제를 응요한 버전이다, 응용된 부분은 "연속을 어떻게 처리할지"이다
> 연속 조건을 처리하기 위해서는 두 자리를 기본단위로 생각해야함, 즉 위의 코드처럼 prev, last로 나눠서
last에 어떤 숫자가 오느냐에 따라서 prev에 올 수 있는 수들이 일부 정해진다는 것을 파악하고. 이를 통해 last값을 저장하는
공간을 만들어야 한다
위의 코드에서는 dp를 2차원 배열로 구현하여 행에는 마지막 수 1, 2, 3을 기록하고 열에는 i(0<=i<=n)을 저장하여
계산했다
내가 이 문제를 선정한 이유는 dp 알고리즘이 2차원 배열 형태로 구현되는 경우도 있음을 보여주고 싶었기 때문임
### 3. 가장 긴 바이토닉 수열(https://www.acmicpc.net/problem/11054) ###
- 문제 분석 & 접근법
- 구현
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));
int n = Integer.parseInt(br.readLine());
int[] a = new int[n];
String[] line = br.readLine().split(" ");
for (int i=0; i<n; i++) {
a[i] = Integer.parseInt(line[i]);
}
// d1 : 증가하는 부분 수열의 길이 저장, d2 : 감소하는 부분 수열의 길이 저장
int[] d1 = new int[n], d2 = new int[n];
// 증가하는 부분 수열의 최대 길이 구하기
for (int i=0; i<n; i++) {
// 자기 자신만 포함한 경우 길이 1
d1[i] = 1;
for (int j=0; j<i; j++) {
// 증가 조건 만족할 경우 길이 업데이트
if (a[j] < a[i]) {
d1[i] = d1[i] > 1 + d1[j] ? d1[i] : 1 + d1[j];
}
}
}
// 감소하는 부분 수열의 최대 길이 구하기, 감소 형태는 뒤에서 부터 접근해야 함
for (int i=n-1; i>-1; i--) {
// 자기 자신만 포함한 경우 길이 1
d2[i] = 1;
for (int j=n-1; j>i; j--) {
// 감소 조건 만족할 경우 길이 업데이트
if (a[j] < a[i]) {
d2[i] = d2[i] > 1 + d2[j] ? d2[i] : 1 + d2[j];
}
}
}
int result = 0;
for (int i=0; i<n; i++) {
result = result > d1[i] + d2[i] -1 ? result : d1[i] + d2[i] -1;
}
System.out.println(result);
}
}위의 문제는 가장 긴 증가하는 부분 수열 문제와 가장 긴 감소하는 부분 수열의 문제를 응용한 버전이다
이 문제를 선정한 이유는 항상 복잡한 문제를 풀 때는 각각의 개념을 분리해서 접근하는 방법이 유용하기 때문에 선정했다
위에 바이토닉 부분 수열을 한번에 구하는 방법이 아니라 바이토닉 부분 수열이 결국에는 증가하는 부분 수열과 감소하는 부분 수열로 나눌 수 있고 이를 각각 dp 알고리즘을 통해 최대 길이를 구한 뒤에 마지막에 더해주면서 원하는 값을 찾아낼 수 있다
### 4. 타일 채우기(https://www.acmicpc.net/problem/2133) ###
개인적으로 애먹은 문제 ㅠㅜ🤯
- 문제 분석 & 접근법
- 구현
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));
int n = Integer.parseInt(br.readLine());
int[] d = new int[n+1];
// 예외 처리
if (n<2 || n%2==1) {
System.out.println(0);
return;
}
// 기본 세팅 값
d[2] = 3;
// 누적합 계산
int acc = 0;
for (int i=4; i<=n; i+=2) {
acc += d[i-4]*2;
d[i] = d[i-2]*3 + 2 + acc;
}
System.out.println(d[n]);
}
}물론 해당 코드는 배열의 공간이 낭비되고 있음, 왜냐하면 짝수 값에 대해서만 계산이 진행되기 때문에 홀수인덱스 값들은 실질적으로 필요없는 값
고러면 위의 for()문에서 i<=n을 i<=n/2로 바꿔서 애초에 인덱스 0, 1, 2, 3, ,,, 이 짝수 0, 2, 4, 6, ,,,일때로 가정하고 풀수도 있당
이 문제를 선정한 이유는 단순하게 분할과 중복만 찾는다고 해서 DP 문제를 풀수 있는 건 아님을 알려주고 싶었기 때문이다... ㅠㅜ
여기서는 위의 노트처럼 특이한 케이스가 발생하고 그것 또한 규칙적으로 발생함을 파악하고 해당 부분을 잘 고려해서 코딩을 해야하기 때문이다
첫 번째 특이 케이스가 발생하는 시점은 3*4이다
여기서는 밑에 사진과 같은 특이 케이스가 2번 발생함을 알 수 있다
따라서 이를 적절히 처리해주어야 한다
그래서 특이 케이스를 기본 단위로 분할할 수 있음으로 이를 고려해서 DP 알고리즘을 작성해야 한다
근데,,, 여기서 끝이 아니다, 앞서 말했듯이 해당 특이 케이스가 규칙적으로 발생하고 있다
두 번째 특이 케이스가 발생하는 시점은 3*6이다
여기서는 새로운 형태의 특이 케이스 2개가 추가적으로 발생함을 알 수 있다
이를 또 적절히 처리해야 한다
세 번째 특이 케이스가 또 발생한다 3 *8
여기서도 새로운 형태의 특이 케이스가 2개 추가되는 것을 확인할 수 있다
해당 문제는 앞 전의 발생한 특이 케이스를 기준으로 분할할 수 있음으로 이를 적용하여 밑에와 같이 3*8을 분할할 수 있다
### 5. RGB 거리(https://www.acmicpc.net/problem/1149)###
- 문제 분석 & 접근법
- 구현
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));
int n = Integer.parseInt(br.readLine());
int[][] cost = new int[n+1][3], d = new int[n+1][3];
for (int i=1; i<=n; i++) {
String[] line = br.readLine().split(" ");
for (int j=0; j<=2; j++) {
cost[i][j] = Integer.parseInt(line[j]);
}
}
// c = 0이면 Red, c = 1이면 Green, c = 2이면 Blue
// 초기 세팅값
for (int c=0; c<=2; c++) {
d[1][c] = cost[1][c];
}
// dp 알고리즘 적용하기
for (int i=2; i<=n; i++) {
d[i][0] = cost[i][0] + Math.min(d[i-1][1], d[i-1][2]);
d[i][1] = cost[i][1] + Math.min(d[i-1][0], d[i-1][2]);
d[i][2] = cost[i][2] + Math.min(d[i-1][0], d[i-1][1]);
}
// 결과 찾기
int result = -1;
for (int c=0; c<=2; c++) {
if (result == -1 || result > d[n][c])
result = d[n][c];
}
System.out.println(result);
}
}해당 문제에서 중요한 부분은 "연속x"를 의미하는 조건이 제시되었다
> "연속x"
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
(밑에 그림을 참조하자)
결국에는 해당 문제를 그림으로 그려보면 밑에와 같은데
이 그림에서 알 수 있는 사실, 즉 하위 문제로 상위 문제를 해결해 나갈 수 있고 중복된 경우가 발생한다는 것이다
이를 통해 dp 알고리즘을 사용할 수 있음을 파악할 수 있다
(그림 그려서 사진 추가하기)
이후에는 해당 dp의 의미와 점화식을 정의한 다음에 구현을 하면 된다
(위의 과정은 노트 필기에 적혀있다)
### 6. RGB 거리2(https://www.acmicpc.net/problem/17404) ###
개인적으로 애먹은 문제 ㅠㅜ🤯
- 문제 분석 & 접근법
- 구현
import java.util.*;
import java.io.*;
public class Main {
// 문제에서 제시한 n(집의 개수)의 값은 1000, 각 집을 색칠하는 비용의 최대값은 1000
// 문제에서의 최대값 세팅해주기
static final int max = 1000*1000;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] cost = new int[n+1][3], d = new int[n+1][3];
for (int i=1; i<=n; i++) {
String[] line = br.readLine().split(" ");
for (int j=0; j<=2; j++) {
cost[i][j] = Integer.parseInt(line[j]);
}
}
int result = max+1;
// 고정 시킬 색깔을 fix로 지정하기
for (int fix=0; fix<=2; fix++) {
for (int c=0; c<=2; c++) {
// 색 중에서 fix 하려고 하는 색이 골라진 경우
// 고정시키기
if (c == fix) {
// 해당 fix의 비용 넣어주기
d[1][fix] = cost[1][fix];
}
// 고정되지 않은 경우는 최대값 저장해두기
else {
d[1][c] = max + 1;
}
}
// DP 알고리즘 적용하기
for (int i=2; i<=n; i++) {
d[i][0] = cost[i][0] + Math.min(d[i-1][1], d[i-1][2]);
d[i][1] = cost[i][1] + Math.min(d[i-1][0], d[i-1][2]);
d[i][2] = cost[i][2] + Math.min(d[i-1][0], d[i-1][1]);
}
// 마지막 번째의 집의 색을 골라주기
for (int c=0; c<=2; c++) {
// 마지막 번째 집이 첫번째 집의 색과 같은 경우 건너뜀
if (fix == c) continue;
// 그외의 경우 최소값 갱신
if (result > d[n][c]) {
result = d[n][c];
}
}
}
System.out.println(result);
}
}내가 개인적으로 애먹은 문제다,,, 슬펐다,,, 속상했다;;; 는 개뿔 이 문제 곱씹어 먹을거다
문제에서 제시한 조건을 잘 파악해야 한다
> "연속x"를 의미하는 조건
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
> "원형"을 의미하는 조건
1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다
N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
위의 조건이 의미하는 바는 해당 집들은 현제 원형 구조로 놓여져 있다는 것이다
원형을 해결하는 방법에는 고정시키는 방법이 있다
해당 문제를 예시로 들면 첫 번째 집과 마지막 집이 연결되어 있는 구조이다
(그림 그려서 사진 추가하기)
원형 문제는 순회하는 특징이 있기 때문에 특정한 지점을 기준으로 고정시켜서 문제를 풀 수 있다
현재 나는 첫번째 집을 고정시키고(집의 색상을 정하고) 그 이후에 문제를 풀어나가는 것으로 접근했다
따라서 위의 코드를 보면 해당 부분은 첫 번째 집의 색을 고정시키는 코드이고
// 고정 시킬 색깔을 fix로 지정하기
for (int fix=0; fix<=2; fix++) {
for (int c=0; c<=2; c++) {
// 색 중에서 fix 하려고 하는 색이 골라진 경우
// 고정시키기
if (c == fix) {
// 해당 fix의 비용 넣어주기
d[1][fix] = cost[1][fix];
}
// 고정되지 않은 경우는 최대값 저장해두기
else {
d[1][c] = max + 1;
}
}
//,,, (코드 생략) ,,,
}마지막에는 마지막 번째의 집의 색상을 고를 때, 첫 번째 집의 색을 건너뛰고 고르는 식으로 처리했다
// 마지막 번째의 집의 색을 골라주기
for (int c=0; c<=2; c++) {
// 마지막 번째 집이 첫번째 집의 색과 같은 경우 건너뜀
if (fix == c) continue;
// 그외의 경우 최소값 갱신
if (result > d[n][c]) {
result = d[n][c];
}
}
나머지 코드 구현은 기존의 문제 RPG 문제와 같다
### 7. 합분해(https://www.acmicpc.net/problem/2225) ###
- 문제 분석 & 접근법
개인적으로 애먹은 문제 ㅠㅜ🤯
- 구현
import java.io.*;
public class Main {
static long mod = 1000000000L;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]), k = Integer.parseInt(line[1]);
long[][] d = new long[k+1][n+1];
// 초기 세팅값, 숫자 i를 한자리로 나눈 경우는 자기 자신만 해당하므로 1
for (int i=0; i<=n; i++) {
d[1][i] = 1;
}
// 알고리즘 적용
// i : 몇 개로 분할했는지, 마지막에 k개까지 분할해나감
for (int i=2; i<=k; i++) {
// j : 합을 의미하며 n까지 늘려감
for (int j=0; j<=n; j++) {
// s : 하위 문제에서 만들었던 합을 의미함, 즉 마지막 수는 이미 선택했다고 가정하고
// 그 하위의 문제 s의 합을 i-1로 분할한 경우를 의미함
// 예를 들어서, d[3][5]의 경우 d[2][0] + ,,, + d[2][5]으로 분할할 수 있으며
// 순서대로 각각의 d[i-1][s]는 5를 선택한 경우, 4를 선택한 경우,,, 0을 선택한 경우로 매칭됨
for (int s=0; s<=j; s++) {
d[i][j] += d[i-1][s];
}
d[i][j] %= mod;
}
}
System.out.println(d[k][n]);
}
}이 문제가 알고리즘 기초 1편 강의 중에서 가장 어려운 문제이다
그 이유는 아마 마지막 수(last)는 0~n까지 선택할 수 있는 것이 고정되어 있고 마지막 수를 선택함에 따라 그 하위 문제(n-last)(이때 last는 내가 선택한 마지막 수)로 분할할 수 있다는 것을 알아차리기 어려웠기 때문인 것 같다
뭔가 다른 문제들 처럼 한눈에 dp 점화식이 세워지지 않았고 좀 더 고민을 해봐야 한다 예를 들어 내가 그린 테이블 그림 처럼
특정 문제를 풀어감에 있어서 어떤 문제들로 분할할 수 있는지를 세부적으로 알아냈어야 했다
위의 그림은 n = 5이고 k = 3일 때, 즉 "0~5까지의 정수 3개를 더해서 그 합이 5가 되는 경우의 수를 구하는 것이다"
일단 정수 3 개로 나누는 것은 정수 2개로 나누는 문제와 마지막에 어떤 수가 오는지에 따라 풀수 있다
또한, 정수 2개로 나누는 문제는 정수 1개로 나누는 문제와 마지막에 어떤 수가 오는지로 풀 수 있다
마지막으로 정수 1개로 나누는 문제로 기초 베이스를 시작할 수 있다
위의 문장을 보기 좋은 형태로 나타내보면 밑에와 같음
이 그림을 보면 해당 문제는 백트랙킹으로도 풀 수 있음을 알 수 있음
결국에는 내가 생각하는 이 문제의 핵심은 바로 위의 그림처럼 문제를 하위 문제들로 분할 할 수 있으며 분할된 문제는 그 상위 문제의 마지막 수에 영향을 받는 다는 것을 파악하는 것이다
그래서 코드 구현 과정에서도 해당 부분을 추가해주었다
// 알고리즘 적용
for (int i=2; i<=k; i++) {
// 문제에서 합이 j인 것을 의미하며
for (int j=0; j<=n; j++) {
// 그 하위 문제에서는 합들이 0~j까지의 경우의 수만 추가하는 것을 확인할 수 있음
for (int l=0; l<=j; l++) {
d[i][j] += d[i-1][l];
}
d[i][j] %= mod;
}
}
📌 3. 느낀점
결국에는 문제로부터 "분할과 중복"을 찾아내는 것이 중요해!! 그래야 이 문제를 DP로 풀어나가야 겠다고 발상할 수 있기 때문이야
그리고 그 문제들을 일반적인 관점에서 "점화식 정의"을 찾아내는 것이 또 중요하지
그리고 그걸 토대로 "구현"을 하면 끄으으읕!!
그리고,, 이게 나같이 알고리즘 초보자라면 직접 그림을 그려보면서 DP 알고리즘이 어떻게 동작하는지도 파악하는게 정말 좋아!!
시간은 오래 걸리더라도 정확하고 꼼꼼하게 하는게 최고야 최고!!
핵심 : "분할과 중복" > "점화식 정의" > "구현"
잠깐 칭구야 좋아요 좀 눌러줭 ㅠㅜ ㅋㅋ 그러면 뿌듯해서 더 열심히 포스팅할꺼 같아!!
고럼 20,000 👋 👋 👋 (근데 이렇게 작성해 두니깐 의외로 뿌듯하다)
'Data Structure & Algorithms' 카테고리의 다른 글
| 구슬 탈출 2 (백준 13460) - 브루트 포스(비트 마스크)👨🏻💻 (1) | 2023.06.07 |
|---|
