DP22
Updated:
0-1 Knapsack 알고리즘 수행
FOR i in 0 -> n: K[i,0] <- 0
FOR w in 0 -> w: K[0,w] <- 0
FOR i in 1 -> W
FOR w in 1-> W
IF wi > w
K[i,w] <- K[i-1,w]
ELSE
K[i,w] <- max(vi + K[i-1, w-wi], K[i-1,w])
RETURN K[n,w]
- Line 1~2에서는 아래와 같이 배열의 0번 행과 0번 열의 각 원소를 9으로 초기화한다.
- Line 3에서는 물건을 하나씩 고려하기 위해서 , 물건 번호 i가 1~4까지 변하며, line4에서는 배낭(임시)용량 w가 1kg씩 증가되어 마지막엔 배낭의 용량인 10kg이 된다.
import java.util.Scanner;
public class DP1_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];
for(int i=1; i<=N; i++) {
weights[i] = sc.nextInt();
profits[i] = sc.nextInt();
}
int[] D = new int[W+1];
//1차원 배열 활용하는 방법
for(int i=1; i<=N; i++) {
for(int w = W; w>=weights[i]; w--) {
//해당 물건을 가방에 넣을 수 있다.
D[w] = Math.max(D[w], profits[i] + D[w-weights[i]]);
}
}
System.out.println(D[W]);
}
}
최장 증가 수열의 길이는? (LIS)
- 다음과 같이 어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있다. 3,2,6,4,5,1
- 이 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열의 길이는 얼마일까?
- Longest Increasing Subsequence
- 최장 증가 수열 Brute-foce 접근방법
- 수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지 판별한다. 증가 수열 중 가장 길이가 긴 값을 구한다.
DP접근방법1
- 입력 : 숫자열 a1,a2,…,an
- LIS(i) : a1, a2, …, ai에서 최장 부분 수열의 길이
- LIS(i)를 LIS(1), LIS(2),…,LIS(i-1)와의 관계로 표현 할 수 있을까?
- case1 : LIS(i)가 ai를 포함하지 않는다면, LIS(i)= LIS(i-1) 이방법 X
- case2 : LIS(i)가 ai를 포함한다면, LIS(i) = ?
- 증가 수열의 관계인 aj < ai인 aj 찾는다.
- j값을 알 수 없으므로 모두 검색해야 한다.
- 그 중 최대값을 찾아 1증가시켜 LIS(i)에 저장한다.
LIS(i) = 1 + max LIS(j) j<i and aj<ai- LIS()중에서 최대값을 찾는다.
DP접근 알고리즘
- O(n^2)
FOR i in 1 -> n
LIS[i] = 1
FOR j in 1-> i-1
IF aj<ai AND LIS[i] <1 + LIS[j]
LIS[i] = 1 + LIS[j]
RETURN max LIS[]
- 시간복잡도 O(N^2)
- Bruteforce보다 효율적이지만 n이커지면 시간이 오래걸린다.
import java.util.Scanner;
public class DP2_LISTest1 {
//O(n^2)
//Bruteforce보다는 효율적이지만 n이커지면 안좋다.
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();
}
int max = 0;//전체중의 최대길이
for(int i=0; i<N; i++) {
LIS[i] = 1;
for(int j = 0; j<i; j++) {//j : i의 앞쪽 원소
if(arr[j]<arr[i] && LIS[i] < LIS[j]+1) {
LIS[i] = LIS[j]+1;
}
}//i를 끝으로 하는 최장길이 값 계산 완료
max = Math.max(max, LIS[i]);
}
System.out.println(max);
}
}
DP 접근방법2
- LIS[i] : i길이를 LIS롤 하는 가장 작은 끝값
- 시간복잡도 O(log N)
- 이진탐색으로 자신의 위치를 찾는다.
- 이진 검색을 이용한 보다 효율적인 방법
- C[k] : 길이 k의 증가 수열에 대하여 가장 작은 값은 C[k]에 저장
- 각 위치에서 C[]를 갱신하기 위해 이진 검색을 수행한다.
import java.util.Arrays;
import java.util.Scanner;
public class DP2_LISTest2 {
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();
}
int size = 0; //LIS에 채워진 원소 수
for(int i=0; i<N ; i++) {
// 중복값이 없으므로 탐색 실패. 음수값 ==> 삽입위치로 환산
int temp = Math.abs(Arrays.binarySearch(LIS, 0, size, arr[i]))-1;
LIS[temp] = arr[i];
if(temp == size) {
size++;
}
}
System.out.println(size);
}
}
모든 쌍 최단 경로
- 다익스트라 : O(N^3)
- 플로이드로샬 : O(N^3)
- 시간복잡도는 똑같으나 플로이드로샬이 실수할 확률도 작고, 더 빠르다
- Brute-force 접근방법
- 한 정점에서 다른 정점으로의 모든 경로를 구한 뒤, 그들 중에서 최단 경로를 찾는다.
- 그래프가 n개의 정점을 가지고 있고, 완전그래프라고 가정하면
- 한 정점 i에서 어떤 정점 j로 가는 경로들을 다 모아보면, 그 경로들 중에서 나머지 모든 정점을 한번씩은 꼭 거쳐서 가는 경로들도 포함되어 있는데, 그 경로들의 수만 우선 계산해보자.
- i에서 출발하여 처음에 도착할 수 있는 정점의 가지 수는 n-2개이고, 그 중에 하나를 선택하면, 그 다음에 도착할 수 있는 정점의 가지 수는 n-3개 이고, 이렇게 계속하여 계산해 보면 총 경로의 개수는 (n-2)(n-3)..1 = (n-2)!이 된다.
- 이 경로의 개수만 보아도 지수보다 훨씬 크므로, 이 알고리즘은 절대적으로 비효율적이다.
- 이 문제를 해결하려면, 각 점을 시작점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행한다.
- 이때의 시간복잡도는 인접행렬을 사용하면 O(n^3)이다. 단, n은 정점의 수이다.
- Warshall은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안했고, Floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안하였다.
- 따라서 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘을 플로이드 워샬 알고리즘이라고 한다.
- 플로이드 알고리즘의 시간복잡도는 O(n^3)으로 다익스트라의 시간복잡도와 동일하다.
- 그러나 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다.
DP 접근방법
- 동적 계획 알고리즘으로 모든 쌍 최단 경로 문제를 해결하려면 먼저 부분문제들을 찾아야한다.
- 이를 위해 일단 그래프의 정점의 수가 적을 때를 생각해보자.
- 그래프에 3개의 정점이 있는 경우, 정점 i에서 정점 j까지의 최단 경로를 찾으려면 2가지 경로, 즉, 정점 i에서 정점 j로 직접 가는 경로와 정점 1을 경유하는 경로 중에서 짧은 것을 선택하면 된다.
- 또 하나의 중요한 아이디어는 경유 가능한 정점들을 : 정점 1로부터 시작하여, 정점 1과 2, 그다음에 정점 1,2,3으로 하나씩 추가하여, 마지막에는 정점 1~n까지의 모든 정점을 경유 가능한 정점들로 고려하면서, 모든 쌍의 최단 경로의 거리를 계산한다.
- 부분문제 정의 : 단, 입력 그래프의 정점을 각각 1,2,3,…,n이라 하자.
- Dijk = 정점{1,2,,,k}만을 경유 가능한 정점들로 고려하여, 정점 i로부터 정점 j까지의 모든 경로 중에서 가장 짧은 경로의 거리
- 여기서 주의할 점은 정점 1에서 정점 k까지의 모든 정점들을 반드시 경유하는 경로를 의미하는 것이 아니다.
- 여기서 k!=i, k!=j이고, k=0인 경우, 정점 0은 그래프에 없으므로 어떤 정점도 경유하지 않는다는 것을 의미한다. 따라서 Dij0은 입력으로 주어지는 선분(i,j)의 가중치이다.
- Dij1은 i에서 정점 1을 경유하여 j로 가는 경로와 i에서 j로 직접 가는 경로, 즉, 선분(i,j), 중에서 짧은 거리이다.
- 따라서 모든 쌍 i와 j에 대하여 Dij1을 계산하는 것이 가장 작은 부분 문제들이다. 단 i!=1, j!=1이다.
- 그다음엔 i에서 정점 2를 경유하여 j로 가는 경로의 거리와 Dij1중에서 짧은 거리를 Dij2로 정한다. 단 정점 2를 경유하는 경로는 Di21 + D2J1이다.
- 모든 쌍 i와 j에 대하여 Dij2를 계산하는 것이 그 다음으로 큰 부분 문제들이다. 단, i!=2, j!=2이다.
- 정점 i에서 정점 k를 경유하여 j로 가는 경로의 거리와 Dij(k-1)중에서 짧은 것으로 정한다. 단 정잠 k를 경유하는 경로의 거리는 Dik(k-1) + Dkj(k-1)이고 i!=k, j!=k이다.
- 이런 방식으로 k가 1에서 n이 될때까지 Dijk를 계산해서, Dijn, 즉, 모든 정점을 경유 가능한 정점들로 고려한 모든 쌍 i와 j의 최단경로의 거리를 찾는 방식이 플로이드의 모든 쌍 최단 경로 알고리즘이다.
모든 쌍 최단 경로 알고리즘
D[i][j] = 정점 i에서 정점 j로의 최소비용 AllPairsShortest(D[][]) FOR k in 1->n //경유지를 고정 FOR i in 1->n (단, i!=k)// 출발지 FOR j in 1-> n (단, j!=k, j!=i) //도착지 D[i][j] <- min(D[i][k] + D[k][j], D[i][j]) - Line1의 for-루프는 k가 1에서 n까지 변하는데, 이는 경유 가능한 정점을 1부터 n까지 확장 하는것.
- Line2~3 : 점들의 각 쌍을 하나씩 고려하기 위한 루프(단, i-i,라든가 i=k또는 j=k의 경우 제외)
- Line 4 : 각 정점의 쌍 i-j 에 대해 i에서 j까지의 거리가 k를 포함하여 경유하는 경로의 거리, 즉, D[i][k] + D[k][j]와 정점 {1,2,…,(k-1)}만을 경유 가능한 점들로 고려하여 계산된 최단 경로의 거리 D[i][j]가 짧은 지를 결정하여 D[i][j]를 갱신한다.
Leave a comment