북마크로 복습 문제집 만들기
코드트리에는 문제마다 공유하기 버튼 왼쪽에 문제를 마킹할 수 있는 북마크 기능이 존재한다.
이를 이용하면 알고리즘 분류별로 개념이 흔들렸거나 나중에 다시 풀어볼만한 문제들을 문제집처럼 만들어서 관리할 수 있다.
이번주는 DP니까 DP 폴더를 생성해서 정리해 주었다.
맨 왼쪽 섹션을 열어보면 북마크가 있고 거기서 추가된 문제를 폴더별로 확인할 수 있다.
원래는 회고를 적을 때 문제 옆에 임의로 아이디어가 좋았거나 읽어볼만한 (다시 보기) 와
어려워서 뭔가 다음에 다시 풀 수 없을 거 같아 여러 번 읽어야할 문제는 (다시 풀기) 등으로 나타냈었는데
코드트리 문제에 한해서는 북마크 기능을 활용해서 시간순으로 목록이 정렬되니 일주일 뒤나 2주 뒤에 풀면 좋을 것 같다.
따로 메모할 수는 없으니 귀찮아도 지웠다가 다시 추가하는 식으로 해 놓을 예정이다.
상세 학습 계획
이번주는 dp를 공부하기로 했다. 지금까지 완전탐색, 트리, 이진트리 개념을 공부했고
트리의 정보를 부모와 자식간 전파할 때, 최적화 방법으로 dp를 사용해서 재사용을 고민했으니
dp의 기본 개념은 알고 있으니 본격적으로 dp 문제를 풀기에 적합하다고 판단했다.
문제마다
1) 상태 정의와 전이 기준 선택
2) 상태 전이 과정 따라가며 초기값, 점화식 틀 잡기
3) 가능하다면 상태 압축
위의 프로세스를 따라가며 어떻게 이 점화식이 유도 되었는지 정리하는 방향으로 문제를 풀이하고 정리 및 요약을 한다.
문제 - 사각형 채우기 (다시 보기)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rectangle-fill-3/description
사각형 채우기 3 설명 | 코드트리
사각형 채우기 3를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static final long MOD = 1_000_000_007;
public static void main(String[] args) throws IOException{
int N = read();
// i길이까지 꽉 채우는 모양으로 끝나는 경우
long[] dp1 = new long[N+1];
// ㄴ모양으로 1*1칸 위로 비우는 모양으로 끝나는 경우
long[] dp2 = new long[N+1];
dp1[0] = 1;
dp1[1] = 2;
dp2[0] = 0;
dp2[1] = 1;
for(int i = 2; i<=N; i++){
dp2[i] = (dp1[i-1] + dp2[i-1]) % MOD;
dp1[i] = ((2*dp1[i-1]) % MOD + dp1[i-2] + (2*dp2[i-1]) % MOD) % MOD;
}
System.out.print(dp1[N]);
}
}사고의 흐름
상태 기준을 정하고 그걸 따라가며 나오는 형태가 뭐가 있는지 살펴보는 방향으로 점화식을 도출했다.
문제 조건에서 N이 진행됨에 따라 커지는 건 가로 길이이며 이걸 idx로 놓는다.
그리고 따라가다보면 길이 i에서 끝나는 상태가 2가지이다.
1) i에서 꽉채워져서 끝나는 경우,
2) i에서 위나 아래쪽이 한칸 빈 모양으로 끝나는 경우
-> 각자 dp1, dp2로 놓는다. 크기는 계산의 용이성을 위해 1-based, long 으로 설정
dp2 점화식 도출
dp1은 길이 i에서 2가지 상태가 존재하기 때문에 2번상태에 해당하는 dp2를 먼저 정의하고 dp1을 구해야 한다.
한 칸 튀어나온 frontier state를 다 쓰면 길어지니 아래서부터 ㄴ자, ㄴ자 모양이라 한다.
dp2는 길이 i에서 ㄴ자 모양으로 끝날 때의 방법의 갯수를 나타낸다.
-> 하지만 실제로는 아래가 빈 모양도 나오는데 이는 ㄴ자의 경우와 완전히 대칭이기 때문에 한 방향만 대표 상태로, 즉
ㄴ자의 경우만 압축해서 저장하고 dp1의 점화식에서 2* dp2 [ i - 1 ]로 표현할 수 있음.
idx = 0
-> 어떻게 놔도 1칸 튀어나오게 놓을 수 없음 ( 0 )
idx = 1
-> 1*1 아래 한칸 놓으면 ㄴ자 완성 가능
idx = 2
-> 1에서 꽉찬 사각형 + 1*1 아래에 놓으면 ㄴ자 완성 ( dp1 [ i - 1 ] )
+ 1의 dp2 상태에서 빈칸 방향으로 가로 1*2를 이어 붙이면 반대 방향의 dp2 state가 유지되므로 ( dp2 [ i - 1 ] )
-> 위 빈 -> 아래 빈 -> 위 빈 -> 아래 빈 이렇게 번갈아서 나타나게 됨.
dp1 점화식 도출
idx = 0
-> 아무것도 안놓는거 1가지 ( 1 )
idx = 1
-> 1*1 2개 놓는거 + 1*2 1개 세로로 놓는거 = 총 2가지
idx = 2
-> 바로 전 idx에서 꽉채우는 모양 에서 채운다고 하면 세로 1*2를 채워야 하니까 ( 2*dp1 [ i -1 ] )
+ 가로로 1*2 1개씩 2개 놓기 (dp1 [ i - 2 ] )
+ 바로 전 idx에서 위아래 한칸씩 빈 모양이면 아래에다가 1*2, 위에 1*1 랑 위에 1*2, 아래에 1*1 한거 2가지 ( 2 * dp2[ i - 1 ] )
점화식 정리
dp2[i] = (dp1[i-1] + dp2[i-1]) % MOD;
dp1[i] = ((2*dp1[i-1]) % MOD + dp[i-2] + (2*dp2[i-1]) % MOD) % MOD;총 시간복잡도는 O(N)이다.
문제 - 서로 다른 BST
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-number-of-unique-bst/description
서로 다른 BST 개수 세기 설명 | 코드트리
서로 다른 BST 개수 세기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
long[] dp = new long[N+1];
dp[0] = 1;
if(N >= 1)
dp[1] = 1;
for(int i = 2; i<=N; i++){
for(int r = 1; r<=i; r++){
dp[i] += dp[r-1] * dp[i-r];
}
}
System.out.print(dp[N]);
}
}사고의 흐름
BST니까 노드는 distinct하고,
최상위 루트를 고정시켜 놓으면 왼쪽 서브트리의 값 구간과 오른쪽 서브트리의 값 구간이 정해진다.
-> 최상위 루트가 고정되면 왼쪽도 고정되고 왼쪽이 고정되면 오른쪽도 고정
-> 가능한 모든 최상위 루트에 대해서 왼쪽 서브트리의 모든 경우를 해보면 될 거 같다.
또한 내부 서브트리에 대해서
dp는 1부터 i 까지의 가능한 BST의 경우의 수를 저장하고 있으므로
1->N 순서로 진행하면 값을 재사용 가능하다.
초기값 정하기
빈 서브트리는 빈 상태의 경우 1가지이기 때문에 1로 함. -> dp[ 0 ] = 1
노드가 1 하나인 서브트리는 1가지이다. -> dp[ 1 ] = 1
점화식 도출
BST는 이진트리이기 때문에 자식이 2개씩 있고 한 자식의 경우에 다른 자식의 경우 전부가 조합 가능하기 때문에
-> 부모 = 왼쪽 subtree 경우의 수 * 오른쪽 subtree 경우의 수
dp[i] = dp[i-1] * dp[N-i]상태 전이
이제 최상위 노드가 될 수 있는 모든 후보에 대해 root = [ 1, N ]
최상위 루트 노드가 정해졌을때 왼쪽 subtree의 root 후보는 left = [ 1, root ] 가 된다.
오른쪽 subtree는 왼쪽이 정해지면 굳이 볼 필요 없으므로 이를 코드로 나타내면
for(int i = 2; i<=N; i++){
for(int r = 1; r<=i; r++){
dp[i] += dp[r-1] * dp[i-r];
}
}문제 - 사각형 채우기 2
https://www.codetree.ai/ko/trails/complete/curated-cards/test-rectangle-fill-2/description
사각형 채우기 2 설명 | 코드트리
사각형 채우기 2를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
import java.util.*;
import java.io.*;
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static final int MOD = 10_007;
public static void main(String[] args) throws IOException{
int N = read();
int[] dp = new int[N+1];
dp[0] = 1;
dp[1] = 1;
if(N > 1)
dp[2] = 3;
for(int i= 3; i<=N; i++){
dp[i] = (dp[i-1] + (2*dp[i-2]) % MOD) % MOD;
}
System.out.print(dp[N]);
}
}
사고의 흐름
상태 전이의 기준은 가로 길이의 위치이다. 이를 idx로 놓고 생각한다.
idx = 0
-> 아무것도 없는 상태 1가지 -> dp[0] = 1
idx = 1
-> 1*2를 세로로 놓는 것 1가지 -> dp[1] = 1
idx = 2
-> 1*2를 세로로 2개 , 1*2를 가로로 2개, 2*2 네모 1개 -> dp[2] = 3
풀이 : 점화식 도출
초기값은 위에서 구한 것을 그대로 쓸 것이다.
일반화를 위해 현재 가로 길이가 i 일 때를 생각해보면, 가로 길이 종류상 놓을 수 있는 것은 2가지가 있다.
길이 1의 경우 : 1*2를 세로로 놓는 것
길이 2의 경우 : 1*2를 가로로 놓기 , 2*2 사각형 놓기
결과가 i가 되어야 하므로 결국 식으로 나타내게 되면 길이가 i일때 경우의 수는 다음과 같다.
dp[i] = dp[i-1] + 2 * dp[i-2]N = 3 이상부터 채워나간 후 dp[ N ]을 출력하면 된다. (1-based size로 잡았으므로)
문제 - 정수 사각형의 최솟값의 최대 (minimax dp)
정수 사각형 최솟값의 최대 설명 | 코드트리
정수 사각형 최솟값의 최대를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[][] board = new int[N][N];
for(int i= 0; i<N; i++){
for(int j = 0; j<N; j++){
board[i][j] = read();
}
}
int[][] dp = new int[N][N];
dp[0][0] = board[0][0];
for(int j = 1; j<N; j++){
dp[0][j] = Math.min(dp[0][j-1], board[0][j]);
}
for(int i = 1; i<N; i++){
dp[i][0] = Math.min(dp[i-1][0], board[i][0]);
}
for(int i = 1; i<N; i++){
for(int j = 1; j<N; j++){
dp[i][j] = Math.max(Math.min(dp[i-1][j], board[i][j]), Math.min(dp[i][j-1], board[i][j]));
}
}
System.out.print(dp[N-1][N-1]);
}
}사고의 흐름
(1,1) -> (N,N) 이 목표인데 지나는 값의 최솟값을 최대로 갱신할 때 그 결과값을 출력하는 문제이다.
조건 그대로 풀어서 쓰면 된다.
dp 초기값은 0,0은 그대로 가져가고 첫번째 행과 열은 경로가 문제 조건상 한가지밖에 존재하지 않으므로
min으로만 갱신해서 dp 초기값을 설정한다.
풀이
1) 경로를 선택할때는 최소로
2) 모든 경로를 취합해서 해당 도착지 좌표에서의 값은 최대로
경로는 왼쪽에서 오는 것 ( [ i ][ j - 1 ] ) 과 위에서 오는 것 ( [ i - 1 ][ j ] ) 이 있고 도착지는 현재 board이다.
그리고 여기서는 경로가 2가지 뿐이니 그 두가지중 max를 고르면 된다.
A = min(dp[i-1][j], board[i][j])
B = min(dp[i][j-1], board[i][j])
dp[i][j] = max(A, B)문제 - 정수 사각형 최장 증가 수열(DAG dp)
정수 사각형 최장 증가 수열 설명 | 코드트리
정수 사각형 최장 증가 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N;
static int[][] board;
static int[][] dp;
static int[][] outDegree;
//북동남서
static int[] di = {-1,0,1,0};
static int[] dj = {0,1,0,-1};
public static void main(String[] args) throws IOException{
N = read();
board = new int[N][N];
dp = new int[N][N];
outDegree = new int[N][N];
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
board[i][j] = read();
}
}
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
for(int d = 0; d<4; d++){
int ni = i + di[d];
int nj = j + dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= N)
continue;
if(board[ni][nj] > board[i][j])
outDegree[i][j]++;
}
}
}
Queue<int[]> q = new ArrayDeque<>();
for(int i = 0; i<N; i++){
for(int j= 0; j<N; j++){
if(outDegree[i][j] == 0)
q.add(new int[]{i,j});
}
}
int ans = 0;
while(!q.isEmpty()){
int size = q.size();
ans++;
for(int s = 0; s<size; s++){
int[] cur = q.poll();
int ci= cur[0];
int cj= cur[1];
// 역방향이니까 현재보다 작은 값 찾기
for(int d = 0; d<4; d++){
int ni = ci + di[d];
int nj = cj + dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= N)
continue;
if(board[ni][nj] >= board[ci][cj])
continue;
if(--outDegree[ni][nj] == 0){
q.add(new int[]{ni,nj});
}
}
}
}
System.out.print(ans);
}
}사고의 흐름
N*N 크기의 보드가 있을때 아무곳이나 시작점으로 잡아서 다음 칸의 값이 현재 값보다 클 때만 이동 가능한 경로로 이동할 때 해당 경로의 최장 경로 값을 구하는 문제이다.
각 지점을 어떤 노드로 보고 간선 길이를 1이라고 하고,
그래프는 작은 값 -> 큰 값으로 정방향 구성하고 탐색만 역간선 방향으로 수행한다.
다음 칸을 지정하는 명확한 기준이 존재하기 때문에 사이클이 없는 그래프에서의 최장 경로 탐색 문제로 바꿀 수 있다.
다시 말해, 현재 -> 미래 로 가게 되면 어딜 골라야 할지 애매한데 미래 -> 현재 뱡향,
즉 역방향 탐색을 하게 되면 시작점은 여러개일 수 있어서 알 수 없지만, 끝점은 명확하게 판별할 수 있다.
사실 DFS + dp로 모든 시작점을 선택한 뒤 제일 긴 경로를 ans에 최대로 갱신하는 방법으로 풀 수도 있다.
처음에는 단순히 재귀에 함수 call 오버헤드가 불리해 보여 이거로 고른거지만 찾아보니 Java 스펙상 근거가 있었다.
-> Java는 디버깅 및 스택 트레이스 보존을 위한 정확한 호출 스택을 중요하게 여겨서 Tail Call Optimization(TCO, 재귀 스택 최적화)가 JVM 스펙에서 보장하지 않으며, 재귀 깊이를 안전하게 믿을 수 없다는 점이다.
풀이
먼저 입력을 받은 격자 보드에 대해 모든 점에서의 나가는 간선 갯수인 outDegree(진출차수)를 구한다.
그리고 진출차수가 0인 지점은 더이상 문제 조건으로 경로를 이어나갈 수 없는 끝점의 후보들이고
역방향 탐색이므로 이를 Queue에 시작점으로 삽입한다.
현재 BFS는 DAG의 끝점들을 layer 단위로 제거하는 Kahn 위상정렬 기반 탐색이다.
한 layer가 제거될 때마다 경로 길이가 1 소모되므로
총 layer 수가 최장경로의 길이가 된다.
-> 구현 상으로는 늘어나는 것처럼 보이지만 개념상으로는 역간선 탐색이기 때문에 제거되는 상태이다.
따라서 Queue의 현재 크기는 BFS layer의 크기인데
BFS layer 단위로 처리를 해 주고 ans++
-> 더 깊은 깊이(더 긴 경로)가 나타날때마다 ans가 1씩 커지게 되고
Queue가 비고 더이상 탐색할 경로가 없어지는 종료 상태에 이르면
ans 가 곧 해당 격자에서의 가장 긴 경로의 길이 값이 되기 때문이다.
문제 - 정수 사각형 차이의 최소 2(minimax, 다시 풀기)
정수 사각형 차이의 최소 2 설명 | 코드트리
정수 사각형 차이의 최소 2를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N;
static int[][] board;
static List<Integer> arr = new ArrayList<>();
static int[] di = {1,0};
static int[] dj = {0,1};
static boolean bfs(int min, int max){
boolean[][] v = new boolean[N][N];
Queue<int[]> q = new ArrayDeque<>();
if(board[0][0] < min || board[0][0] > max)
return false;
q.add(new int[]{0,0});
v[0][0] = true;
while(!q.isEmpty()){
int[] cur = q.poll();
int ci = cur[0];
int cj = cur[1];
if(ci == N-1 && cj == N-1)
return true;
for(int d = 0; d<2; d++){
int ni = ci + di[d];
int nj = cj + dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= N)
continue;
if(board[ni][nj] < min || board[ni][nj] > max)
continue;
if(v[ni][nj])
continue;
v[ni][nj] = true;
q.add(new int[]{ni,nj});
}
}
return false;
}
public static void main(String[] args) throws IOException{
N = read();
board = new int[N][N];
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
board[i][j] = read();
arr.add(board[i][j]);
}
}
Collections.sort(arr);
int l = 0;
int r = 0;
int ans = 101;
while(l<arr.size() && r<arr.size()){
int min = arr.get(l);
int max = arr.get(r);
// 지금 값으로 가능하면
// l++를 해야 max-min이 더 작아짐
// 최소로 갱신하는거니까
if(bfs(min, max)){
ans = Math.min(ans, max-min);
l++;
}
else{
r++;
}
}
System.out.print(ans);
}
}사고의 흐름
dp 챕터에 있어서 dp로 풀려고 했는데 상태가 2개인데 이걸 어떻게 표현하지, 아님 줄이지에서 생각이 안나가서
격자에 있는 값을 TreeSet으로 distinct 하게 오름차순으로 정렬하고
투포인터로 [ 최솟값, 최댓값 ] 구간을 정해서 문제 조건을 만족하는 경로가 해당 구간을 만족하는지에 대해 구하고 (BFS)
만약 만족한다면 최솟값을 증가시켜서 max - min 값을 최소화시키는 방향으로 풀었다.
-> 시간복잡도는 K가 등장하는 값의 범위라고 한다면 O( (K + log K) * N^2 )
공식 해설 참조
min 후보를 고정하고, 그 안에서 가능한 경로의 max를 최소화하는 방향으로 발상을 시작한다.
사용할 수 있는 칸 : board[ i ][ j ] >= min
이동은 오른쪽과 아래 방향만 가능
dp[ i ] [ j ] = (1, 1) -> ( i, j ) 까지 올 때 경로에서의 최댓값의 최솟값
문제 - 최장 증가 수열 길이 구하기(LIS)
최대 증가 부분 수열 설명 | 코드트리
최대 증가 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
import java.util.*;
import java.io.*;
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] a = new int[N];
for(int i= 0; i<N; i++){
a[i] = read();
}
List<Integer> li = new ArrayList<>();
for(int n : a){
if(li.isEmpty() || li.get(li.size()-1) < n){
li.add(n);
}
else{
int idx = Collections.binarySearch(li, n);
if(idx < 0)
idx = -(idx+1);
li.set(idx, n);
}
}
System.out.print(li.size());
}
}정리
O(N log N)으로 길이만 구할때 쓰는 템플릿이다.
빈 오름차순으로 정렬될 list를 두고 이분탐색으로 현재 원소를 알맞은 위치에 스왑/추가 한다.
풀이
계속 증가해야 하므로 현재 원소가 list의 끝 원소보다 크면 그냥 끝에 삽입하고
아니라면 이분탐색으로 위치를 찾아서 List.set(인덱스, 값) 으로 스왑한다.
만약 이분탐색 결과가 음수가 나온다면 맨 앞에 넣어야 하므로 Collections.binarySearch(찾을 곳, 위치 찾을 값)의 결과값 형식을 바꿔서 idx를 갱신하고 처리해야 한다.
실제 LIS 구할때는?
그럼 길이만 구하는게 아니라 LIS 실제 값이 필요하다고 하면 N log N 풀이는 현재 길이 idx+1의 마지막 인덱스를 저장하는 배열과이전 원소를 link 해주는 prev 배열이 필요하다.
-> 지금은 축약된 for문으로 구현했지만 이때는 원래의 for 문이 필요하다. ( i = n의 idx, idx = 이분탐색 결과값 )
// 현재 길이 idx+1 의 마지막 원소 인덱스
lisIdx[idx] = i;
// 이전 원소 연결
if(idx > 0){
prev[i] = lisIdx[idx - 1];
}
사실 실제 LIS 배열을 구한다고 하면
O(N^2)이라 조금 느리지만 값을 갱신할 때마다 prev 배열만 쓰면 되는 DP 풀이가 직관적이라 할 수 있다.
문제 - 최대 감소 부분 수열
최대 감소 부분 수열 설명 | 코드트리
최대 감소 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] arr = new int[N];
for(int i= N-1; i>=0; i--){
arr[i] = read();
}
int[] dp = new int[N];
for(int i = 0; i<N; i++){
dp[i] = 1;
for(int j = 0; j<i; j++){
if(arr[j] < arr[i]){
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
}
int ans = 0;
for(int n : dp){
ans = Math.max(ans, n);
}
System.out.print(ans);
}
}
최대 감소 수열의 길이를 구하라는데 이거 그냥 입력을 뒤집고 똑같이 해주면 된다.
이번에는 dp 방식으로 O(N^2)에 풀었다.
문제 - 최대 점프 횟수
최대 점프 횟수 설명 | 코드트리
최대 점프 횟수를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] a = new int[N];
for(int i = 0 ;i<N; i++){
a[i] = read();
}
int[] dp = new int[N];
for(int i= N-1; i>=0; i--){
int jump = a[i];
for(int j = i+1; j<=i+jump && j<N; j++){
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
System.out.print(dp[0]);
}
}사고의 흐름 및 풀이
dp[ i ] = i에서 시작했을때 앞으로 가능한 최대 점프 횟수
로 정의하고 풀었다.
그러면 최적해는 현재 1번 점프 + 다음 위치의 최적해가 된다.
-> dp[i] = Math.max(dp[i], dp[j]+1);
따라서, 미래의 값이 먼저 계산되어야 하므로 뒤에서부터 순회를 돌아야 한다.
문제 - 증가했다가 감소하는 수열 (bitonic)
증가했다가 감소하는 부분 수열 설명 | 코드트리
증가했다가 감소하는 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] in = new int[N];
int[] rev = new int[N];
for(int i = 0; i<N; i++){
int cur = read();
in[i] = cur;
rev[N-i-1] = cur;
}
int[] dp1 = new int[N];
int[] dp2 = new int[N];
Arrays.fill(dp1, 1);
Arrays.fill(dp2, 1);
for(int i = 0; i<N; i++){
for(int j = i+1; j<N; j++){
if(in[i] < in[j])
dp1[j] = Math.max(dp1[j], dp1[i]+1);
if(rev[i] < rev[j]){
int ni = N-1-i;
int nj = N-1-j;
dp2[nj] = Math.max(dp2[nj], dp2[ni]+1);
}
}
}
int ans = 0;
for(int i = 0; i<N; i++){
ans = Math.max(dp1[i] + dp2[i]-1, ans);
}
System.out.print(ans);
}
}사고의 흐름
문제 조건을 보면 증가했다가 감소하기, 증가만 하기, 감소만 하기 3가지가 가능하다.
따라서 한 피봇을 두고
거기까지 봤을때 증가하는 수열의 최대 길이 + 거기서부터 시작하는 감소하는 수열의 최대 길이 -1
를 보면 된다.
감소하는 수열의 최대 길이는 거꾸로 입력받은 배열의 증가하는 수열의 최대길이와 동치이다.
풀이
증가하는 수열은 LIS 구하듯 구하고, 감소하는 수열은 똑같이 구하긴 하는데
마지막에 합할때 기준은 정방향 입력이기 때문에 그걸 고려해서
인덱스를 변환하고 dp를 갱신해 줘야 한다.
if(rev[i] < rev[j]){
int ni = N-1-i;
int nj = N-1-j;
dp2[nj] = Math.max(dp2[nj], dp2[ni]+1);
}피봇을 0 <= pivot <= N-1에 대해
dp1[ pivot ] + dp2[ pivot ] - 1 의 최댓값을 갱신하고 출력하면 된다.
문제 - 무한 배낭
https://www.codetree.ai/ko/trails/complete/curated-cards/intro-coin-change/description
동전 거슬러주기 설명 | 코드트리
동전 거슬러주기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] coin = new int[N];
int M = read();
int INF = M+2;
for(int i =0; i<N; i++){
coin[i] = read();
}
int[] dp = new int[M+1];
Arrays.fill(dp, INF);
dp[0] = 0;
for(int i = 0; i<N; i++){
int cur = coin[i];
for(int j = cur; j<=M; j++){
dp[j] = Math.min(dp[j], dp[j-cur]+1);
}
}
System.out.print(dp[M] == INF ? -1 : dp[M]);
}
}사고의 흐름
어떤 금액 M을 동전의 종류가 N개 있고 각 동전은 무한히 사용할 수 있을 때, M을 거슬러주기 위한 (구성하기 위한) 최소 동전 갯수를 구해야 하는 문제이다. 단, 금액 M을 구성할 수 없으면 -1을 출력하기.
M의 범위가 크지 않으므로 M을 dp의 인덱스로 사용하기
-> 종류가 N개 있으나 각 종류당 동전 사용 가능 갯수가 무한이므로 무한 배낭이라 봐야 함
풀이
dp[ m ] = 금액 m을 구성하는 동전의 최소 갯수 로 정의
금액 0원을 구성하기 위한 갯수는 0개 이고 (dp [ 0 ] = 0 )
dp 전체는 금액 m을 구성하기 위한 최대 갯수로 초기화해놓는다.
-> INF = m+1 ( 최대 갯수 = m / 1 (동전 값어치가 1일때 최대 갯수이므로 ) + 1)
현재 동전 종류가 cur이라면 dp [ j - cur ] + 1 (cur 하나 쓰는거 의미) 가
dp [ j ] 보다 작다면 dp [ j ] = dp [ j - cur ] + 1로 상태를 전이한다.
문제 - 0/1 배낭 상태압축
부분 수열의 합이 M 설명 | 코드트리
부분 수열의 합이 M를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int M = read();
int[] A = new int[N];
for(int i = 0; i<N; i++){
A[i] = read();
}
int[][] dp = new int[N+1][M+2];
int INF = N+1;
for(int i = 0; i<=N; i++){
Arrays.fill(dp[i], INF);
dp[i][0] = 0;
}
for(int i = 1; i<=N; i++){
int cur = A[i-1];
for(int j = 0; j<=M; j++){
// 선택 안함
dp[i][j] = dp[i-1][j];
// 선택 함
if(j >= cur)
dp[i][j] = Math.min(dp[i][j], dp[i-1][j-cur] + 1);
}
}
System.out.print(dp[N][M] == INF ? -1 : dp[N][M]);
}
}사고의 흐름 및 풀이
부분수열이니까 순서를 지켜야 하고 각 원소를 한번씩만 써야 함
dp[i][j] = 앞에서 i번째까지 물건을 사용해서 숫자의 합이 j일때 최소 사용 갯수
dp[i][j] = min(dp[i-1][j], dp[i-1][j-A[i-1]] + 1)
최대 사용 갯수는 N, INF = N+1
-> 참조를 i-1, 이전 상태(이번 값으로 인해 갱신 안된 상태)로만 해서
dp[j] = 숫자의 합이 j일때 최소 사용 갯수 로 상태압축 가능
근데 현재 값으로 갱신 안된 상태를 유지해야하고
점화식은 dp[j-A[i]] 이므로 정방향으로 갱신하게 되면 이전 상태가 갱신된 상태이기 때문에 불가능하고
역방향으로 갱신하게 되면 이전 상태가 갱신되지 않은 상태를 유지하기 때문에
상태 압축 전의 의미가 보존됨.
-> 정방향 : dp[j-A[i]] = 이미 현재 원소를 사용한 상태일수도 있음 (재사용 가능)
-> 역방향 : dp[j-A[i]] = 아직 현재 원소를 사용하지 않은 상태 (1번만 사용 가능)
따라서 역방향으로 갱신하여 상태 전이시키면 됨.
문제 - 최대 동전 거슬러주기
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-max-coin-change/description
최대 동전 거슬러주기 설명 | 코드트리
최대 동전 거슬러주기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int M = read();
int[] A = new int[N];
for(int i= 0; i<N; i++){
A[i] = read();
}
//Arrays.sort(A);
int[] dp = new int[M+1];
int INF = 10001;
Arrays.fill(dp, -INF);
dp[0] = 0;
for(int i =0 ; i<N; i++){
int cur = A[i];
for(int j = cur; j<=M; j++){
if(dp[j-cur] != -INF)
dp[j] = Math.max(dp[j], dp[j-cur]+1);
}
}
System.out.print(dp[M] < 0 ? -1 : dp[M]);
}
}사고의 흐름 및 풀이
dp[ i ] = i 원을 만드는 최대 동전 갯수로 정의하고 풀었다.
최대화로 갱신해야하니까 불가능한 상태를 - INF로 둬야 한다. INF는 동전 종류 중 가장 작은 값을 M으로 나눠서 + 1,2를 해줘도 되고 그냥 매우 큰 값으로 잡아도 된다. 여기서는 M이 최대 10000이므로 10001로 잡았다.
또한 동전의 값이 주어지는게 오름차순이든 내림차순이든 상관이 없다.
왜냐하면 여기서 동전 사용 순서와 무관하게 최종 최적값이 동일하기 때문에 값 정렬은 필요 없다.
-> O(N*M) 이라서 N log N 보다 크니까 괜찮을 거 같긴 한데 그래도 필요 없다.
-> 원래는 INF값 계산할때 쓰려고 썼었는데 그냥 Integer.MIN_VALUE 이런거 아니면 -10001정도면 overflow 이슈도 없고 ㄱㅊ
이전 상태가 invalid 하지 않을 때만 참조해서 업데이트한다.
-> 근데 최대화로 갱신하기 때문에 INF값이 -1같은게 아니라면 어차피 탈락해서 if문을 쓰지 않아도 동작한다.
-> if(불가능 상태 아님) 전이 의 가독성과 의미 전달을 위해서 쓰고 템플릿화 하기 좋기 때문에 공식 해설에서도 등장하는 것 같다.
-> 또한 매우 큰 값일때 overflow 문제를 방지한다.
문제 - 부분 수열의 합
부분 수열의 합 설명 | 코드트리
부분 수열의 합를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws Exception {
int N = read();
int M = read();
int[] A = new int[N];
for(int i= 0; i<N; i++)
A[i] = read();
boolean[] dp = new boolean[M+1];
dp[0] = true;
for(int i = 0; i<N; i++){
int cur = A[i];
for(int j = M; j>=cur; j--){
dp[j] = dp[j] || dp[j-cur];
}
}
System.out.print(dp[M] ? "Yes" : "No");
}
}사고의 흐름 및 풀이
어떤 수열이 주어지고 해당 수열의 부분수열을 가지고 각 원소를 sum해서 M을 만들 수 있는지 여부를 묻는 문제다.
처음에는 백트래킹으로 풀이했다가 TLE가 났다. 왜냐하면 부분 문제 해결 -> 큰 문제 해결의 구조를 활용하지 않았기 때문이다.
dp [ i ] = 합 i 가 가능한지 여부
가능한 상태는 2가지가 있는데
1) dp [ i ] 가 원래 가능한 경우
2) dp [ i - A[ j ] ] , 즉 이전 상태가 가능해서 현재 원소를 합하면 그 역시 가능한 상태가 되는 경우
이를 식으로 나타내면 다음과 같다.
dp[j] = dp[j] || dp[j-cur];문제 - 배낭 채우기 (0/1 knapsack)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-knapsack/description
배낭 채우기 설명 | 코드트리
배낭 채우기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static final int INF = Integer.MIN_VALUE;
public static void main(String[] args) throws Exception {
int N = read();
int M = read();
int[][] A = new int[N][2];
for(int i = 0; i<N; i++){
A[i][0] = read();
A[i][1] = read();
}
int[] dp = new int[M+1];
Arrays.fill(dp, INF);
dp[0] = 0;
int ans = 0;
for(int i = 0; i<N; i++){
int cw = A[i][0];
int cv = A[i][1];
for(int j = M; j>=cw; j--){
if(dp[j-cw] != INF){
dp[j] = Math.max(dp[j], dp[j-cw]+cv);
ans = Math.max(ans, dp[j]);
}
}
}
System.out.print(ans);
}
}사고의 흐름 및 풀이
담을 수 있는 보석의 무게의 최대치가 고정되었을 때, 가치를 최대화하는 문제이다.
dp [ w ] = 현재 가방의 총 무게가 정확히 w일때, 가능한 최대 가치
로 정의한다.
정확히 W이기 때문에 invalid 상태를 정의해주어야 한다. (Integer.MIN_VALUE)
그리고 문제 조건 상 보석을 하나씩만 사용할 수 있으므로 역방향으로 전이해야 한다.
-> 상세 설명은 2차원 배낭문제 압축을 참고
전이 조건은
1) 현재 무게의 총 가치가 더 클 때 그대로 유지
2) 현재 보석을 넣기 전의 배낭의 가치가 valid 한 값이며, 현재의 보석을 넣어서 가치의 총 합이 이전보다 크면 그걸로 갱신
if(dp[j-cw] != INF)
dp[j] = Math.max(dp[j], dp[j-cw]+cv);또한 상태가 2가지이고
최대 가치가 반드시 최대 무게에서 나오는 것이 아니므로 dp를 갱신할 때마다
정답에 최대화하는 쪽으로 갱신해서 정답을 계산한다.
공식 해설과 비교
공식 해설은 2차원 dp로 푼 것 같다.
상태는 지금까지 고려한 보석의 위치 , 지금까지 고려한 보석의 무게의 합, 지금까지 얻은 가치이며
압축하면 점화식은 내 풀이와 같지만 의미가 달라진다.
-> dp [ w ] = 무게 제한이 w일때 얻을 수 있는 최대 가치
현재 보석을 담거나, 현재 보석을 담지 않을 때 둘 중 최대 가치로 갱신함.
모든 상태가 이미 valid 한 상태라서 굳이 INF를 설정하지 않아도 됨.
-> 모든 dp[ j ]는 최소 0이기 때문이다.
if 문 없이 똑같이 역방향 갱신으로 풀이함.
문제 - 막대기 나누기
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rod-cutting/description
막대기 나누기 설명 | 코드트리
막대기 나누기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static final int INF = -(100 * 10_000 + 1);
public static void main(String[] args) throws IOException{
int N = read();
int[][] A = new int[N][2];
for(int i = 0; i<N; i++){
A[i][0] = i+1;
A[i][1] = read();
}
int[] dp = new int[N+1];
Arrays.fill(dp, INF);
dp[0] = 0;
for(int i = 0; i<N; i++){
int cw = A[i][0];
int cv = A[i][1];
for(int j = cw; j<=N; j++){
if(dp[j-cw] != INF){
dp[j] = Math.max(dp[j], dp[j-cw] + cv);
}
}
}
System.out.print(dp[N]);
}
}사고의 흐름 및 풀이
막대기의 총 길이가 N이고 입력에서 1~N의 길이로 각각 잘랐을때 가치가 주어짐.
총 합이 정확히 N일 때 가능한 가치합을 최대로 해야하므로 정의는 다음과 같다.
-> dp [ i ] = 길이 합이 정확히 i일 때, 가능한 최대 value의 sum
자꾸 invalid를 정의하게 되는데 사실 이 문제에서는 문제 조건에 의해 필요 없다.
왜냐하면 길이 1이 항상 존재하기에 어떤 길이도 항상 만들 수 있기 때문이다.
하지만 어려운 dp문제에서는 가능한 경우에만 전이하고 전이 조건을 고려해야하기 때문에
이게 더 뭔가 편해서 이렇게 구현하긴 했다.
문제 - 최소 차 분할 (다시 보기)
최소 차 분할 설명 | 코드트리
최소 차 분할를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] A = new int[N];
int tot = 0;
for(int i =0 ; i<N; i++){
A[i] = read();
tot += A[i];
}
// i개를 선택했을때 합이 j가 가능한가?
// boolean[][] dp1 = new boolean[N+1][tot+1];
// dp1[0][0] = true;
// for(int i = 0; i<N; i++){
// int cur = A[i];
// // 갯수 역순
// for(int cc = N; cc >= 1; cc--){
// // 가능한 합 역순
// for(int j = tot-cur; j>=0; j--){
// // cur을 선택하지 않은 이전 상태가 가능하면 (cc-1개, 총합은 j)
// // 다음 상태 (cc : cur 선택함 (cc인건 역순이라), 총합은 j + cur)
// if(dp1[cc-1][j]){
// dp1[cc][j+cur] = true;
// }
// }
// }
// }
// 압축하면 이렇게 가능
// dp[i]= 합 i 가 가능한지
boolean[] dp = new boolean[tot+1];
dp[0] = true;
for(int i = 0; i<N; i++){
int cur = A[i];
for(int j = tot; j >= cur; j--){
dp[j] |= dp[j-cur];
}
}
int ans = 100 * 1000 + 1;
for(int j = 0; j<=tot; j++){
if(dp[j])
ans = Math.min(ans, Math.abs(tot - (2*j)));
}
System.out.print(ans);
}
}사고의 흐름
N개의 수가 있을 때 정확히 2개의 그룹으로 나누어 A의 합 - B의 합이 최소가 되도록 하는 프로그램 작성.
-> 그룹 A, B를 둘다 뭐 갱신하기는 좀 복잡하고 하나를 결정하면 나머지 하나가 자동으로 결정되므로
total을 계산해가지고 나머지 하나만 N-1개까지 고르고 abs(tot - 2 * 현재 합)을 최솟값으로 갱신하면 될 거 같다.
하나씩만 사용해야 하니까 역방향으로 갱신해야한다.
풀이
정확한 합을 만들어야 하는 건데 B = tot - A로 표현할 수 있다.
따라서 점화식으로 나타내게 되면 다음과 같다.
-> 원래는 dp [ i ][ j ] = i 까지 봤을 때, 합이 j가 되는지 여부 지만 항상 이전상태만 참고하므로
압축하면 dp [ i ] = 총 합이 i일 때 가능한지에 대한 여부 가 된다.
추가로 설명하면,
dp [ i ] = true 라는 것은 합이 i가 되도록 원소를 선택하는 방법이 존재한다는 뜻이다.
이때 선택되지 않은 나머지 원소들은 자동으로 다른 그룹 B가 되므로, B의 합은 항상 tot - i 가 된다.
-> 가능한 모든 i에 대해 abs( i - (tot - i ) ) = abs ( tot - 2*i )
각 그룹이 최소 1개 이상이어야 한다는 조건에 따라 [1, tot-1] 의 구간에서 dp[ i ] 가 참일 때
abs( tot - 2*i ) 를 최솟값으로 갱신한 것을 출력하면 된다.
-> 공집합과 전체집합을 제외해서 갱신하기
문제 - 최대 합 분할 (다시 보기)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-maximum-sum-partition/description
최대 합 분할 설명 | 코드트리
최대 합 분할를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] A = new int[N];
int tot = 0;
for(int i = 0; i<N; i++){
A[i] = read();
tot += A[i];
}
int INF = -2*(tot+1);
// -tot ~ tot
int[] dp = new int[2*tot+1];
Arrays.fill(dp, INF);
dp[tot] = 0;
for(int cur : A){
int[] next = dp.clone();
for(int d = -tot; d<=tot; d++){
//dp[d+tot] = 현재 차이 d를 만들때 A 합의 최댓값
if(dp[d+tot] == INF)
continue;
// A에 현재 숫자 넣기
// A에 넣으면 A합-B합이니까 양수로 작용
int nd = d + cur;
if(nd >= -tot && nd <= tot){
// A에 넣을때만 A합 증가
next[nd+tot] = Math.max(next[nd+tot], dp[d+tot] + cur);
}
// B에 넣기
// B에 넣으면 A합-B합이니까 음수로 작용
nd = d - cur;
if(nd >= -tot && nd <= tot){
next[nd+tot] = Math.max(next[nd+tot], dp[d+tot]);
}
// C에 넣기
// C에 넣으면 A합-B합 변화 없음
next[d+tot] = Math.max(next[d+tot], dp[d+tot]);
}
dp = next;
}
System.out.print(dp[tot]);
}
}사고의 흐름
N 개의 수가 주어졌을 때 이를 정확히 3개의 그룹으로 나누어 A에 들어있는 수들의 합과 B에 들어있는 수들의 합을 같게 만들면서, 그 합이 최대로 되도록 하는 프로그램을 작성해야 한다.
a,b,c 에 정확히 한개씩 모든 수가 들어가있는 상태로 종결되어야 한다.
또한 a,b,c의 공집합의 합은 0이다.
처음에는 위에 문제처럼 생각하고 C는 원소가 더해져도 사실상 A 합과 B 합 비교하는 거라 의미가 없으니
A와 B의 subset sum problem으로 접근하려 했다.
-> 문제는 그것의 합이 존재한다고 하더라도 A와 B에서 구성 요소가 중복해서 들어가는 것을 방지할 수 없어서 WA이다.
그러면 상태 정의부터 다시 해야한다고 생각했다.
-> A와 B 간의 disjoint 조건 때문에 재정의를 해야 한다.
C는 A합과 B합의 차이에 직접적인 영향을 주지 않는다.
따라서 이 문제의 핵심은 A와 B의 균형을 맞추는 문제로 볼 수 있다.
여기서는 절댓값으로 계산할 수는 없다.
왜냐하면 A에 구성요소가 붙는거랑 B에 구성요소가 붙을 때 기준에 따라 양수가 될 수도 있고 음수가 될 수 도 있기 때문에
최댓값과 최솟값의 한계점을 미리 계산해서 offset으로 붙여두고 항상 양수로 인덱스를 뽑아야 한다.
-> A에 넣을 때와 B에 넣을 때의 방향성이 다름
-> total을 구하면 한쪽에 쏠리더라도 0이 나올테니 계산할때 항상 tot을 붙여서 계산하면 될 것 같다.
풀이
동일한 diff를 만드는 방법은 여러 개 존재할 수 있다.
그 중 최종적으로 A합 = B합이 되었을 때, 그 합을 최대화해야 하므로 각 diff 상태에서는 가능한 max A 합 만 저장한다.
dp [ diff ] = A합 - B합을 diff라 할 때, diff를 만들 때 가능한 A합의 최댓값-> 여기서 dp 크기는 2*tot + 1로 잡는다. A합이 기준이기 때문에 실제 diff는 음수가 나올 수 있다.
초기화를 먼저 해준다.
invalid 는 대략 tot+1 를 2배로 하고 음수로 바꾼 값으로 잡았다. (-1로 표현해도 되긴할듯)
dp[0] = 0 인데 오프셋 때문에 dp[ tot ] = 0 으로 설정한다.
모든 구성 요소에 대해서 순회를 도는데
현재 차이 d를 만들 때 A 합의 최댓값이 invalid 하면 갱신할 수 없으므로 넘어가고
이때, dp를 복사해서 써야한다. (next)
-> 이유는 현재 숫자를 처리하는 과정에서 같은 숫자가 한 번 이상 사용되는 것을 방지하기 위해
이전 상태 ( dp ) 와 현재 갱신 상태 ( next )를 분리해야 한다.
가능한 상태는 3가지로 볼 수 있다. (설명용이라 offset은 수식에서 제외함)
1) 현재 가르키는 요소 A에 넣기
-> A에 넣으면 newDiff = curDiff + curNum 이다.
newDiff가 유효한 범위에 존재한다면 A에 넣었으니
next [ nd ] = max ( next[ nd ] , dp[ d ] + curNum )
2) 현재 요소 B에 넣기
-> B에 넣게되면 newDiff = curDiff - curNum이다. (A 기준이므로)
newDiff가 유효한 범위에 존재한다면 B에 넣었으니 A의 합은 변화가 없다.
next [ nd ] = max ( next [ nd ] , dp [ d ] )
3) 현재 요소 C에 넣기
-> C에 넣게되면 newDiff는 A합과 B합의 차이이기 때문에 변화하지 않는다.
next [ d ] = max ( next [ d ], dp [ d ] )
모든 가능한 d 후보에 대해 순회했다면 갱신된 복사된 dp인 next를 dp로 업데이트한다.
정답 출력은 점화식의 정의에 따라 diff = 0 상태는 A합 - B합 = 0. 즉, A합 = B합 상태이다.
-> Offset을 적용해서 dp [ tot ] 이 정답이 된다.
문제 - 경험치를 빠르게 얻기
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-gain-exp-quickly/description
경험치를 빠르게 얻기 설명 | 코드트리
경험치를 빠르게 얻기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int M = read();
int[][] A = new int[N][2];
// 모든 시간의 합 -> dp 크기
int tot = 0;
for(int i = 0; i<N; i++){
// val, weight
int val = read();
int weight = read();
A[i] = new int[]{val, weight};
tot += weight;
}
long[] dp = new long[tot+1];
long INF = -1;
Arrays.fill(dp, INF);
dp[0] = 0;
for(int i = 0; i<N; i++){
int cw = A[i][1];
int cv = A[i][0];
for(int j = tot; j >= cw; j--){
if(dp[j-cw] == INF)
continue;
dp[j] = Math.max(dp[j], dp[j-cw]+cv);
}
}
int ans = -1;
for(int i = 0; i<dp.length; i++){
if(dp[i] >= M){
ans = i;
break;
}
}
System.out.print(ans);
}
}사고의 흐름
제한조건은 N = 100, M = 1_000_000, 입력은 (value, t) pair로 들어오는데 val = 1_000_000, t = 100
각 퀘스트는 1~N번 으로 주어지고 해결하면 얻을 수 있는 경험치, 걸리는 시간이 입력으로 주어질 때
M의 경험치를 얻기 위한 최소 시간을 구하는 문제이다.
여기서 N*M은 1억이라 상태로 정의하게 되면 인덱스가 터지기 때문에 발상의 전환이 필요하다.
풀이
경험치가 상태이면 시간을 최소화 하는 방향으로 하면 되지만 반대로 생각해보면
시간을 상태로 두게 되면 같은 시간에 경험치를 최대화 한다면
M 이상의 경험치를 최초로 만족하는 시간이 곧 최소 시간이 된다고 할 수 있다.
-> 문제 정답 조건 충족
점화식으로 나타내면 다음과 같다.
dp [ weight ] = weight 만큼 정확히 시간이 걸렸을 때, 얻을 수 있는 경험치의 최대 값
여기서 각 퀘스트는 한번씩만 해결 가능하니 역방향으로 전이한다.
또한 dp의 크기는 각 퀘스트의 time 누적 값으로 하고 정확한 시간이 상태에 들어가서 INF를 설정하고
이전 상태가 invalid 하면 갱신하지 말아야 한다.
문제 - 동일하게 분할
https://www.codetree.ai/ko/trails/complete/curated-cards/test-equal-partition/description
동일하게 분할 설명 | 코드트리
동일하게 분할를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
public static void main(String[] args) throws IOException{
int N = read();
int[] A = new int[N];
int tot = 0;
for(int i =0 ; i<N; i++){
A[i] = read();
tot += A[i];
}
if(tot % 2 != 0){
System.out.print("No");
return;
}
boolean[] dp = new boolean[tot+1];
dp[0] = true;
for(int i = 0; i<N; i++){
int cur = A[i];
for(int j = tot; j>=cur; j--){
dp[j] |= dp[j-cur];
}
}
System.out.print(dp[tot/2] ? "Yes" : "No");
}
}사고의 흐름 및 풀이
문제는 A 수열을 정확하게 2 그룹으로 나눴을 때 각자의 합이 같게 되는 가능한지에 대한 여부를 출력하는 것이다.
여기서 total을 구했을 때 홀수이면 아무리 나눠도 합이 같아질 수 없으므로 NO이다.
그래서 일단 모든 합이 가능한지에 대해 원소를 하나씩 사용하는 역방향 전이 0/1 배낭 DP를 사용하고
정답 조건을 다시 생각해보면 나눴는데 합이 같다고 한다. 이를 수식으로 나타내면,
A sum + B sum = tot
-> 2 * A sum = tot
-> A sum = tot / 2-> dp [ tot / 2 ] 의 boolean 값에 따른 출력을 해주면 된다.
이제 dp 1은 다 풀었으니까 다시 위상정렬, 트리 DP 쪽 가서 dp 관련 최적화와 그쪽 생각들을 풀어보는게 좋을 거 같다.
#코드트리 #코딩테스트 #코테공부 #오답노트 #공부습관
'공부 > 알고리즘' 카테고리의 다른 글
| [코드트리] 5 - 구현/시뮬레이션 및 해결 전략 총정리 (0) | 2026.06.13 |
|---|---|
| [코드트리] 4 - 트리 DP, LCA, 한 달 공부 후기, 2차 갭체크 (0) | 2026.06.03 |
| [코드트리] 2 - 트리 공부 및 1일 1문제 습관 형성하기 (0) | 2026.05.20 |
| 자바 입출력 팁 : StreamTokenizer (0) | 2026.05.14 |
| 코드트리 - 슬라이딩 윈도, 누적합, prefix max 기법, 최적화 (0) | 2026.05.12 |
