small instances first, store the results, whenever we need a result, look it up instead of recomputing it.
알고리즘: Using Divide-and-Conquer
문제: 이항계수를 계산한다
입력: 음수가 아닌 정수 n과 k, 여기서 k <= n
출력: bin, [n k]
1 2 3 4 5 6
intbin(int n, int k){ if (k == 0 || n == k) return1; else return bin(n-1, k-1) + bin(n-1, k); }
시간복잡도 분석:
분할정복 알고리즘은 작성하기는 간단하지만, 효율적이지 않음
이유? 재귀호출(recursive call)할때 같은 계산을 반복해서 수행하기 때문
예를 들면, bin(n-1, k-1)과 bin(n-1, k)는 둘다 bin(n-2, k-1)의 결과가 필요한데, 따로 중복 계산이 됨
[n: k]를 구하기 위해서 이 알고리즘이 계산하는 항(term)의 개수는 2[n: k]-1이다. (증명을 해보자)
증명: (n에 대한 수학적 귀납법으로 증명)
귀납출발점: 항의 개수 n이 1일 때 2[n: k]-1 = 2 x 1 - 1 = 1이 됨을 보이면 된다.
[1: k]는 k=0이나 1일때 1이므로 항의 개수는 항상 1이다.
귀납가정: [n: k]를 계산하기 위한 항의 개수는 2[n: k] - 1이라고 가정한다.
귀납절차: [n+1: k]를 계산하기 위한 항의 개수가 2[n+1: k] - 1임을 보이면 된다.
알고리즘에 의해서 [n+1: k] = [n: k-1] + [n: k] 이므로, [n+1: k]를 계산하기 위한 항의 총 개수는 [n: k-1]을 계산하기 위한 총 개수와 [n: k]를 계산하기 위한 항의 총 개수에다가 이 둘을 더하기 위한 항 1을 더한 수가 된다.
그런데 [n: k-1]을 계산하기 위한 항의 개수는 가정에 의해서 2[n: k-1] -1이고, [n: k]를 계산하기 위한 항의 개수는 가정에 의해서 2[n: k] - 1이다.
동적계획식 알고리즘 설계전략
Establish a recursive property (재귀 관계식을 정립):
2차원 배열 B를 만들고, 각 B[i][j]에는 [i: j]값을 저장하도록 하면, 그 값은 다음과 같은 관계식으로 계산할 수 있다.
Solve an instance of the problem in a bottom-up fashion:
[n: k]를 구하기 위해서는 다음과 같이 B[0][0]부터 시작하여 위에서 아래로 재귀 관계식을 적용하여 배열을 채워 나가면 된다. 결국 값은 B[n][k]에 저장된다.
문제: 이항계수를 계산한다.
입력: 음수가 아닌 정수 n 과 k, 여기서 k <= n
출력: bin, [n: k]
1 2 3 4 5 6 7 8 9
int bin2(int n, int k) { index i, j; int B[0..n][0..k]; for(i = 0; i <= n; i++) for(j = 0; j <= minimum(i,k); j++) if(j==0 || j==1) B[i][j] = 1; else B[i][j] = B[i-1][j-1] + B[i-1][j]; return B[n][k]; }
동적계획 알고리즘의 분석
단위연산: for-j 루프 안의 문장
입력의 크기: n, k i = 0일 때 j-루프 수행 횟수 : 1 i = 1일 때 j-루프 수행 횟수 : 2 i = 2일 때 j-루프 수행 횟수 : 3 …………… i = k-1일 때 j-루프 수행 횟수 : k i = k일 때 j-루프 수행 횟수 : k + 1 i = k+1일 때 j-루프 수행 횟수 : k + 1 …………… i = n일 때 j-루프 수행 횟수 : k + 1
따라서 총 수행횟수는: 1 + 2 + 3 + … + k + (k+1) + … + (k+1) = k(k+1)/2 + (n-k+1)(k+1) = (2n-k+2)(k+1)/2 = O(nk)
그래프
그래프 용어
정점(vertex, node), 이음선(edge, arc)
방향 그래프(directed graph, or digraph)
가중치(weight), 가중치 포함 그래프 (weighted graph)
경로(path) - 두 정점사이에 edge가 있는 정점들의 나열
단순경로(simple path) - 같은 정점을 두 번 지나지 않음
순환(cycle) - 한 정점에서 다시 그 정점으로 돌아오는 경로
순환그래프(cyclic graph) vs 비순환 그래프 (acyclic graph)
길이(length): the sum of weights on the path (weighted graph)
the number of edges on the path (unweighted graph)
Shortest Path
Shortest Path: 한 도시에서 다른 도시로 직항로가 없는 경우
가장 빨리 갈 수 있는 항로를 찾는 문제
문제: 가중치 포함, 방향성 그래프에서 최단경로 찾기
Optimization problem (최적화 문제)의 정의
주어진 문제에 대하여 하나 이상의 많은 해답 후보가 존재할 때, 이와 연관된 값이 최소 또는 최대인 해답(optimal solution)을 찾아야 하는 문제
에너지 최소화 문제라고도 함.
shortest Path는 Optimization problem에 속함
Brute-force algorithm(무작정 알고리즘)
한 정점에서 다른 정점으로의 모든 경로의 길이를 구한 뒤, 그들 중에서 최소길이를 찾는다.
상향식으로 k=1부터 n까지 다음과 같이 이 과정을 반복하여 해를 구한다. D(0), D(1),……,D(n)
Floyd’s Algorithm I
가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산
1 2 3 4 5 6 7 8
voidfloyd(int n, const number W[][], number D[][]){ int i, j, k; D = W; for(k=1; k <= n; k++) for(i=1; i <= n; i++) for(j=1; j <= n; j++) D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]); }
Floyd’s Algorithm II
가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산, 각각의 최단경로를 구하라.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
voidfloyd2(int n, const number W[][], number D[][], index P[][]){ index i, j, k; for(i=1; i <= n; i++) for(j=1; j <= n; j++) P[i][j] = 0; D = W; for(k=1; k <= n; k++) for(i=1; i <= n; i++) for(j=1; j <= n; j++) if(D[i][k] + D[k][j] < D[i][j]) { P[i][j] = k; D[i][j] = D[i][k] + D[k][j]; } }
어떤문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적 해를 항상 포함하고 있으면 그 문제는 최적의 원칙(the principle of optimality)이 적용된다 라고 한다.
Optimal Binary Search Trees
definition
binary search tree
Ordered set
Each node contain one key
The keys in the left subtree are less than or equal to the key in that tree
Depth - number of edges from the root
balanced - if the depth of the 2 subtrees of every node never different by more than 1
optimal - the average time it takes to locate a key is minimized
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
voidoptsearchtree(int n, constfloat p[], float& minavg, index R[][]){ index i, j, k, diagonal; float A[1...n+1][0..n]; for(i=1; i<=n; i++) { A[i][i-1] = 0; A[i][i] = p[i]; R[i][i] = i; R[i][i-1] = 0; A[n+1][n] = 0; R[n+1][n] = 0; for(diagonal=1; diagonal <= n-1; diagonal++) for(i=1; i<=n-diagonal; i++) { j = i + diagonal; A[i][j] = minimum(A[i][k-1] + A[k+1][j]) + R[i][j] = a value of k that gave the minimum; } minavg = A[1][n]; } }
The Traveling Salesperson Problem
Problem Definition
Determine a shortest route that starts at the salesperson’s home city, visits each of the cities once, and ends up at the home city
Adjacent matrix W
V = set of all the vertices
A = a subset of V
D[vi][A] = length of a shortest path from vi to v1
passing through each vertex in A exactly once
Length of an optimal tour = minimum(W[1][j] + D[vj][V - {v1, vj}])
```C void travel(int n, const number W[][], index P[][], number& minlength) { index i, j, k; number D[1..n][subset of V-{v1}]; for(i=2; i<=n; i++) D[i][0] = W[i][1];
for(k=1; k<=n-2; k++) for(all subsets A V-{v1} containing k vertices) for(i such that i!= 1 and vi is not in A) { D[i][A] = min(j:vj A)(W[i][j]+D[j][A-{vj}]); P[i][A] = value of j that gave the minimum; } D[1][V-{v1}] = min(2<=j<=n)(W[1][j] + D[j][A-{v1,vj}]); P[1][V-{v1}] = value of j that gave the minimum; minlength = D[1][V-{v1}] }
분할: 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택
정복: 선택된 반쪽 배열에서 X를 찾는다
통합: 필요없음
재귀 알고리즘(recursive algorithm)에서 모든 재귀호출이 알고리즘의 마지막(꼬리) 부분에서 이루어 질 때 꼬리 재귀호출(tail recursion)이라고 함 - 그 알고리즘은 반복 알고리즘(iterative algorithm)으로 변환하기 수월ㅋ
최악의 경우 시간복잡도 분석
단위연산: x와 S[mid]의 비교
입력 크기: 배열의 크기 n(= high - low + 1)
알고리즘에서는 단위연산으로 설정한 조건문을 while루프 내에서 2번 수행하지만, 사실상 비교는 한번만 수행 (1) 어셈블리언어로는 하나의 조건 명령으로 충분히 구현 가능 (2) x를 찾기 전까지는 항상 2개의 조건문을 수행하므로 하나로 묶어서 한 단위로 취급해도 됨
경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 n/2이 되는 경우
시간복잡도를 나타내주는 재현식(recurrence)는 다음과 같다 W(n) = W(n/2)+1, n > 1이고, n = 2k(k>=1) W(1) = 1 이식의 해는 다음과 같이 구할 수 있다 W(1) = 1 W(2) = W(1) + 1 = 2 W(4) = w(2) + 1 = 3 W(8) = W(4) + 1 = 4 W(16) = W(8) + 1 = 5 … W(2k)=k+1 … W(n) = lg n + 1
증명: 수학접 귀납법:
귀납 출발점: n=1이면, W(1) = 1 = lg 1 + 1. 귀납 가정: 2의 거듭제곱(power)인 양의 정수 n에 대해서, W(n)=lg n + 1라고 가정 귀납 단계: W(2n) = lg(2n) + 1임을 보이면 된다. 재현식을 사용하면, W(2n) = W(n) + 1
= lg n + 1 + 1
= lg n + lg 2 + 1
= lg(2n) + 1
경우 2: 일반적인 경우 - 반쪽 배열의 크기는 [n/2]이 됨
합병정렬(Mergesort)
1 2 3 4 5 6 7 8 9 10 11 12
voidmergesort(int n, keytype S[]){ constint h = n / 2, m = n - h; keytype U[1..h], V[1..m];
if(n>1) { copy S[1] through S[h] to U[1] through U[h]; copy S[h+1] through S[n] to V[1] through V[m]; mergesort(h,U); mergesort(m,V); merge(h,m,U,V,S); } }
시간복잡도 분석
합병 알고리즘의 최악의 경우 시간복잡도 분석
단위연산: U[i]와 V[j]의 비교
입력크기: 2개의 입력 배열에 각각 들어있는 항목의 개수: h와 m
분석: i=h이고, j=m-1인 상태로 루프(loop)에서 빠져 나가는 때가 최악의 경우로서 (V에 있는 처음 m-1개의 항목이 S의 앞부분에 위치하고, U에 있는 h개의 모든 항목이 그 뒤에 위치하는 경우), 이때 단위연산의 실행 횟수는 h + m - 1이다. 따라서 최악의 경우 합병하는 시간복잡도는 W(h, m) = h + m - 1.
합병정렬 알고리즘의 최악의 경우 시간복잡도 분석
단위연산: 합병 알고리즘 merge에서 발생하는 비교
입력크기: 배열 S에 들어 있는 항목의 개수 n
분석: 최악의 경우 수행시간은 W(h,m) = W(h) + W(m) + h + m - 1이 된다. 여기서 W(h)는 U를 정렬하는데 걸리는 시간, W(m)은 V를 정렬하는데 걸리는 시간, 그리고 h + m - 1은 합병하는데 걸리는 시간이다. 정수 n을 2k(k>=1)이라고 가정하면, h= n/2, m=n/2가 된다. 따라서 최악의 경우 재현식은: W(n) = 2W(n/2)+n-1 n>1이고, n=2k(k>=1) W(1) = 0 왜냐하면 합병이 전혀 이루어지지 않으므로 이 재현식의 해는 아래의 도사정리의 2번을 적용하면 W(n) = O(n lg n)이 된다.
