Algorithm Past Paper PDF 2023.04.27

ALGORITHM 2023.04.27 Hyun-Jun Kim Software Department @Chung-ang University • Algorithms – Design and Analysis • Divide and Conquer • Sorting • Selection Algorithm • Search Tree • Hash Table • Lists • Mid-Term Examination • Dynamic Programming • Graph Algorithm 1 • Graph Algorithm 2 • Greedy Alg...

ALGORITHM 2023.04.27 Hyun-Jun Kim Software Department @Chung-ang University • Algorithms – Design and Analysis • Divide and Conquer • Sorting • Selection Algorithm • Search Tree • Hash Table • Lists • Mid-Term Examination • Dynamic Programming • Graph Algorithm 1 • Graph Algorithm 2 • Greedy Algorithm • The Theory of NP • Shortest Path • Advanced Topic • Final Examination 동적 프로그래밍 • 동적 프로그래밍이 무엇인지 이해한다. • 어떤 문제가 동적 프로그래밍의 적용 대상인지 감지할 수 있도록 한다. • 기본적인 몇 가지 문제를 동적 프로그래밍으로 해결할 수 있도록 한다. 동적 프로그래밍 • 배경 • 재귀적 해법 • 큰 문제에 닮음꼴의 작은 문제가 깃든다 • 잘쓰면 보약, 잘못쓰면 맹독 • 관계중심으로 파악함으로써 문제를 간명하게 볼 수 있다 • 재귀적 해법을 사용하면 심한 중복 호출이 일어나는 경우가 있다 동적 프로그래밍 • 재귀적 해법이 바람직한 예 • 퀵정렬, 병합정렬 등의 정렬 알고리즘 • 계승(factorial) 구하기 • 그래프의 DFS • … • 재귀적 해법이 치명적인 예 • 피보나치수 구하기 • 행렬곱셈 최적순서 구하기 • … 동적 프로그래밍 • 피보나치 수 구하기 • f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 • 아주 간단한 문제지만 – 동적 프로그래밍의 동기와 구현이 다 포함되어 있다 동적 프로그래밍 • 피보나치 수 구하기 fib(n) { if (n = 1 or n = 2) then return 1; else return (fib(n-1) +fib(n-2)); } ü 엄청난 중복 호출이 존재한다 동적 프로그래밍 • 피보나치 수열의 호출 트리 fib(7) fib(6) fib(5) fib(5) fib(4) fib(3) fib (2) fib(4) fib(3) fib(2) fib(2) fib (1) fib(3) fib (2) fib(1) fib(4) fib(3) fib(2) fib (1) fib (2) fib(3) fib(2) fib(2) fib (1) 중복 호출의 예 fib(1) 동적 프로그래밍 • 피보나치수를 구하는 동적 프로그래밍 알고리즘 fibonacci(n) { f[1] ← f[2] ← 1; for i ← 3 to n f[i] ← f[i-1] +f[i-2]; return f[n]; } ü 선형시간에 끝난다 동적 프로그래밍 • 피보나치수를 구하는 동적 프로그래밍 알고리즘2 fib(n) { //f[n]은 0으로 초기화 되어 있음 if (f[n] != 0) then return f[n]; else { if (n=1 or n=2) then f[n] <- 1 else f[n] <- fib(n-1) + fib(n-2); return f[n]; } ü Memorization 기법 동적 프로그래밍 • 동적 프로그래밍의 적용 요건 • 최적 부분구조optimal substructure – 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨 • 재귀호출시 중복overlapping recursive calls – 재귀적 해법으로 풀면 같은 문제에 대한 재귀호출이 심하게 중복됨 동적 프로그래밍이 그 해결책! 동적 프로그래밍 • 문제예 1: 행렬 경로 문제 • 양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다 • 이동 방법 (제약조건) – 오른쪽이나 아래쪽으로만 이동할 수 있다 – 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 • 목표: 행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최소화되도록 한다 동적 프로그래밍 • 불법 이동의 예 6 7 12 5 6 7 12 5 5 3 11 18 5 3 11 18 7 17 3 3 7 17 3 3 8 10 14 9 8 10 14 9 불법 이동 (상향) 불법 이동 (좌향) 동적 프로그래밍 • 유효한 이동의 예 6 7 12 5 6 7 12 5 5 3 11 18 5 3 11 18 7 17 3 3 7 17 3 3 8 10 14 9 8 10 14 9 동적 프로그래밍 • 문제의 핵심 (1, 1) (i-1, j) (i, j-1) cij = (i, j) 0 if i=0 or j=0 mji + max{ci-1, j , ci, j-1} otherwise 동적 프로그래밍 6 7 12 5 6 13 25 30 5 3 11 18 11 16 36 54 7 17 3 3 18 35 39 57 8 10 14 9 26 45 59 68 동적 프로그래밍 • 재귀 알고리즘 matrixPath(i, j) ▷ (i, j)에 이르는 최고점수 { if (i = 0 or j = 0) then return 0; else return (mij + (max(matrixPath(i-1, j), matrixPath(i, j-1)))); } 동적 프로그래밍 mat(4,4) mat(4,3) • 호출 트리의 예 mat (4,2) mat(4,1) mat(3,3) mat(3,2) mat(3,2) mat(2,2) mat(2,2) mat(3,1) mat(2,2) mat(2,3) mat(3,1) mat(3,1) mat(2,1) mat(2,1) mat(2,1) mat(1,2) mat(2,1) mat(2,1) mat(1,2) mat(2,1) mat(1,2) mat(1,2) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(3,4) mat(2,4) mat(1,4) mat(3,3) mat(2,3) mat(1,3) mat(1,3) mat(2,2) mat(1,2) mat(1,2) mat(1,2) mat(2,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(2,3) mat(2,2) mat(3,2) mat(1,3) mat(3,1) mat(2,2) mat(2,1) mat(1,2) mat(1,2) mat(2,1) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,3) 동적 프로그래밍 • DP알고리즘 matrixPath(n) ▷ (n, n)에 이르는 최고점수 { for i ← 0 to n c[i, 0] ← 0; for j ← 1 to n c[0, j] ← 0; for i ← 1 to n for j ← 1 to n c[i, j] ← mij + max(c[i-1, j], c[i, j-1]); return c[n, n]; } 동적 프로그래밍 • 문제 예 2: 돌 놓기 • 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다 • 조약돌을 놓는 방법 (제약조건) • 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다 • 각 열에는 적어도 하나 이상의 조약돌을 놓는다 • 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌 놓기 동적 프로그래밍 • 테이블의 예 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 동적 프로그래밍 • 재귀 합법적인 예 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 합법적이지 않은 예 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 Violation! 가능한 패턴 패턴 1: 패턴 2: 패턴 3: 임의의 열을 채울 수 있는 패턴은 4가지뿐이다 패턴 4: 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 서로 양립할 수 있는 패턴 1: 패턴들 2 1 3 1 1 2 3 2 1 3 2 3 2 4 패턴 2: 패턴 3: 패턴 1은 패턴 2, 3과 패턴 2는 패턴 1, 3, 4와 패턴 3은 패턴 1, 2와 패턴 4는 패턴 2와 양립할 수 있다 패턴 4: 4 2 i열과 i-1열의 관계 i-1 i 6 7 12 -5 -5 5 3 11 3 -8 10 … 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 i-1열이 패턴 1로 끝나거나 i-1열이 패턴 3으로 끝나거나 i-1열이 패턴 4로 끝나거나 동적 프로그래밍 Optimal Substructure i: 패턴 1, i-1: 패턴 2 or 3 i: 패턴 2, i-1: 패턴 1 or 3 or 4 i: 패턴 3, i-1: 패턴 1 or 2 i: 패턴 4, i-1: 패턴 2 i-1 i 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 Cip = W1p If i = 1 Max{Ci-1, q } + Wip If i > 1 Cip : i열이 패턴 p로 놓일 때 최고 점수 Wip : i열이 패턴 p로 놓일 때 i에 놓인 점수의 합 q : i열이 패턴 p일 때 올 수 있는 패턴 q 동적 프로그래밍 • 재귀 알고리즘 pebble(i, p) ▷ i 열이 패턴 p로 놓일 때의 i 열까지의 최대 점수 합 구하기 ▷ w[i, p] : i 열이 패턴 p로 놓일 때 i 열에 돌이 놓인 곳의 점수 합. p {1, 2, 3, 4} { } if (i = 1) then return w[1, p] ; else { max ← -∞ ; for q ← 1 to 4 { if (패턴 q가 패턴 p와 양립) then { tmp ← pebble(i―1, q) ; if (tmp > max) then max ← tmp ; } } return (max + w[i, p]) ; } 동적 프로그래밍 • 재귀 알고리즘 pebbleSum(n) ▷ n 열까지 조약돌을 놓은 방법 중 최대 점수 합 구하기 { } return max { pebble(n, p) } ; p =1,2,3,4 ü pebble(i, 1), …, pebble(i, 4) 중 최대값이 최종적인 답 peb(5,1) 호출 트리 peb(4,3) peb (3,1) peb(3,2) peb(2,2) peb(2,3) peb(2,1) peb(2,3) peb(2,4) peb(1,1) peb(1,3) peb(1,4) peb(1,1) peb(1,2) peb(1,2) peb(1,3) peb(1,1) peb(1,2) peb(1,2) peb(4,2) peb (3,1) peb(2,2) peb(3,3) peb(2,3) peb(1,1) peb(1,3) peb(1,4) peb(1,1) peb(1,2) peb(3,4) peb(2,1) peb(2,2) peb(2,2) peb(1,2) peb(1,3) peb(1,1) peb(1,3) peb(1,4) peb(1,1) peb(1,3) peb(1,4) 동적 프로그래밍 • DP적용 • DP의 요건 만족 • 최적 부분구조 • pebble(i, .)에 pebble(i-1, .)이 포함됨 • 즉, 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨 • 재귀호출시 중복 • 재귀적 알고리즘에 중복 호출 심함 동적 프로그래밍 6 7 12 -5 DP적용 5 3 11 3 i: 패턴 1, i-1: 패턴 2 or 3 i: 패턴 2, i-1: 패턴 1 or 3 or 4 i: 패턴 3, i-1: 패턴 1 or 2 i: 패턴 4, i-1: 패턴 2 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 6 18 39 -8 27 32 11 18 34 17 11 46 P i 동적 프로그래밍 • DP알고리즘 pebble (n) { for p ← 1 to 4 peb[1, p] ← w[1, p] ; for i ← 2 to n for p ← 1 to 4 peb[i, p] ← max {peb[i-1, q]} + w[i, p와 양립하는 패턴 q p] ; return max { peb[n, p] } ; } ü복잡도 : Θ(n) p =1,2,3,4 동적 프로그래밍 • 복잡도 분석 기껏 4 바퀴 pebble(n) { 기껏 n 바퀴 p] ; } 무시 for p ← 1 to 4 peb[1, p] ← w[1, p] ; for i ← 2 to n for p ← 1 to 4 peb[i, p] ← max {peb[i-1, q]}+w[i, p와 양립하는 패턴 q returnp =1,2,3,4 max { peb[n, p] } ; ü복잡도 : Θ(n) n * 4 * 3 = Θ(n) 기껏 3 가지 동적 프로그래밍 • 문제 예 3: 행렬 곱셈 순서 • 행렬 A, B, C • (AB)C = A(BC) • 예: A:10ⅹ100, B:100ⅹ5, C:5ⅹ50 • (AB)C: 7,500번의 곱셈 필요 • A(BC): 75,000번의 곱셈 필요 • A1, A2, A3, …, An을 곱하는 최적의 순서는? • 총 n-1회의 행렬 곱셈을 어떤 순서로 할 것인가? 동적 프로그래밍 • 재귀적 관계 • 마지막 행렬 곱셈이 수행되는 상황 – n-1가지 가능성 • • • • • • A1(A2 … An ) (A1A2)(A3 … An) (A1A2 A3)(A4 … An) ··· (A1 … An-2) (An-1An) (A1 … An-1)An – 어느 경우가 가장 매력적인가? 동적 프로그래밍 • 재귀적 관계 ü cij: 행렬 Ai, …, Aj의 곱 Ai…Aj를 계산하는 최소 비용 ü Ak의 차원: pk-1pk cij = 0 if i=j min {cik + ck+1,j + pi-1pkpj} if i<j i ≤ k ≤ j-1 일반형: (A1 … Ak) (Ak+1 … An) 동적 프로그래밍 • 재귀적 구현 rMatrixChain(i, j) ▷ 행렬곱 Ai…Aj를 구하는 최소 비용 구하기 { if (i = j) then return 0; ▷ 행렬이 하나뿐인 경우의 비용은 0 min ← ∞; for k ← i to j-1 { q ← rMatrixChain(i, k) + rMatrixChain(k+1, j) + pi-1pkpj; if (q < min) then min ← q; } return min; } ü 엄청난 중복 호출이 발생한다! 동적 프로그래밍 A 1A 2A 3A 4 j 0 A 1A 2 (A1A2)A3 Or i 0 … A1(A2A3) A 2A 3 (A2A3)A4 Or 0 A2(A3A4) A 3A 4 0 동적 프로그래밍 • 재귀적 구현 matrixChain(i, j) { for i ← 1 to n m[i, i] ← 0; ▷ 행렬이 하나뿐인 경우의 비용은 0 for r ← 1 to n-1 ▷ r: 문제 크기를 결정하는 변수, 문제의 크기 = r+1 for i ← 1 to n-r { j ← i+r; i ≤ k ≤j]j-1 m[i, ← min{m[i, k] + m[k+1, j] + pi-1pkpj}; } } return m[1, n]; ü 복잡도: Θ(n3) 동적 프로그래밍 • 문제 예 4: 최장 공통 부분순서LCS • • 두 문자열에 공통적으로 들어있는 공통 부분순서 중 가장 긴 것을 찾는다 부분순서의 예 – <bcdb>는 문자열 <abcbdab>의 부분순서다 • 공통 부분순서의 예 – <bca>는 문자열 <abcbdab>와 <bdcaba>의 공통 부분순서다 • 최장 공통 부분순서longest common subsequence(LCS) – 공통 부분순서들 중 가장 긴 것 – 예: <bcba>는 문자열 <abcbdab>와 <bdcaba>의 최장 공통 부분순서다 동적 프로그래밍 • 최적 부분 구조 • 두 문자열 Xm = <x1x2 … xm>과 Yn = <y1y2 … yn>에 대해 – xm= yn이면 Xm과 Yn의 LCS의 길이는 Xm-1과 Yn-1의 LCS의 길이보다 1이 크다 – xm≠ yn이면 Xm과 Yn의 LCS의 길이는 Xm과 Yn-1의 LCS의 길이와 Xm-1과 Yn의 LCS의 길이 중 큰 것과 같다 • cij = 0 if i = 0 or j = 0 ci-1, j-1 + 1 if i, j > 0 and xi= yj max{ci-1, j, ci, j-1} if i, j > 0 and xi ≠ yj ü cij : 두 문자열 Xi = <x1x2 … xi>과 Yj = <y1y2 … yj>의 LCS 길이 동적 프로그래밍 • 재귀적 구현 LCS(m, n) ▷ 두 문자열 Xm과 Yn의 LCS 길이 구하기 { if (m = 0 or n = 0) then return 0; else if (xm= yn) then return LCS(m-1, n-1) + 1; else return max(LCS(m-1, n), LCS(m, n-1)); } ü 엄청난 중복 호출이 발생한다! LCS(3,4) LCS(3,3) • 호출 트리의 예 LCS(3,2) LCS(2,3) LCS(2,2) LCS(1,3) LCS(0,3) LCS(1,2) LCS(1,2) LCS(0,2) LCS(1,1) LCS(0,2) LCS(1,1) LCS(2,0) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(0,1) LCS(3,0) LCS(2,1) LCS(1,1) LCS(2,0) LCS(1,1) LCS(0,2) LCS(1,1) LCS(2,0) LCS(1,1) LCS(1,0) LCS(1,0) LCS(0,1) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(2,1) LCS(2,4) LCS(1,4) LCS(2,2) LCS(3,1) LCS(2,3) LCS(2,2) LCS(1,3) LCS(0,4) LCS(1,3) LCS(0,3) LCS(1,2) LCS(0,3) LCS(1,2) LCS(0,2) LCS(1,1) LCS(0,2) LCS(1,1) LCS(0,2) LCS(1,1) LCS(2,0) LCS(1,1) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(1,2) LCS(2,1) LCS(1,2) LCS(2,1) 동적 프로그래밍 • 재귀적 구현 LCS(m, n) ▷ 두 문자열 Xm과 Yn의 LCS 길이 구하기 { for i ← 0 to m C[i, 0] ← 0; for j ← 0 to n C[0, j] ← 0; for i ← 1 to m for j ← 1 to n if (xi= yj) then C[i, j] ← C[i-1, j-1] + 1; else C[i, j] ← max(C[i-1, j], C[i, j-1]); return C[m, n]; } ü 복잡도: Θ(mn) 동적 프로그래밍 <abcb> <bdcab> i j 0 0 0 1 1 1 1 1 1 2 1 1 2 2 2 1 1 2 2 3 동적 프로그래밍 • 문제5: 최단 경로 • Weighted digraph G=(V, E) – wij : vertex i에서 vertex j에 이르는 edge의 길이 • Edge가 없으면 ∞ • 목표 – 시작점 s에서 다른 각 정점vertex에 이르는 최단거리를 모두 구한다 동적 프로그래밍 • 문제5: 최단 경로 • dtk : 중간에 최대 k 개의 edge를 거쳐 s로부터 vertex t에 이르는 최단거리 • 목표: dtn-1 • Note! For i≠s, – d t0 = ∞ – dt1 = ws,t 다음 페이지로 넘어가기 전에 무엇을 중심으로 관계를 파악할 지 스스로 생각해보자 동적 프로그래밍 • 재귀적 관계 dtk = min {drk-1+ wrt} for all edges (r, t) ds0 = 0; dt0 = ∞; 동적 프로그래밍 • DP알고리즘 Ballman-Ford(G, s) { ds ← 0; for all vertices i ≠ s di ← ∞; for k ← 1 to n-1 { for all edges (a, b) { if (da + wab < db ) then db ← da + wab ; a } } } ü Propagation 되는 모습이 떠오르면 잘 이해한 것! b 동적 프로그래밍 (a) 8 ∞ ∞ -15 0 ∞ 3 ∞ 8 -7 8 (f) i =5 8 3 11 0 (e) i =4 1 9 8 -7 8 10 8 6 11 11 4 10 -8 11 (d) i =3 19 8 4 -7 5 -12 12 8 -7 8 16 6 11 4 10 4 3 2 1 9 11 4 -6 -15 0 2 1 0 8 ∞ 5 -12 8 10 2 1 9 19 9 3 10 -15 3 4 -15 0 2 5 -12 -7 -6 9 11 ∞ ∞ 8 8 0 2 5 ∞ 1 9 ∞ -12 8 10 -15 0 11 -15 9 11 4 ∞ (c) i =2 1 9 3 ∞ 10 -15 11 ∞ 5 -12 8 8 0 2 1 9 11 (b) i =1 10 7 5 -12 12 8 -7 8 19 4 12 동적 프로그래밍 (f) i =5 8 10 -15 0 11 -15 2 1 9 3 1 0 11 5 -12 9 8 -7 8 6 4 10 (g) i =6 8 11 1 -3 3 8 -7 8 10 5 -12 8 3 11 -18 9 11 4 -5 3 8 -7 8 7 5 -12 8 6 11 -18 3 -5 2 1 9 9 11 4 10 -15 0 2 1 9 3 (i) 10 -15 0 2 1 9 3 (h) i =7 10 -15 0 11 -15 3 8 -7 8 7 5 -12 4 6