의존 관계를 외부에서 주입(Dependecy Injection(DI))받는 것이 아닌, 직접 필요한 의존 관계를 찾는 것을 의존관계 조회(탐색) (Dependency Lookup(DL)) 이라고 한다. Spring 의 Application Context 전체를 주입받게 된다면, Spring Container 에 종속적인 코드가 되고, 그로 인해 단위 테스트도 어려워지게 된다. 이 때 필요한 것이 의존 관계 조회이다.
2. 본론
Spring 에서는 ObjectProvider 인터페이스로 DI Container 에서 해당 객체를 찾아 반환해준다.
DI Container 로 관리되는 Bean 객체들이 서로 의존성으로 엮여 있다면, 단위 테스트하기 많이 불편해지는데 해당 객체에서 필요한 객체들만 가지고 와 테스트하거나 의존성을 맺을 수 있므로 엄청난 이점을 가져다 준다. 사용방법은 단순하다.
ObjectProvider<찾고자 하는 클래스> testProvider = new ObjectProvider<>();
찾고자 하는 클래스 test = testProvider.getObject()
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.ObjectProvider;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;
import org.springframework.context.annotation.Scope;
import javax.annotation.PostConstruct;
import javax.annotation.PreDestroy;
import static org.assertj.core.api.AssertionsForClassTypes.assertThat;
public class SingletonWithPrototypeTest1 {
@Test
void prototypeFind() {
AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(PrototypeBean.class);
PrototypeBean prototypeBean1 = ac.getBean(PrototypeBean.class);
prototypeBean1.getCount();
assertThat(prototypeBean1.getCount()).isEqualTo(1);
PrototypeBean prototypeBean2 = ac.getBean(PrototypeBean.class);
prototypeBean2.getCount();
assertThat(prototypeBean2.getCount()).isEqualTo(1);
}
@Test
void singletonClientUsePrototype() {
AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(ClientBean.class, PrototypeBean.class);
ClientBean clientBean1 = ac.getBean(ClientBean.class);
int count1 = clientBean1.logic();
assertThat(count1).isEqualTo(1);
ClientBean clientBean2 = ac.getBean(ClientBean.class);
int count2 = clientBean2.logic();
assertThat(count2).isEqualTo(1);
}
@Scope("singleton")
static class ClientBean {
@Autowired
private ObjectProvider<PrototypeBean> prototypeBeanProvider;
public int logic() {
PrototypeBean prototypeBean = prototypeBeanProvider.getObject();
prototypeBean.addCount();
int count = prototypeBean.getCount();
return count;
}
}
@Scope("prototype")
static class PrototypeBean {
private int count = 0;
public void addCount() {
count++;
}
public int getCount() {
return count;
}
@PostConstruct
public void init() {
System.out.println("PrototypeBean.init " + this);
}
@PreDestroy
public void destory() {
System.out.println("PrototypeBean.destory");
}
}
}
스프링의 ObjectProvider 말고도 JSR330 Provider자바 표준 프로바이더도 있다.
implementation 'javax.inject:javax.inject:1' 만 의존성 추가해주면 사용이 가능하고 앞에 구문에서 ObjectProvider 를 Provider 로 수정하면 된다.
W x H 크기의 직사각형 감옥이 있다. 이 감옥에는 두 명의 죄수가 있는데 이 두 죄수를 탈출시키기 위해서 열어야 하는 문의 최소 개수값은 얼마인지 구하시오. 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다. 문은 한 번 열리면 계속 열린 상태가 된다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다. (죄수 - 감옥 - 죄수 모두 연결 상태)
2.문제예제
3.팩트추출
Fact 1: Dijkstra 알고리즘 문제처럼 보인다. 그런데 출발지가 두 군데이고, 두 군데에서 같이 움직이면 BFS 의 경로 정보가 변질되어 버린다. [Programmers] 등산 코스 정하기 (Java) :: 골드에그 (tistory.com) 문제 같은 경우는 어디서 출발하던지 산봉우리에 도달하는 최소 경로만 찾으면 되므로 같이 움직여도 상관 없지만, 이 문제는 두 사람이 같은 경로로 탈출해야 한다는 점이 다르다.
같이 움직일 수 없다면 따로 움직여서 정보를 합쳐야 하는데 어떤 정보를 기준으로 합쳐야 할까?
어떠한 지점에서 BFS 최소 결과 값을 합친다면, 그 의미는 두 사람이 그 지점으로 만나기 위한 최소 값이다.
위 예제에서는 A 에서 1 로 가는 최소의 경로가 1 이고 B 에서 1 로 가는 최소의 경로가 2 인 것이다. A 와 B 가 만나기 위한 최소 값이라고 해석할 수 있다. 그런데 이 정보만으로는 부족하다. 탈출하기 위한 루트가 포함되지 않았다. A 와 B 는 만났지만, 탈출하기 위한 최소값이라고 볼 수는 없다.
탈출하기 위한 경로를 계산하려면, 탈출구에서 해당 지점까지 가는 경로도 추가해야 한다.
모든 경로가 최소가 되려면, A 에서 1 지점까지 거리도, B 에서 1 지점까지 거리도, 1 지점에서 탈출구까지 거리도 모두 최소여야 하기 때문이다. 만나는 지점을 중심으로 생각해보면 쉽다.
Fact 2: 탈출구에 대한 정보를 맵 입력을 받을 때 알 수 없으므로 원래 맵 크기보다 1사이즈 더 크게 만들어 탈출구에서 오는 길목을 만들어준다. 원래 맵 크기가 N X M 이라면 N+2 X M+2 크기의 맵에서 시작한다.
Fact 3 :정보를 합칠 때 중요한 점은 중복 정보를 제거해야 한다는 것이다. 1 지점까지 가는데 어떤 정보들이 중복이 되는지 생각해보아야 한다. 지문에서 문이 한 번 열리면 계속 열린 상태가 된다고 하였으므로 세 정보를 합칠 때 문에서 중복 카운트는 빼주어야 한다. 여기서는 세 명이 만난다고 가정해도 되므로 -2 를 해주면 된다.
4.문제풀이(수동)
위 팩트추출을 통해 알아본 알고리즘으로 첫 번째 예제를 풀어보면 다음과 같다.
(출처 : BOJ 9376 · 탈옥 — PROJECT REBAS)
(출처 : BOJ 9376 · 탈옥 — PROJECT REBAS)
(출처 : BOJ 9376 · 탈옥 — PROJECT REBAS)
5.문제전략
문제 전략은 팩트 추출과 문제 풀이를 통해 알아보았다. 원래 맵 크기보다 한 사이즈 큰 맵을 준비하고, 탈출구에서 오는 최소 DFS 결과 값과 각 죄수들로부터 DFS 한 결과 값을 합쳐 최소 경로를 구한다.
6.소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int row, column;
private static char[][] map;
private static Node[] prisoners;
private static final int[] dx = { 0, 0, -1, 1 };
private static final int[] dy = { 1, -1, 0, 0 };
private static final char WALL = '*';
private static final char DOOR = '#';
private static final char PRISONER = '$';
static class Node implements Comparable<Node>{
int x, y, open;
Node(int x, int y) {
this.x = x;
this.y = y;
this.open = 0;
}
Node(int x, int y, int open) {
this.x = x;
this.y = y;
this.open = open;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.open, o.open);
}
}
private static int[][] bfs(Node start) {
PriorityQueue<Node> queue = new PriorityQueue<>();
int[][] visited = new int[row+2][column+2];
for (int[] visit: visited) {
Arrays.fill(visit, -1);
}
queue.offer(start);
visited[start.x][start.y] = 0;
while(!queue.isEmpty()) {
Node current = queue.poll();
for (int i = 0; i < 4; i++) {
int neighborX = current.x + dx[i];
int neighborY = current.y + dy[i];
if(neighborX < 0 || neighborX >= row+2 || neighborY < 0 || neighborY >= column+2) continue;
if(visited[neighborX][neighborY] != -1 || map[neighborX][neighborY] == WALL) continue;
if(map[neighborX][neighborY] == DOOR) {
visited[neighborX][neighborY] = visited[current.x][current.y] + 1;
queue.offer(new Node(neighborX, neighborY, current.open + 1));
} else {
visited[neighborX][neighborY] = visited[current.x][current.y];
queue.offer(new Node(neighborX, neighborY, current.open));
}
}
}
return visited;
}
private static int getSum(int[][] one, int[][] two, int[][] out) {
int minSum = row * column;
for (int i = 0; i < one.length; i++)
{
for (int j = 0; j < one[i].length; j++)
{
if (map[i][j] == WALL)
continue;
if (one[i][j] == -1 && two[i][j] == -1 && out[i][j] == -1)
continue;
int sum = one[i][j] + two[i][j] + out[i][j];
if (map[i][j] == DOOR)
{
sum -= 2;
}
if (minSum > sum)
{
minSum = sum;
}
}
}
return (minSum);
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCase = Integer.parseInt(br.readLine());
while(testCase-- > 0) {
st = new StringTokenizer(br.readLine());
row = Integer.parseInt(st.nextToken());
column = Integer.parseInt(st.nextToken());
map = new char[row+2][column+2];
int[][] prisonerOne, prisonerTwo, out;
prisoners = new Node[2];
int prisonersIndex = 0;
for (int i = 0; i < row; i++) {
char[] row = br.readLine().toCharArray();
for (int j = 0; j < column; j++) {
if (row[j] == PRISONER) {
prisoners[prisonersIndex++] = new Node(i + 1, j + 1);
}
map[i+1][j+1] = row[j];
}
}
out = bfs(new Node(0,0));
prisonerOne = bfs(prisoners[0]);
prisonerTwo = bfs(prisoners[1]);
System.out.println(getSum(prisonerOne, prisonerTwo, out));
}
}
}
각 문제마다 조건이 추가된다. 이 이항계수 시리즈는 수학적인 사고력을 높이고 특히 모듈러 연산에 대해 깊게 생각할 수 있게 해주는 문제들이다.
이항 계수 (1)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static long factorial(long n) {
long result = 1;
while(n > 1) {
result = (result * n);
n--;
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long N = Long.parseLong(st.nextToken());
long R = Long.parseLong(st.nextToken());
long first = factorial(N);
long second = factorial(R) * factorial(N-R);
System.out.println(first / second);
}
}
이항 계수 (2)
이항 계수 (3)
+ 이항 계수 결과 값을 특정 숫자로 나누었을 때 나머지를 출력해야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private final static long P = 1000000007;
private static long factorial(long n) {
long result = 1;
while(n > 1) {
result = (result * n) % P;
n--;
}
return result;
}
private static long pow(long base, long exponent) {
long result = 1;
while (exponent > 0) {
if (exponent % 2 == 1) {
result *= base;
result %= P;
}
base = (base * base) % P;
exponent /= 2;
}
return result;
}
/*
* [*] nCr mod P = n! / r! (n-r)! mod P
* = n! * (r! * (n-r)!)^-1 mod P ( ※ 나눗셈에 대한 mod 연산은 없으므로 곱하기 연산으로 바꾸어 준다. )
* = ( n! mod P * (r! * (n-r)!)^-1 mod P ) mod P ( ※ 곱셈에 대한 mod 연산으로 바꾸어 준다. )
*
* [*] 페르마 정리 a^p mod p = a mod p 응용하여 a mod p 의 역원 구하기
* = a^p-1 mod p = 1 mod p ( ※ 양 쪽에 a^-1 를 곱하였다. )
* = a * a^p-2 mod p = 1 mod p 이므로 a mod p 의 역원은 a^p-2 mod p 이다.
*
* = ( n! mod P * (r! * (n-r)!)^p-2 mod P ) mod P ( ※ a mod p 의 역원으로 바꾸어 준다. )
* */
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long N = Long.parseLong(st.nextToken());
long R = Long.parseLong(st.nextToken());
long first = factorial(N);
long second = pow(factorial(R) * factorial(N-R) % P, P-2);
System.out.println(first * second % P);
}
}
R x C 직사각형 모양의 호수가 존재한다. 이 호수에는 백조가 두 마리 존재하는데 빙판이 있어 서로 만날 수 없다. 하루가 지날 때마다 물에 인접한 빙판들은 모두 녹는다고 할 때 며칠이 지나야 백조 두 마리가 만날 수 있는지 구하시오.
2.문제예제
3.문제풀이(수동)
전형적인 BFS 문제로 수동 풀이는 진행하지 않는다. 지문에서 언급한 내용처럼 물에 인접한 빙판들은 모두 녹는다.
녹을 때 두 백조가 만날 수 있는지만 체크하면 된다.
4.팩트추출
Fact 1: 전형적인 BFS 문제이다. 한 번 맵을 훑으면서 빙판을 녹이고, 백조가 서로 만나는지 다시 맵을 훑으면 된다. 단순 BFS 구현 문제라고 생각이 들지만, R 과 C 가 무려 1500 으로 한 번 맵을 탐색할 때마다 1500 * 1500 시간복잡도가 발생한다. 그것도 빙판을 녹일 때 한 번, 백조가 서로 만나는지 확인하기 위해 한 번 수행하면 총 1500 * 1500 * 2 시간복잡도가 된다. 조금 더 효과적으로 BFS 를 수행해야 한다.
Fact 2:백조 중심으로 BFS 를 수행하면 빙판을 만나거나 백조를 만나거나 두 가지 경우를 만나게 된다. 백조를 만나면 그 동안에 계산된 day 를 리턴하면 되고, 빙판을 만났다면 그 빙판들을 기억하기 위해 모두 큐에 담아 그 큐에서부터 다시 시작하면 된다. 빙판을 녹이기 위한 BFS 는 따로 수행해서 서로 영향을 미치지 않게 동작시킨다. 따라서, Water 에 대한 큐, 다음 검색을 위한 큐가 필요하다.
5.문제전략
문제 전략은 팩트 추출을 통해 알아보았다. 백조 중 하나부터 시작해서 dfs 를 수행하고 빙판을 만나면 그 지점들을 기억했다가 다시 그 부분부터 dfs 를 시작하면 된다. 다시 dfs 를 시작하기 전 빙판이 녹아야 하므로 빙판에 대한 dfs 를 한 번 수행한다.
6.소스코드
package org.example;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int R, C;
private static Node[] swan;
private static char[][] map;
private static Queue<Node> queue, waterQueue;
private static boolean[][] visited;
private static final int[] dr = { -1, 1, 0, 0 };
private static final int[] dc = { 0, 0, -1, 1 };
private static int day = 0;
static class Node {
int r, c;
Node(int r, int c) {
this.r = r;
this.c = c;
}
}
private static void waterBFS() {
// 한 번만 녹여야 하므로, 현재 큐 사이즈만큼만 돌린다.
int waterSize = waterQueue.size();
while (waterSize-- > 0) {
Node now = waterQueue.poll();
for (int i = 0; i < 4; i++) {
int nextR = now.r + dr[i];
int nextC = now.c + dc[i];
if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0) continue;
if (map[nextR][nextC] == 'X') {
map[nextR][nextC] = '.';
waterQueue.offer(new Node(nextR, nextC));
}
}
}
}
private static void BFS() {
boolean meet = false;
while (true) {
Queue<Node> nextQueue = new LinkedList<>();
while (!queue.isEmpty()) {
Node now = queue.poll();
if (now.r == swan[1].r && now.c == swan[1].c) {
meet = true;
break;
}
for (int i = 0; i < 4; i++) {
int nextR = now.r + dr[i];
int nextC = now.c + dc[i];
if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0 || visited[nextR][nextC]) continue;
visited[nextR][nextC] = true;
if (map[nextR][nextC] == 'X') {
nextQueue.offer(new Node(nextR, nextC));
continue;
}
queue.offer(new Node(nextR, nextC));
}
}
if (meet) break;
queue = nextQueue;
waterBFS();
day++;
}
return;
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
swan = new Node[2];
queue = new LinkedList<>();
waterQueue = new LinkedList<>();
visited = new boolean[R][C];
int swanIndex = 0;
for (int i = 0; i < R; i++) {
char[] line = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
map[i][j] = line[j];
if(map[i][j] == 'L') {
swan[swanIndex++] = new Node(i, j);
}
if(map[i][j] != 'X') {
waterQueue.offer(new Node(i, j));
}
}
}
queue.offer(swan[0]);
visited[swan[0].r][swan[0].c] = true;
BFS();
System.out.println(day);
}
}
정수를 하나씩 외칠 때마다 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 현재까지 모은 숫자의 갯수가 짝수 개라면 중간에 있는 두 수 중에서 짝수를 말해야 한다.
2.문제예제
3.문제풀이(수동)
위 문제 예제 입력 1번에 대해서 문제풀이한다.
숫자를 하나씩 받을 때마다 정렬하여 중간에 있는 숫자를 출력하면 된다. 숫자가 짝수 개일때는 둘 중에 작은 숫자를 출력한다.
1 => 1
1, 5 => 1 (짝수이므로 둘 중에 작은 숫자)
1, 5, 2 => 2
1, 5, 2, 10 => 2 (짝수이므로 둘 중에 작은 숫자)
-99, 1, 2, 5, 10 => 2
-99, 1, 2, 5, 7, 10 => 2(짝수이므로 둘 중에 작은 숫자)
-99, 1, 2, 5, 5, 7, 10 => 5
4.팩트추출
Fact 1: 숫자를 받을 때마다 그 리스트를 정렬하여 중간 값을 가지고 오면 문제는 쉽게 풀린다. 다만 지문에서 확인할 수 있듯이, 아래와 같이 N 이 최대 100,000 이며, 받을 때마다 정렬하면 매번 O(N) 시간이 소요된다. 이러면 시간제한인 0.1초를 해결할 수 없을 것이다. 0.1초라는 시간을 만족하려면 삽입할 때마다 정렬하는 시간도 줄여야 하고 중간 값을 탐색하는 시간도 줄여야 한다. 정렬, 탐색 시간을 모두 줄여야 한다.
Fact 2: 아래 사이트에서 자바 Collection 들에 대한 시간복잡도를 모두 찾아보았다.
이 자료구조들에서 아이템을 삽입했을 때 자동정렬해주는 자료구조는 PriorityQueue 밖에 없다. O(log N) 으로 삽입과 동시에 정렬을 하기 때문에 빠르게 수행할 수 있다. 그리고 중간 값을 찾아주는 메서드는 어느 자료구조에도 없다. 결국 탐색해야 한다. Priority Queue 의 peek O(1) 시간 복잡도를 활용할 수 있는 방안은 없을까?
Priority Queue 의 peek 은 우선순위가 가장 높은 아이템 하나를 뽑으므로 중간에 peek 을 가리킬 수 있도록 Priority Queue 를 두 개 준비한다면 중간값을 바로 찾을 수 있을 것이다. 우선순위는 서로 반대이므로 왼쪽이 Max Heap, 오른쪽이 Min Heap 이 되어야 한다. Max Heap 은 내림차순으로 정렬되어 있는 자료구조로 가장 큰 값이 우선순위가 높고, Min Heap 은 오름차순으로 정렬되어 있는 자료구조로 가장 작은 값이 우선순위가 높다.
매번 삽입할 때마다 정렬하므로 maxHeap 의 peek 은 절반 중 가장 큰 값이고, minHeap 의 peek 은 절반 중 가장 작은 값이다. 아이템을 minHeap 에 넣든 maxHeap 에 넣든 상관없지만, 위 구조를 만족시키려면 minHeap 의 최소값이 maxHeap 의 최대값보다 항상 크도록 만들어주어야 한다. 넣고 나서 비교하고 maxHeap peek 숫자가 크다면 바꾸어 주면 된다.
5.문제전략
문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. minHeap 과 maxHeap 을 절반씩 만들어 값을 번갈아 가며 넣고 peek 으로 중간값을 꺼낸다.
6.소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
for(int i = 0 ; i < n; i++){
int num = Integer.parseInt(br.readLine());
if(minHeap.size() == maxHeap.size()) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
if(!minHeap.isEmpty() && !maxHeap.isEmpty())
if(minHeap.peek() < maxHeap.peek()){
int tmp = minHeap.poll();
minHeap.offer(maxHeap.poll());
maxHeap.offer(tmp);
}
sb.append(maxHeap.peek() + "\n");
}
System.out.println(sb);
}
}
주인공의 배낭은 최대 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());
}
}
