주인공의 배낭은 최대 K 크기 만큼 물건을 넣을 수 있다. 배낭에 넣을 수 있는 물건들의 무게와 가치가 주어질 때, 배낭에 넣을 수 있는 물건들의 가치 최댓값을 출력하시오.
2.문제예제
3.팩트추출
"워낙 유명한 문제라 DP 알고리즘 문제라는 것을 알고 문제를 푸는 것이 아니라
어떻게 DP 로 접근했을까 생각하고 아이디어를 정리해보았다."
Fact 1: 각 물건들을 고르거나 고르지 않는 모든 경우의 수를 고려해보면 쉽게 문제를 해결할 수 있다. 하지만, O(2^N) 시간복잡도가 필요하며 너무 많은 시간이 소요된다. 물건이 하나씩 추가될 때마다 기존 시간의 2배 정도 시간이 필요한 것이다. 물건에만 포커스를 맞춘 경우인데 이러한 구조는 이미 경우의 수 일부에서 배낭이 꽉 찬 경우인데도 어쩔 수 없이 탐색할 수 밖에 없다. 위 예제 1에서 첫 번째 아이템을 선택하면 무게가 6으로 그 다음은 7-6=1무게만큼 필요한데 1무게를 찾기 위해서 모든 조합을 다 찾아야 한다는 것이다. 여기서 힌트를 얻을 수 있다.
내가 지금 필요한 무게에 대한 최대값을 바로 찾을 수 있다면 그런 수고를 덜 수 있다. 위 예제에서는 1무게에 대한 최대값 말이다. 다시 말해 물건과 무게 두 곳에 포커스를 맞추어 정답을 구하는 것이다.
Fact 2: i 번째 물건까지 보았을 때 가치가 최대인 무게들을 구한다는 것은 부분문제처럼 보인다. 여기서 구하려고 하는 최종 결과값도 최대 가치를 만들려고 하는 것이기 때문이다. 부분 문제이고 작은 문제들의 정답이 다음 문제들에게 영향을 미친다면 DP (Dynamic Programming) 문제이다. DP[i][j] 를 i 번째 물건까지 보았을 때 j 무게에서 최대 가치라고 할 때 아래와 같은 수식이 만족한다.
dp[i-1][j] 는 이전 물건까지만 고르고 현재 물건을 고르지 않는 경우이고, v[i] + dp[i-1][j-w[i]] 는 이전 물건도 고르고 이번 물건도 고르는 경우이다. j-w[i] 수식을 보면 배낭의 남은 무게보다 현재 물건의 무게가 작아야 한다는 것을 알 수 있다. 물건을 탐색했을 때 가방에 넣을 수 있다면 해당 무게로 이전까지 선택한 최대치에 현재 가치를 더해서 최대치를 갱신한다.
Fact 3 : 점화식도 분명 현재 물건을 넣는 경우와 넣지 않는 경우의 수가 필요한 것이 분명한데 O(2^N) 이 되지 않는 점을 이해해야 한다. 모든 조합의 경우의 수를 구해서 문제를 푸는 것이 아니라 각 단계마다 정답을 구해 이전 경우의 수를 상쇄시키는 것이 특징이다. 이전 값만 보고 판단한다. DP 특징이기도 하다. 또한 해당 시점에서 배낭의 무게를 1차이로 모두 구해 탐색하지 않고 바로 답을 구하는 것을 볼 수 있다.
4.문제풀이(수동)
문제 예제 입력 1번의 DP 테이블을 만들었을 때 다음과 같다.
i \ j
0
1
2
3
4
5
6
7
1
0
0
0
0
0
0
13
13
2
0
0
0
0
8
8
13
13
3
0
0
0
6
8
8
13
14
4
0
0
0
6
8
12
13
14
위 DP 점화식을 토대로 i 가 1부터 4까지 j 행을 차례로 구한다.
dp[3][7] 을 살펴보면, dp[3][7] 은 dp[2][7] 과 dp[3][7-(3번 물건의 무게)] + v[3] 둘 중 큰 값을 저장하게 된다. dp[3][4] 값은 8이고 v[3] 은 6이므로 최종적으로 dp[2][7] 은 13, dp[3][7] 은 14이므로 dp[3][7] 에는 14가 저장된다.
5.문제전략
문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. 도출한 DP 방정식으로 문제를 풀었다.
6.소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, K;
private static int[] weight, value;
private static int[] dp;
private static void knapsack() {
for (int i = 1; i <= N; i++) {
for (int j = K; j - weight[i] >= 0; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
weight = new int[N+1];
value = new int[N+1];
dp = new int[K+1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
weight[i] = Integer.parseInt(st.nextToken());
value[i] = Integer.parseInt(st.nextToken());
}
knapsack();
System.out.println(dp[K]);
}
}
각 문제마다 조건이 추가된다. 이 N 과 M 시리즈는 재귀함수(DFS)의 본질을 이해하고, 우리가 흔히 접할 수 있는 순열 및 조합 문제를 풀 수 있는 기초가 되기 때문에 꼭 풀어보는 것을 권장한다.
N과 M (1)
+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
+ 자기 자신은 제외하고 남은 수열을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
combinations[depth] = i + 1;
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (2)
+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
if (!visited[i]) {
combinations[depth] = i + 1;
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (3)
+ 1부터 N까지 자연수 중에서 M개를 고른 수열
+ 같은 수를 여러 번 골라도 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
combinations[depth] = i+1;
dfs(i, depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (4)
+ 1부터 N까지 자연수 중에서 M개를 고른 수열
+ 같은 수를 여러 번 골라도 된다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
combinations[depth] = i+1;
dfs(i, depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combinations = new int[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (5)
+ 자기 자신은 제외하고 남은 수열을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
if(!visited[i]) {
combinations[depth] = items[i];
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (6)
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
if(!visited[i]) {
combinations[depth] = items[i];
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (7)
+ 같은 수를 여러 번 골라도 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
combinations[depth] = items[i];
dfs(i,depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (8)
+ 같은 수를 여러 번 골라도 된다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = index; i < N; i++) {
combinations[depth] = items[i];
dfs(i,depth + 1);
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0,0);
System.out.println(sb.toString());
}
}
N과 M (9)
+ 중복 수열은 출력하지 않는다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = 0; i < N; i++) {
if (prevNumber != items[i] && !visited[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
visited[i] = true;
dfs(depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0);
System.out.println(sb.toString());
}
}
N과 M (10)
+ 같은 수를 여러 번 골라도 된다.
+ 중복 수열은 출력하지 않는다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = index; i < N; i++) {
if (prevNumber != items[i] && !visited[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
visited[i] = true;
dfs(i, depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
visited = new boolean[N];
dfs(0, 0);
System.out.println(sb.toString());
}
}
N과 M (11)
+ 같은 수를 여러 번 골라도 된다.
+ 중복 수열은 출력하지 않는다.
+ 같은 숫자를 여러 번 골라도 된다.
package org.example;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = 0; i < N; i++) {
if (prevNumber != items[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
dfs(i, depth + 1);
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0, 0);
System.out.println(sb.toString());
}
}
N과 M (12)
+ 같은 수를 여러 번 골라도 된다.
+ 중복 수열은 출력하지 않는다.
+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N, M;
private static int[] combinations, items;
private static List<Integer> itemsDistinct;
private static StringBuilder sb = new StringBuilder();
private static void dfs(int index, int depth) {
// 종료 조건
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(combinations[i]).append(" ");
}
sb.append("\n");
return;
}
int prevNumber = -1;
for (int i = index; i < N; i++) {
if (prevNumber != items[i]) {
combinations[depth] = items[i];
prevNumber = items[i];
dfs(i, depth + 1);
}
}
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
items = new int[N];
combinations = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(items);
dfs(0, 0);
System.out.println(sb.toString());
}
}
지도의 각 칸에는 그 지점의 높이가 주어지며 (0, 0) 지점에서 (n-1, m-1) 지점으로 내려가려고 한다. 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 할 때 이동할 수 있는 경로의 수를 구하시오.
2.문제예제
3.팩트추출
Fact 1:전형적인 BFS 와 DFS 문제인것처럼보이지만, 입력의범위를보면완전탐색시시간초과가발생할수있다. 최대칸수가 500 * 500 으로 250000 이며상하좌우 4방향으로움직일수있으니 4 의 250000 제곱경우의수가존재한다. 경우의수를줄일수있는방법을찾아야한다.
Fact 2: 문제예제를살펴보면전체문제의답이작은부분문제의답의합으로구성되어있다. 50 번지점에서 목적지까지가는경로의수는 45번지점에서가는경로의수 + 35번지점에서 가는경로의수로이루어져있다. 35번지점이나 30번지점, 27번 지점은경로의수가하나로나중에이지점을방문하더라도계산할필요가없다. 즉 DP 문제이다.
Fact 3 : 기존 DFS 나 BFS 에서사용하던 visited 배열을응용하여 "해당지점에서목적지까지가는경로의수" 로생각하여해당값을재활용하면탐색범위를줄일수있다. 여기서중요한점은 DFS 와 BFS 의 visited 배열활용도가조금다르다는 것이다. BFS 는주변부터탐색하기때문에단순방문했는지여부만파악할수있지만 DFS 는한가지경우의수부터모두탐색하고다시원래위치로돌아오기때문에수행도중 visited 배열을오염시킨다면 그경로는다시탐색하지않아도된다. 4 번 문제 풀이 (수동) 부분에서 자세히 확인한다.
Fact 4: DP[x][y] 배열을 0 으로 초기화하면 이 경로의 수가 0 인지 노드를 방문하지 않은 것인지 확인이 불가능하다. DP 배열이 visited 배열의 역할도 하기 때문에 -1 로 초기화한다.
4.문제풀이(수동)
문제 예제 입력 1을 DFS 알고리즘 + DP 방식으로 문제를 풀었을 때 애니메이션이다.
손수 애니메이션으로 만들어준 우투리와툴툴 티스토리 블로그님께 감사의 말씀을 전한다. 덕분에 이해하기가 쉽다.
5.문제전략
문제 전략은 팩트 추출을 통해 알아보았다. DFS + DP 방식으로 문제를 풀었다.
6.소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int M, N;
static int[][] map;
static int[][] dp;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[M][N];
dp = new int[M][N];
for(int j = 0; j < M; j++) {
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
map[j][i] = Integer.parseInt(st.nextToken());
}
}
initDP();
System.out.println(dfs(0, 0));
}
private static void initDP() {
for(int j = 0; j < M; j++) {
for (int i = 0; i < N; i++) {
dp[j][i] = -1;
}
}
}
private static int dfs(int x, int y) {
if(x == M-1 && y == N-1){ return 1; }
if(dp[x][y] != -1) return dp[x][y];
dp[x][y] = 0;
for (int i=0; i<4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX < 0 || newX >= M || newY < 0 || newY >= N) continue;
if (map[x][y] <= map[newX][newY]) continue;
dp[x][y] += dfs(newX, newY);
}
return dp[x][y];
}
}
Fact 3: lgN 트리 길이만큼 매번 연산하지 말고, 업데이트나 조회 시 해당 구간이 필요하면 변수를 하나 두어 해당 변수에 업데이트하고 다음 번에 도착했을 때 한 단계씩 자식에게 값을 늦게 전파하면 연산을 획기적으로 줄일 수 있다. 이러한 방법을 Lazy Propagation 이라고 한다. 자세한 내용은 다음 글을 참고하자.
public class Main {
static final int SIZE = 65536;
static int[] arr, tree;
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 k = Integer.parseInt(st.nextToken());
arr = new int[n+1];
for(int i=1; i<=n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
tree = new int[SIZE*4];
// 1 번부터 k 직전까지 노드 삽입
for(int i=1; i<k; i++) {
update(0,SIZE,1,arr[i],1);
}
int prev = 1;
int mid = (k+1)/2;
long ans = 0;
// k 부터 n 까지 노드 삽입하면서 중앙값을 계산하고, 슬라이딩 윈도우 기법으로 K 배열을 움직인다.
for(int i=k; i<=n; i++) {
update(0,SIZE,1,arr[i],1);
ans += find(0,SIZE,1,mid);
update(0,SIZE,1,arr[prev++],-1);
}
System.out.println(ans);
}
static int update(int start, int end, int node, int index, int diff) {
// 기저사례 1 : 타겟 인덱스가 범위 밖인 경우, skip
if(index < start || end < index) {
return tree[node];
}
// 기저사례 2 : 타겟 인덱스 안에 있으면서 start == end 값이 같다면 index 지점에 도착했다는 뜻
if(start == end) {
return tree[node] += diff;
}
int mid = (start + end) / 2;
// 좌측 의 카운트와 우측의 카운트를 합친 값이 부모 카운트
return tree[node] = update(start, mid, node*2, index, diff)+update(mid+1, end, node*2+1, index, diff);
}
static int find(int start, int end, int node, int k) {
if(start == end) {
return start;
}
int mid = (start+end) / 2;
if(tree[node*2] >= k) {
return find(start, mid, node*2, k);
} else {
return find(mid+1, end, node*2+1, k-tree[2*node]);
}
}
}
N개의 스위치와 N개의 전구가 있다. i (1 < i < N) 번 스위치를 누르면 i - 1, i, i + 1 의 세 개의 전구의 상태가 동시에 바뀐다.
(자기 자신을 포함해서 양 옆에 있는 전구가 동시에 바뀐다.) N개의 전구들 현재 상태와 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.
2.문제예제
3.팩트추출
Fact 1:자기 자신의 스위치를 바꿀 수 있는 것은 양 옆에 있는 전구이다.
그런데 만약 0 ~ N - 1 까지 순차적으로 실행하게 된다면, 왼쪽에 있는 전구는 오른쪽 전구에 의해 바뀔 수 있으므로 사고 과정에서 생략할 수 있다. 오른쪽 전구로만 컨트롤하게 바꾼다면 이전 정보가 필요 없어지게 된다. 또 부분문제이기 때문에 그리디 알고리즘으로 풀 수 있다.
Fact 2:i - 1 번째 전구만 보면서 타겟 전구와 같다면 넘기고, 다르다면 스위치를 누른다. 그런데 가장 첫 번째 전구는 눌러야 할지, 말아야 할지 결정할 수가 없기 때문에 두 가지 경우의 수 모두 구한다.
Fact 3:i 가 마지막 N 위치까지 왔는데 타겟 전구의 상태와 다르다면, 도달할 수 없다는 뜻이고 같다면 최소의 경우의 수 이므로 count 를 반환한다.이 전략이 항상 최선의 상태를 반환하는지는(최소 값을 보장하는지는) 아래 문제풀이(수동)을 통해 알아본다.
4.문제풀이(수동)
그리디 알고리즘은 해당 전략이 항상 최선의 상태를 반환해주는지 검증해야 한다. 문제를 전구 배열 3 크기로 나누어서 생각해본다.
현재 전구 상태 : 010
목표 전구 상태 : 111
목표 전구 상태와 다른 부분을 보고 바로 킨다면 010 -> 100 -> 011 루틴으로 가장 첫 번째 전구를 못 키게 된다.
그 다음 인덱스에서 킨다면 101 -> 110 -> 111 로 안정적으로 킬 수 있게 된다.
현재 전구 상태 : 000
목표 전구 상태 : 111
중간에 있는 전구 하나만 키면 되는 것처럼 보이지만 그 다음 인덱스에서 키기 때문에 이 중간 문제도 해당 공식이 성립한다. 이처럼 3 전구 상태 배열의 모든 경우의 수를 나열하고 테스트 해보았을 때, 오른쪽에 있는 전구를 킬 때가 가장 올바른 선택이라는 것을 알 수 있다.
위와 같이 히스토그램 예제가 있을 때, 0번부터 7번까지 순차적으로 문제푸는 방식과 문제를 분할하여 푸는 방식 2가지가 존재한다. 세그먼트 트리를 이용하는 방법도 있다고는 하는데 여기서는 생략한다.
1) 스택활용
먼저 순차적으로 문제푸는 방식으로 예제를 풀어보면, 다음과 같다.
H[0] * 1 = 3 ===> MaxArea 3 으로갱신
H[4] * (5-4) = 5 * 1 = 5 ===> MaxArea 5 로갱신
H[3] * (5-3) = 4 * 2 = 8 ===> MaxArea 8 로갱신
H[2] * (5-2) = 3 * 3 = 9 ===> MaxArea 9 로갱신
H[1] * 5 = 2 * 5 = 10 ===> MaxArea 10 으로 갱신
H[7] * (7-6) = 3 * 1 = 3
H[6] * (7-5) = 3 * 2 = 6
H[5] * 8 = 1 * 8 = 8
따라서 정답은 10 이다.
2) 분할정복
다음은 문제를 분할정복해서 나누어 풀 때 방식이다. 다음과 같다.
일단 문제를 mid 중심으로 나누어 쪼갠다. 좌측과 우측에서 가장 세로 길이가 큰 직사각형을 구하고, 중간 부분부터 가로의 길이를 확장해 나가면서 가로의 길이가 큰 직사각형을 구한다. 세로 길이가 큰 직사각형의 넓이를 구하는 함수를 getArea 라고 하고 중간 영역부터 확장해서 직사각형의 넓이를 구하는 함수를 getMidArea 라고 할 때 수동 풀이는 다음과 같다.
getArea(0, 7)
getArea(0, 3)
getArea(0, 1)
getMidAread(0, 1, 0)
maxArea : 4
getArea(2, 3)
getMidAread(2, 3, 2)
maxArea : 6
getMidArea(0, 3, 1)
maxArea : 8
getArea(4, 7)
getArea(4, 5)
getMidAread(4, 5, 4)
maxArea : 5
getArea(6, 7)
getMidAread(6, 7, 6)
maxArea : 6
getMidArea(4, 7, 5)
maxArea : 6
getMidArea(0, 7, 3)
maxArea : 10
이 풀이방식의 정답도 10 이다.
문제를 절반으로 나누어서 재귀 호출하고, 각각 O(N) 시간만큼 소요되니 O(NlgN) 시간 복잡도를 가진다. getMidArea 부분을 살펴보면 N 크기의 배열을 나누어서 문제를 푸는데 getMidArea(0,7,3) 처럼 최악의 케이스가 N 복잡도를 가지기 때문이다.
4. 팩트추출
Fact 1:스택 활용편의 예제를 살펴보면, "직사각형의 가로 넓이를 확장해 나가는 방향은 자신의 높이보다 작으면서 양 옆에 있는 높이 중 큰 높이를 골라야 한다." 는 점을 알 수 있다. 이 논리와 더불어 순차적으로 문제를 풀기 때문에 (0 => N) 자신의 크기보다 작은 높이가 나왔을 때 비로소 자신과 그 이전 크기들을 한 꺼번에 계산한다. 계산하는 방식을 보면 데이터를 쌓아두었다가 마지막부터 계산하므로 스택 구조를 사용해야 하는 것을 알 수 있다.
Fact 2 : 문제를 좌측에서 가장 큰 사각형과 우측에서 가장 큰 사각형, 중간에서 가장 큰 사각형을 구하는 문제로 분할할 수 있다. 분할 문제이긴 하지만 이전에 계산한 답안을 재사용하진 않는다. 따라서 DP 문제로 풀 수는 없고 분할정복으로만 풀 수 있다.
Fact 3:문제를 중심으로 분할해서 재귀로 풀 경우, 좌측에서 가장 큰 사각형을 구하는 부분과 우측에서 가장 큰 사각형을 구하는 부분은 막대의 넓이가 1 일때 세로 길이가 가장 큰 사각형이다. 결국 중간에서 가장 큰 사각형을 구하는 함수 부분이 핵심이다.
5.문제전략
문제 전략은 예제 풀이(수동)과 팩트 추출을 통해 알아보았다. 스택을 활용하는 방식과 분할 정복으로 문제를 풀 수 있다.
6.소스코드
1) 스택활용
private static long getArea(int len) {
Stack<Integer> stack = new Stack<>();
long max=0;
for (int i=0; i<N; i++) {
while (!stack.isEmpty() && histogram[stack.peek()] > histogram[i]) {
int index = stack.pop();
int width = stack.isEmpty() ? i : i-stack.peek()-1;
max = Math.max(max, (long)width*histogram[index]);
}
stack.push(i);
}
while(!stack.isEmpty()) {
int index = stack.pop();
int width = stack.isEmpty() ? N : N-stack.peek()-1;
max = Math.max(max, (long)width*histogram[index]);
}
return max;
}
2) 분할정복
private static int getArea(int left, int right) {
if (left == right) return histogram[left];
int mid = (left + right) / 2;
int max = Math.max(getArea(left, mid), getArea(mid+1, right));
max = Math.max(max, getMidArea(left, right, mid));
return max;
}
private static int getMidArea(int left, int right, int mid) {
int leftPointer = mid;
int rightPointer = mid+1;
int height = Math.min(histogram[leftPointer], histogram[rightPointer]);
int result = height*2;
while (left<leftPointer || rightPointer<right) {
if(rightPointer < right && (leftPointer == left || histogram[leftPointer-1] < histogram[rightPointer+1])) {
++rightPointer;
height = Math.min(height, histogram[rightPointer]);
} else {
--leftPointer;
height = Math.min(height, histogram[leftPointer]);
}
result = Math.max(result, height * (rightPointer - leftPointer +1));
}
return result;
}
