[Algorithm] DP2
목차
0/1 배낭(Knapsack) 문제
- 초록색: 최적해를 따질 때 물건 i를 포함하지 않는 경우
- 하늘색: 최적해를 따질 때 물건 i를 고려한 경우
DP로 풀어내려면, 구해진 부분문제의 해가 다음 문제를 해결하는 데 쓰일 수 있어야 하고(부분문제의 해를 재사용), 그 위에 최적화를 적용해야 한다.
i번째 물건까지 무게 w를 만족하는 최적과정에서, 그 전 단계의 결과를 사용하는 과정이 나왔다. 즉 무게 w를 만드는 가치를 구하기 전에 i-1까지 w-W, w를 만족하는 계산이 미리 되어 있으면, i번째 물건까지 무게 w를 만족하는 최적의 가치를 구할 수 있다.
package com.ssafy;
import java.util.Scanner;
public class DP_KnapsackTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int W = sc.nextInt();
int [] weights = new int[N+1];//물건의 무게정보
int [] profits = new int[N+1];//물건의 가치 정보
int [][]D = new int[N+1][W+1];//해당 물건까지 고려하여 해당 무게를 만들 떄의 최대 가치
for(int i =1; i<=N;i++) {
weights[i] = sc.nextInt();
profits[i] = sc.nextInt();
}
for(int i =1; i<=N;i++) { //첫 물건부터 고려
for(int w = 1; w<=W;W++)// 무게 1부터 고려
{
if(weights[i]<=w) {//가방에 넣을 수 있는 상황
//넣을까
Math.max(D[i-1][w-weights[i]]+profits[i],D[i-1][w]); //자신이 들어가면서 생기는 가치.
//말까
D[i][w] = D[i-1][w];
}else { //가방에 넣지 못하는 상황
D[i][w] = D[i-1][w];
}
//시간복잡도는? for 2번 돌면서 위에거 실행한다 치면 n2
//근데 재귀적이면 물건이 30개만 되도 2의 30승이였다. 굉장히 큰 차이.
//계산하는 과정에서 어떤 무게가치들이 쓰일지 모른다.
//사용되지 않은 애들도 있음. 뒤쪽에서 안 쓰일 수 있음. DP도 다 계산하는데 스마트하게 다한다(스마트한 완탐)
}
}
System.out.println(D[N][W]);
}
}
시간복잡도
- for문을 2번 돌면서 위 연산을 실행하면 O(N²)이다.
- 반면 재귀적으로 풀면 물건이 30개만 되어도 2³⁰ 수준으로, 굉장히 큰 차이가 난다.
- 계산하는 과정에서 어떤 무게/가치들이 쓰일지는 미리 알 수 없다. 사용되지 않는 값(뒤쪽에서 안 쓰일 수 있음)도 있다.
- DP도 결국 다 계산하지만, 스마트하게 다 한다(스마트한 완전탐색).
배열은 1차원으로도 가져갈 수 있다.
어려운 게 맞다. 그래도 보고 또 보고 해서 낯선 느낌이 없어지면 그래도 한 발 전진했다고 볼 수 있다.
최장 증가 수열(LIS)
기본 아이디어:
- 수열의 모든 부분집합을 구해, 그 부분집합이 증가수열인지 판별한다.
- 증가수열 중 가장 길이가 긴 값을 구한다.
냅색도 그렇고 LIS도 그렇고, 항상 넣을까 말까를 고려한다.
DP는 수도코드 그대로 구현하면 끝이다.
맨 끝인 6의 길이가 필요한 게 아니라, 모든 원소가 끝이 될 수 있고 그중 가장 길이가 긴 LIS를 선택한다.
반복을 돌면서 가장 큰 값을 찾으면 된다.
package com.ssafy;
import java.util.Arrays;
import java.util.Scanner;
public class DP_ListTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int [] arr = new int[N];//원소들 저장
int[] LIS = new int[N]; //각 원소를 마지막에 세웠을 때의 최장길이
for(int i =0; i<N;i++) {
arr[i] = sc.nextInt();
}
// Arrays.fill(LIS, 1);
int max=0; //하나씩 값 돌때마다 max 갱신하게
for(int i =0; i<N; i++) {
LIS[i]=1;//어차피 반복 돌리니까 그냥 안에서 직접 돌리자.
//자기 혼자 세웠을 떄의 길이로 초기화
for(int j =0; j<=i-1;j++) { //맨 앞부터 자신의 직전의 원소들과 비교
if(arr[j]<arr[i] && LIS[i]<LIS[j]+1) {
LIS[i] = LIS[j]+1;
}
}
if(max<LIS[i]) max = LIS[i];
}
System.out.println(max);
/* 4 1 4 3 2*/
// N2을 NlogN으로 바꾸기만 해도 대박.
// N이 10만이면 N2은 100억
// NlogN은 10만에 대한 log10만
}
}
- N²을 NlogN으로 바꾸기만 해도 대박이다.
- N이 10만이면 N²은 100억.
- NlogN은 10만에 대한 log(10만) 수준이다.
그래서 이 N²를 NlogN으로 바꿔보자.
IM / ADV 수준 정리
- 하나는 IM 수준, 하나는 ADV 수준이다. (냅색, 거스름돈, 배달할 때 밀가루봉지 문제 등)
- 문제의 테스트 케이스는 통과되어도 히든 테스트 케이스까지 통과되게 해야 한다(최적화 필요).
- IM은 정렬, 조합, 순열, 부분집합 등을 쓴다.
- 가장 만만한 건 배열로 인덱스를 마음대로 접근해 사방·팔방 탐색하는 것이 가장 단순할 수 있다.
- IM에서 그래프 탐색 같은 건 나오지 않을 거라 생각한다.
방식은 어쨌건 답이 나오면 된다. 일단 결과만 나오면 된다. 최적화를 못 해서 추가점수는 없을 수 있지만, IM은 답만 일단 나오면 된다.
LIS 개념 정리
- 수가 여러 개 = 수열
- LIS: 원소가 n개인 배열의 일부 원소를 골라내 부분 수열을 만들었을 때, 각 원소가 이전 원소보다 더 크다는 조건을 만족하면서 길이가 최대인 부분수열.
LIS[n]: 전체 수열의 n번째 값까지 고려했을 때 만들어지는 최장 수열의 길이.
어떤 기준이 되는 원소가 있을 때, 앞에서 증가하며 온 경우를 본다. 예를 들어 5의 입장에선 앞에 4개가 있는데, 앞에서 조건을 만족하는 것 뒤에 자신을 붙이면 자기를 포함한 최장 증가를 만족한다.
하지만 맨 처음에는, 기준이 되는 원소 앞에 오는 애와 뒤에 오는 애가 어떻게 될지 모르기 때문에, 해당 숫자로 만들 수 있는 최장 수열이 자기 자신만일 수도 있다.
DP로 풀어보기 (LIS)
- LIS에선 원소 순서를 바꾸면 안 된다.
- 삽입될 수 있는 자리를 찾는다.
- 정렬된 결과를 유지한다.
- 정렬된 집합 → 원소를 빠르게 탐색(이진 탐색).
모든 쌍 최단 경로
다익스트라를 여러 번 돌리면 된다.
N번 돌리면 O(N³)이다. 다익스트라가 단순한 O(N²)이 아니라 그보다 좀 완화되어 NlogN과 비슷하게 보이도록 만들면, 이를 돌릴 때 N²·logN이 된다.
최단 경로 문제란
- 한 도시에서 다른 도시로 가장 빨리 갈 수 있는 경로를 찾는 문제
- 가중치 포함, 방향성 그래프에서 최단경로 찾기
- 최적화 문제: 주어진 문제에 대해 하나 이상의 많은 해답이 존재할 때, 이 가운데에서 가장 최적인 해답을 찾아야 하는 문제
3중 for문을 돌면서, 모든 쌍의 최단경로를 구하기 위해 모든 쌍에 대한 반복을 돌린다. 이때 경유지를 계속 변화시키면서 값을 구해 간다.
이게 헷갈리면 경찰과 도둑으로 외우자…
brute-force 접근 방법
- 한 정점에서 다른 정점으로의 모든 경로를 구한 뒤, 그들 중에서 최단 경로를 찾는다.
- 그래프가 n개의 정점을 가지고 있고 완전그래프라고 가정하면, 한 정점 i에서 어떤 정점 j로 가는 경로들을 다 모아보면, 그 경로들 중에서 나머지 모든 정점을 한 번씩은 꼭 거쳐서 가는 경로들도 포함되어 있는데, 그 경로들의 수만 우선 계산해보자.
- i에서 출발하여 처음에 도착할 수 있는 정점의 가지 수는 n-2개이고, 그 중 하나를 선택하면 그 다음에 도착할 수 있는 정점의 가지 수는 n-3개이다. 이렇게 계속 계산하면 총 경로의 개수는 (n-2)(n-3)…1 = (n-2)!이 된다.
- 이 경로의 개수만 보아도 지수보다 훨씬 크므로, 이 알고리즘은 절대 비효율적이다.
DP 접근방법
- 이 문제를 해결하려면, 각 점을 시작점으로 정해 다익스트라의 최단경로 알고리즘을 수행하면 된다.
- 이때의 시간 복잡도는 인접행렬을 사용하면 O(n³)이다(단, n은 정점의 수).
- 워셜은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적계획 알고리즘을 제안했고, 플로이드는 이를 변형하여 모든 쌍 최단경로를 찾는 알고리즘을 고안했다.
- 즉, 모든 쌍 최단경로를 찾는 동적 계획 알고리즘을 플로이드-워셜 알고리즘이라 한다.
- 플로이드 알고리즘의 시간복잡도는 O(n³)으로, 다익스트라의 시간복잡도와 동일하다.
- 그러나 플로이드 알고리즘은 매우 간단하여, 다익스트라 알고리즘을 사용하는 것보다 효율적이다.
2번만 경유지로 쓰는 게 아니라 경유지를 추가한다.
경유지를 바꾸는데, 직접비용과 비교하는 게 아니라 n-1번째로 추가하는 경유지라면 정점 n-1까지 다 비교했을 때와 비교한다.
경유지를 늘려간다고 생각해야 한다.
하나의 중요한 아이디어는 경유 가능한 정점들
- 정점 1로 시작하여, 정점 1과 2, 그 다음엔 정점 1·2·3으로 하나씩 추가하여, 마지막엔 정점 1~n까지의 모든 정점을 경유 가능한 정점들로 고려하면서, 모든 쌍의 최단 경로 거리를 계산한다.
부분 문제 정의 (단, 입력 그래프의 정점을 각각 1,2,3,…,n이라 하자.)
- Dk = 정점 {1,2,3,…,k}만을 경유 가능한 정점들로 고려하여, 정점 i로부터 정점 j까지의 모든 경로 중에서 가장 짧은 경로의 거리
여기서 주의할 점: 이는 정점 1에서 정점 k까지의 모든 정점들을 반드시 경유하는 경로를 의미하는 것이 아니다.
i에서 j까지 최단경로만 구하는 게 아니라, 모든 쌍에 대한 최단 경로를 다 구해야 한다.
사실 플로이드-워셜은 코드가 짧아서 금방 짜지만, 그 원리와 과정을 이해하는 게 더 중요하다.
거쳐오지 않는 게 유리할 수 있고 거쳐오는 게 유리할 수 있으니, 그 중 최소값을 D[i][j]에 넣는다.
1을 띄워서 돌려보고 2를 띄워서 돌려보는 식으로, 1에서 1 가고, 1에서 2 가고, 1→3, 1→4 가고, 모두 구한다.
배열에서 분홍색 부분만 칠해진다.
1번 정점에서 다른 정점들에게 가는 최소값이 저장되고, 출발지를 2로 바꾸면 그 2 부분만 업데이트하려고 시도한다. 그런데 이 과정에서 경유지로 쓰는 값이 하늘색 부분(아직 최적이 아닌 값)인데, 그걸 이용해서 최적해를 결정하고 다 채우면 절대 업데이트가 안 일어나서 오답이 나오게 된다.
그래서 우리는 모든 쌍을 동등한 입장에서 고려해야 한다(어떤 건 경유지 1개를 고려하는데 어떤 건 2~3개를 고려하면 안 됨). 어떤 쌍이든 동등한 조건에서 고려해, 모든 쌍에 관련된 최단을 업데이트하고 모든 해에 대해 최단을 구한다.
어떤 위치에서 무엇을 쓰더라도 직전 단계의 최적해를 보장하게 해야 한다.
핵심은, 한 번씩 경유지가 늘어날 때마다 각 위치는 그 경유지까지 고려한 최단경로가 된다고 생각할 수 있다.
코드를 볼 때는 짧았는데 막상 설명을 들으면 어렵다(당연하다. trade-off라 생각하자).