평범한 컴퓨터공학도의 블로그 :)

CHAPTER 3 - Dynamic Programming

3.1 이항 계수 구하기(The Binomial Coefficient)

- 이항계수(Binomial coefficient)는 아래와 같이 정의된다.

$$\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!}foro\le k\le n$$

- 값이 큰 n에 대해 n!는 굉장히 큰 수가 되므로, 위의 식으로 이항계수를 구하는 것은 힘들 수 있다.
- 이에 재귀 관계식을 사용하면, n!이나 k!를 계산하지 않고도 이항 계수를 구할 수 있다.

$$\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\\ k\end{array}\right),0<k<n$$

$$\left(\begin{array}{c}n\\ k\end{array}\right)=1k=0또는k=n$$

- divide and conquer로 이항 계수를 구하는 코드는 아래와 같다.

int bin (int n, int k)
{
  if( k == 0 || n == k )
    return 1;
  else
    return bin(n-1, k-1)  + bin(n-1, k);
}

- 위의 코드를 실행할 때, 계산하는 항의 개수는 아래와 같다.

$$2\left(\begin{array}{c}n\\ k\end{array}\right)-1$$

- 위의 코드는 굉장히 비효율적인데, 그 이유는 재귀 호출할 때마다 같은 사례를 중복 계산하기 때문이다.
   (ex) bin(n-1, k-1), bin(n-1, k) 모두 bin(n-2, k-1)의 계산 결과가 필요하다.
- divide and conquer에서 input을 원래 크기와 별 차이 없는 크기로 분할하는 경우이기 때문에 비효율적이다.

- 이에, Dynamic Programming 기법을 사용하여 이항계수를 좀 더 효율적으로 구할 수 있다.
- 이 문제를 푸는 Dynamic Programming의 재귀 관계식은 아래와 같다.

$$B\left[i\right]\left[j\right]=\{\begin{array}{ll}B[i-1][j-1]+& B[i-1]\left[j\right]0<j<i\\ 1& j=0또는j=i\end{array}$$

- Dynamic Programming으로 이항 계수를 구하는 코드는 아래와 같다.

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 == i)
           B[i][j] = 1;
        else
           B[i][j] = B[i-1][j-1] + B[i-1][j];

     return B[n][k];
}

- i 값에 따라 for loop을 도는 횟수는 아래와 같다.

- 이에 총 실행 횟수와 Time Complexity는 아래와 같다. ( (k+1)이 n-k-1 번 더해진다.)

$$1+2+3+4+...+k+(k+1)+(k+1)+...+(k+1)$$

$$\frac{k(k+1)}{2}+(n-k+1)(k+1)=\frac{(2n-k+2)(k+1)}{2}\in \mathrm{\Theta }\left(nk\right)$$

3.2 프로이드의 최단경로 알고리즘(Floyd's Algorithm for Shortest Paths)

- 그래프(Graph)를 그림으로 표현하는 경우, 원은 마디(Vertex), 마디를 잇는 선은 이음선(Edge)이라고 한다.
- 이음선(Edge)에 방향이 있는 그래프는 방향 그래프(Directed Graph, digraph)라고 한다.
- 이음선(Edge)와 관련된 값을 가중치(weights)라고 하며, 가중치가 있는 그래프를 weighted graph라고 한다.

​- 방향 그래프(Directed Graph)에서 다음 마디(Vertex)로 가는 이음선(Edge)가 있는 마디(Vetex)의 Sequence를 Path라고 하며,
  어떤 마디에서 그 마디 자신으로 가는 경로는 Cycle이라고 한다.
- 그래프에 Cycle이 있으면 cyclic 하다고 하며, 없는 경우에는 acyclic 하다고 한다.
- 같은 마디(Vertex)를 두 번 이상 거치지 않는 경로를 simple path라고 한다.
- weighted graph에서 path의 length는 path 상에 있는 weight들의 합이며, weight가 없는 graph에서는 path 상에서의 이음선(edge)의 개수이다.

- 최단 경로(Shortest Path) 문제는 최적화 문제(Optimization problem)에 속한다.
- 최적화 문제에는 하나 이상의 해답 후보(Candidate solution)이 있을 수 있다.
- 해답 후보에는 그와 관련된 Value가 있고, 해당 문제의 해답은 해답 후보 값들 중 최적값(Optimal value)가 된다.

- vertex A에서 vertex B로 가는 이음선(Edge)가 있는 경우 A는 B에 인접하다(adjacent)
- 인접 행렬(adjacent matrix) W는 아래와 같은 규칙에 따라 작성할 수 있다.

$$W\left[i\right]\left[j\right]=\{\begin{array}{l}weightonedgeA에서B로가는이음선이있는경우\\ \mathrm{\infty }A에서B로가는이음선이없는경우\\ 0i=j인경우\end{array}$$

- 예시로 왼쪽 아래 그림의 Weighted Directed graph는 오른쪽의 adjacent matrix로 나타날 수 있다.
- 최단 경로 문제를 DP(Dynamic Programming)으로 풀기 위해서는 배열 D가 필요하다.
- 배열 D는 아래와 같이 작성된다.

$$D^{\left(k\right)}\left[i\right]\left[j\right]=set\{v_1,v_2,...,v_k\}에속하는vertex만을거쳐서v_i에서v_j로가는shortestpath$$

- 아래 그림은 weighted directed graph의 배열 W, D를 나타낸 예시이다.

- vertex i에서 vertex j로 가는 최단 경로는, i와 j 사이에 특정 vertex k를 최소한 하나의 vertext가 거치지 않는 경우와 모두 거치는 경우로 나눌 수 있다.

​ (case 1) vertex i와 j로 가는 최단 경로 중 최소한 하나는 특정 vertex k를 거치지 않는 경우
- vertex k를 거치지 않게 되므로, 아래의 수식이 성립하게 된다.

$$D^{\left(k\right)}\left[i\right]\left[j\right]=D^{(k-1)}\left[i\right]\left[j\right]$$

(case 2) vertex i와 j로 가는 최단 경로가 모두 특정 vertex k를 거치는 경우
- vertex k를 무조건 거치므로, shortest_path(i, j) = shortest_path(i, k) + shortest_path(k, j)이다.

- 이에 case2에서는 아래 수식을 만족하게 된다.
$$D^{\left(k\right)}\left[i\right]\left[j\right]=D^{(k-1)}\left[i\right]\left[k\right]+D^{(k-1)}\left[k\right]\left[j\right]$$

- 최종적으로 배열 D를 구하는 수식은 아래와 같다. (min의 첫 번째 항은 case 1, 두 번째 항은 case 2)
$$D^{\left(k\right)}\left[i\right]\left[j\right]=\underset{}{\overset{}{min}}(D^{(k-1)}\left[i\right]\left[j\right],D^{k-1}\left[i\right]\left[k\right]+D^{k-1}\left[k\right]\left[j\right])$$

- Floyd의 Shortest Path Algorithm code는 아래와 같다.

void floyd (int n, const number W[][], number D[][])
{
  index 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]);
}

- 위의 코드는 for-loop 3개가 n 번씩 돌게 되므로, 시간 복잡도 T(n)은 아래와 같이 계산된다.

$$T\left(n\right)=n\times n\times n=n^3\in \mathrm{\Theta }\left(n^3\right)$$

3.3 동적 계획과 최적화 (Dynamic Programming and Optimizaiton Problems)

- 최적화 문제를 동적계획법(Dynamic Programming)으로 풀기 위해서는 최적의 원칙이 성립해야 한다.
- 어떤 문제의 입력 사례(instance)가 그 입력 사례를 분할한 부분 사례(substances)에 대한 optimal solution을
  항상 포함하고 있으면, 해당 문제는 최적의 원칙(Principle of optimality)이 성립한다고 한다.
- 최적의 원칙이 성립하지 않는 예시로는, 최장 경로 문제(Longest path problem)이 있다.

3.4 연쇄 행렬 곱셈 (Chained Matrix Multiplication)

- (i * j) 행렬과 (j * k) 행렬을 곱하면 원소 단위 곱셈의 실행횟수는 (i * j * k) 번이 된다.
- 6개의 행렬을 곱하는 최적의 순서는 다음의 5개 경우 중 하나이다.

$$1.A_1\left(A_2{A}_3{A}_4{A}_5{A}_6\right)$$

$$2.\left(A_1{A}_2\right)\left(A_3{A}_4{A}_5{A}_6\right)$$

$$3.\left(A_1{A}_2{A}_3\right)\left(A_4{A}_5{A}_6\right)$$

$$4.\left(A_1{A}_2{A}_3{A}_4\right)\left(A_5{A}_6\right)$$

$$5.\left(A_1{A}_2{A}_3{A}_4{A}_5\right)A_6$$

- 행렬 M을 아래와 같이 정의할 때,

$$M\left[i\right]\left[j\right]=i<j일때,A_i부터A_j까지행렬을곱하는데필요한원소단위곱셈의최소횟수$$

$$M\left[i\right]\left[i\right]=0$$

재귀 관계식은 아래와 같이 나타난다.

$$M\left[i\right]\left[j\right]=\underset{i\le k\le j-1}{\overset{}{min}}(M\left[i\right]\left[k\right]+M[k+1]\left[j\right]+d_{i-1}{d}_k{d}_j),ifi<j$$

$$M\left[i\right]\left[i\right]=0$$

- 위의 관계식을 기반으로 하여 divide and conquer 기법을 사용하면 지수 시간 알고리즘에 해당한다.
- 이에 아래 그림과 같이 dynamic programming을 사용하여 좀 더 효율적으로 알고리즘을 작성할 수 있다.

- 최소 곱셈의 코드는 아래와 같다.

int minmult (int n, const int d[], index P[][])
{
  index i, j, k, diagonal;
  int M[1..n][1..n];

  for(i = 1; i <= n; i++)
    M[i][i] = 0;
  
  for(diagonal = 1; diagonal <= n-1; diagonal++){
    for(i = 1; i <= n-diagonal; i++){
      j = i + diagonal;

      for(k = i; k <= j-1; k++){
        M[i][j] = minimum(M[i][k] + M[k+1][j] + d[i-1] * d[k] * d[j]);
        P[i][j] = a value of k that gave the minimum;
      }
    }
  }
  return M[1][n];
}

- 최소 곱셈의 시간 복잡도는 아래와 같다.
- (j = i + diagonal)이므로, k-loop 안에서 실행되는 횟수는 아래와 같다.

$$(j-1)-i+1=(i+diagonal-1)-i+1=diagonal$$

- 주어진 diagonal 값에 대해서 i-loop에서 실행하는 횟수는 n-diagonal이 되고, diagonal 값은 1~(n-1)이므로

$$\sum _{diaognal=1}^{n-1}[(n-diagonal)\times diagonal]\frac{n(n-1)(n+1)}{6}\in \mathrm{\Theta }\left(n^3\right)$$

3.5 최적 이분 검색 트리(Optimal Binary Search Trees)

- 이분 검색 트리(Binary Search Tree)의 원소들을 최적으로 정리하는 알고리즘을 만들어보자.
- 이진 트리(Binary)에서 어떤 마디(node)의 왼쪽[오른쪽] 자식 마디(child)를 root로 하는 하위 트리를
그 마디의 왼쪽 하위 트리(Left Subtree)[오른쪽 하위 트리(Right Subtree)]라고 한다.

​

* 정의

- 이분 검색 트리(Binary Search Tree)는 Ordered set으로 속한 원소로 구성된 이진 트리(Binary Tree)이다.
- 이분 검색 트리는 아래와 같은 조건을 만족한다.
   (1) 각 마디(node)는 하나의 원소(element)만을 가지고 있다.
   (2) 마디의 왼쪽 하위 트리에 있는 원소들은 모두 그 마디의 원소보다 작거나 같다.
   (3) 마디의 오른쪽 하위 트리에 있는 원소들은 모두 그 마디의 원소보다 크거나 같다.

- 마디의 깊이(Depth of node)는 root에서 해당 node로 가는 unique path에서 edge의 개수이다.
- 트리의 깊이(Depth of tree)는 해당 트리의 모든 마디의 깊이 중 최댓값을 나타낸다.
- 깊이(Depth)는 때때로 수준(Level)이라고도 불린다.
- 모든 마디의 두 하위 트리의 깊이가 1 이상 차이 나지 않는 트리를 balanced Tree라고 한다.

- 위 그림의 왼쪽 Tree는 Balanced Tree가 아니며, 오른쪽 Tree는 Balanced Tree이다.
- Binary Search Tree에서 search key를 찾는 데 걸리는 평균 시간이 최소가 되도록 정리하는 것이 중요하며,
   그렇게 정리한 Tree를 최적(Optimal)이라고 한다.

- 만약 각 원소가 search key 일 확률이 모두 같다고 하면, 오른쪽 Tree는 Optimal이다.

- Binary Search Tree에서 원소를 검색하는 코드는 아래와 같다.

struct nodetype
{
  keytype key;
  nodetype* left;
  nodetype* right;
}

typedef nodetype* node_pointer;

void search (node_pointer tree, keytype keyin, node_pointer& p) // keyin : search key
{
  bool found;

  p = tree;
  found = false;

  while(!found){
    if(p->key == keyin)
      found = true;
    else if(keyin < p->key)
      p = p->left;
    else if(keyin > p->key)
      p = p->right;
  }
}

- 최적 트리는 해당 트리의 left sub-tree의 최적 트리와 right sub-tree의 최적 트리를 포함한다.

- 트리 k에 대한 평균 검색 시간은 아래와 같다.

$$A\left[1\right][k-1]+(p_1+...+p_{k-1})+p_k+A[k+1]\left[n\right]+(p_{k+1}+...+p_n)$$

A[1][k-1] : left sub-tree에서의 평균 시간
p(1) + ... + p(k-1), p(k+1) ... + p(n) : 뿌리에서 비교하는데 드는 추가시간
p(k) : 뿌리를 검색하는 평균 시간
A[k+1][n] : right sub-tree에서의 평균 시간

- 위의 식을 정리하면 아래와 같다.

$$A\left[1\right][k-1]+A[k+1]\left[n\right]+\sum _{m=1}^n{p}_m$$

$$A\left[1\right]\left[n\right]=\underset{1\le k\le n}{\overset{}{min}}(A\left[1\right][k-1]+A[k+1]\left[n\right])+\sum _{m=1}^n{p}_m$$

- 따라서 일반식으로 정리하면 아래와 같다.

$$A\left[i\right]\left[j\right]=\underset{i\le k\le j}{\overset{}{min}}(A\left[i\right][k-1]+A[k+1]\left[j\right])+\sum _{m=i}^j{p}_m,i<j$$

$$A\left[i\right]\left[i\right]=p_i$$

$$A\left[i\right][i-1]=0$$

$$A[j+1]\left[j\right]=0$$

- 최적 이분 검색 트리 (Optimal Binary Serach Tree)에 대한 코드는 아래와 같다.

void optsearchtree(int n, const float 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;
      
       for(k=i; k<=j; k++){
         if(A[i][j] > A[i][k-1] + A[k+1][j]){
            A[i][j] = A[i][k-1] + A[k+1][j];
            R[i][j] = k;
       }

       for(m=i; m<=j; m++)
         A[i][j] += p[m];
     }
  }
  minavg = A[1][n];
}

- 최적 이분 검색 트리 (Optimal Binary Serach Tree)에 대한 시간 복잡도는 아래와 같다.

$$T\left(n\right)=\frac{n(n-1)(n+4)}{6}\in \mathrm{\Theta }\left(n^3\right)$$

- 최적 이분 검색 트리(Optimal Binary Search Tree)를 구축하는 코드는 아래와 같다.

node_pointer tree (index i, j)
{
  index k;
  node_pointer p;

  k = R[i][j];
  if(k == 0)
     return NULL;
  else {
     p = new_nodetype;

     p->key = Key[k];
     p->left = tree(i, k-1);
     p->right = tree(k+1, j);

     return p;
  }
}

3.6 외판원 문제(The Traveling Salesperson Problem)

- 외판원이 20개 도시로 판매 출장을 계획하고 있으며, 각 도시는 몇 개의 도시와 도로로 연결되어 있다.
- 외판원이 자신이 거주하고 있는 도시에서 출발하여 각 도시를 한 번씩 방문한 뒤, 다시 출발한 도시로 돌아오는
  여행길을 찾는 문제를 외판원 문제(The Traveling Salesperson problem)이라고 한다.

- 이 문제는 도시를 마디(vertex, node)로 하여 weighted directed graph로 표현하여 문제를 해결할 수 있다.

- 일주여행길(tour)는 해밀턴 회로(Hamiltonian circuits)라고도 하며, optimal tour는 최소 거리 tour이다.

- n 개의 도시가 있고 각 도시에서 다른 도시로의 edge가 모두 존재할 때, tour의 총 가지 수는 아래와 같다.

$$(n-1)(n-2)...1=(n-1)!$$

- 그래프가 왼쪽 아래와 같이 있을 때, 인접 행렬(adjacent matrix) W는 오른쪽 아래와 같이 나타난다.

- 이 문제에서 사용할 변수는 아래와 같다.
   V = 모든 도시의 집합 , A = V의 부분집합
   D[v(i)][A] = A에 속한 도시를 각각 한 번씩만 거쳐서 v(i)에서 v(1)로 가는 최단 경로의 길이

   이때, optimal tour의 길이는 아래와 같다.

$$\underset{2\le j\le n}{\overset{}{min}}(W\left[1\right]\left[j\right]+D\left[v_j\right][V-\{v_1,v_j\}])$$

- 이를 구현한 코드는 아래와 같다.

void travel(int n, const number W[][], index P[][], number& minlength)
{
   index i, j, k;
   number D[1..n][subnet of V-{v(1)}];

   for(i=2; i<=n; i++)
     D[i][empty] = W[i][1];

   for(k=1; k<=n-2; k++){
     for(all subnet A containing k vertices){
        for(i such that i!= 1 and v(i) is not in A){
          D[i][A] = min(W[i][j] + D[i][A - {v(j)}]);
          P[i][A] = value of j that gave the minimum;
        }
     }
   }

   D[1][V - {v(1)}] = min(W[1][j] + D[j][V-{v(1), v(j)}]);
   P[1][V - {v(1)}] = value of j taht gave the minimum;
   min length = D[1][V - {v(1)});
}

- 외판원 문제의 시간 복잡도와 공간 복잡도는 아래와 같다.

$$T\left(n\right)=\sum _{k=1}^{n-2}(n-1-k)k\left(\begin{array}{c}n-1\\ k\end{array}\right)=(n-1)(n-2)2^{n-3}\in \mathrm{\Theta }\left(n^2{2}^n\right)$$

$$M\left(n\right)=2\times n{2}^{n-1}=n{2}^n\in \mathrm{\Theta }\left(n{2}^n\right)$$

- 최악 시간 복잡도(Worst-case Time Complexity)가 지수 시간보다 좋은 외판원 문제를 푸는 알고리즘은 없다.
- 하지만, 지수 시간보다 좋은 알고리즘이 없다고 증명한 사람도 존재하지 않는다.

3.7 DNA 서열 정렬(Sequence Alignment)

- DNA는 A, G, C, T 4개의 염기로 구성되어 있으며, (A, T)와 (G, C)가 쌍을 이룬다.
- 동족서열이 아래와 같을 때,

A A C A G T T A C C

T A A G G T C A

​

틈(gap)의 cost를 1, 불일치(mismatch)의 cost를 3으로 두면,

_ A A C A G T T A C C

T A A _ G G T _ _ C A

인 경우에는 정렬에 드는 cost가 10(1 + 1 + 3 + 1 + 1 + 3)이다.

​

A A C A G T T A C C

T A _ A G G T _ C A

인 경우에는 정렬에 드는 cost가 11(3 + 1 + 3 + 1 + 3)이다.

- 최적 정렬(Optimal alignment)를 구하기 위한 계산은 아래 3가지 경우 중 하나로 시작해야 한다.
(1) x[0]과 y[0]을 맞추어 정렬한다. x[0] = y[0]이면, 첫 alignment site에서는 peantly가 없고,
       x[0] != y[0]이면 penalty가 1이다.

(2) x[0]과 gap을 맞추어 정렬하고, 첫 alignment site에서 peanlty가 2이다.

(3) y[0]과 gap을 맞추어 정렬하고, 첫 alignment site에서 penalty가 2이다.

- DNA 서열 정렬을 위해 divide and conquer 방법을 사용하면 코드는 아래와 같다.

void opt (int i, int j)
{
  if( i == m )
    opt = 2(n - j);
  else if( j == n )
    opt = 2(m - i);
  else {
    if(x[i] == y[j])
      penalty = 0;
    else
      penalty = 1;

    opt = min(opt(i + 1, j + 1) + penalty, opt(i + 1, j) + 2, opt(i , j + 1) + 2);
  }
}

- 위의 divide and conquer 방법을 사용하면 중복 계산되는 항들이 많아지게 되어 비효율적이게 된다.
- 이에 배열을 사용하여 아래와 같이 구해볼 수 있다.
- Diagonal1, Diagonal2, ... 로 계산을 수행해가며, 최종 답인 cost 값은 [0][0]에 저장되게 된다.

- 위 배열에서 어떻게 [0][0] 값을 계산했는지 경로를 추적할 수 있다.

  ​(1) [0][0]을 선택한다.  
  (2) 경로에 넣을 둘째 항목을 찾는다.
        (a) [0][1]을 검사한다. (b) [1][0]을 검사한다. (c) [1][1]을 검사한다.

- 경로를 찾으면, 정렬된 서열(alignmented sequence)를 다음과 같이 추출할 수 있다.

(1) 배열의 오른쪽 맨 아래부터 시작하여 표시해둔 경로를 따라간다.
(2) 배열의 [i][j] 칸에 도달하기 위해서 대각선으로 이동할 때마다, i 번째 항에 해당하는 문자를 x에 넣고, j 번째 열에 해당하는 문자를 y 서열에 넣는다.
(3) 배열의 [i][j] 칸에 도달하기 위해서 위로 이동할 때마다, i 번째 항에 해당하는 문자를 x 서열에 넣고, 틈 문자(gap)을 y 서열에 넣는다.
(4) 배열의 [i][j] 칸에 도달하기 위해서 왼쪽으로 이동할 때마다, j 번째 행에 해당하는 문자를 y 서열에 넣고, 틈 문자(gap)을 x 서열에 넣는다.

-Reference-
Neapolitan, Richard E., 『Foundation of algorithms FIFTH EDITION』

CHAPTER 2 - 분할정복(Divide and Conquer)

- 문제의 입력를 두 개 이상의 작은 입력으로 나누고, 답을 얻기 위해 시도한다.
- 답을 얻지 못했다면, 또 각각의 입력 사례에 대해 분할을 한 뒤, 다시 시도한다.
- Divide and Conquer는 하향식(Top-Down) 방식의 접근법이다.

2.1 이분검색 (Binary Search)

- 이분 검색 알고리즘은 오름차순으로 정렬된 배열에서 실행가능하며, 수행 절차는 아래와 같다.

1. [Divide] 배열을 정 가운데 원소를 기준으로 반으로 분할한다. 찾고자 하는 수 x가 가운데 원소보다
   작으면 왼쪽 배열을 선택한다. x가 가운데 원소보다 크면 오른쪽 배열을 선택한다.
2. [Conquer] 선택한 반쪽 배열을 정복한다. 즉, 선택한 반쪽 배열에 x가 있는지 재귀적으로 이분검색한다.
3. [Obtain] 선택한 반쪽 배열에서 얻은 답이 최종 답이다.

index location (index low, index high)
{
  index mid;

  if(low > high)
   return 0;
  else {
   mid = (low + high) / 2;

   if(x == S[mid])
     return mid;
   else if(x < S[mid])
     return location(low, mid - 1);
   else
     return location(mid + 1, high);
  }
}

- 이분 검색의 최악 시간 복잡도(Worst-Case Time Complexity)는,

$$W\left(n\right)=W\left(\frac{n}{2}\right)+1W\left(n\right)=\lg n+1\in \mathrm{\Theta }(\lg n)$$

2.2 Merge Sort

- 합병 정렬(Merge Sort)의 절차는 아래와 같다.

1. [Divide] 배열을 반으로 분할한다. (분할한 배열의 원소는 각각 n/2개 이다.)
2. [Conquer] 분할한 배열을 각각 따로 정렬한다.
3. [Obtain] 정렬한 두 배열을 합병하여 정렬한다.

void mergesort(int n, keytype S[])
{
  if(n > 1) {
    const int h = [n/2], m = n-h;
    keytype U[1..h], V[1..m];

    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);
  }
}

void merge(int h, int m, const keytype U[], const keytype V[], keytype S[])
{
  index i, j, k;
  
  i = 1; j = 1; k = 1;
  while( i <= h && j <= m) {
    if(U[i] < V[j]) {
      S[k] = U[i];
      i++;
    }
    else {
      S[k] = V[j];
      j++;
    }
    k++;
  }

  if(i > h)
    copy V[j] through V[m] to S[k] through S[h+m];
  else
    copy U[i] through U[h] to S[k] through S[h+m];
}

​

- Merge의 Worst-case Time Complexity W(h,m)은 아래와 같다.
  (두 배열 U,V의 원소 개수는 h, m이다.)

$$W(h,m)=h+m-1$$

- Mergesort의 Worst-case Time Complexity W(n)은 아래와 같다.

$$W\left(n\right)=W\left(h\right)+W\left(m\right)+(h+m-1)$$

(1) W(h) : U를 정렬하는데 걸리는 시간
(2) W(m) : V를 정렬하는데 걸리는 시간
(3) (h+m-1) : 합병하는데 걸리는 시간

- 위의 식은 아래와 같이 표현될 수 있다.

$$W\left(n\right)=2W\left(\frac{n}{2}\right)+1,W\left(1\right)=0$$

$$W\left(n\right)\in \mathrm{\Theta }(n\lg n)$$

- MergeSort는 추가적으로 U와 V라는 배열을 만들어서 사용해야 하기 때문에, 추가적인 메모리가 필요하다.
(추가적으로 만들어지는 배열 원소의 총 개수는 대략 n(1+1/2+1/4+...) = 2n개 정도이다.)

​- 이에 n개의 원소를 가진 배열 하나만을 사용하여 메모리 공간을 효율적으로 사용하는 MergeSort가 존재한다.

void mergesort2 (index low, index high)
{
  index mid;

  if(low < high){
    mid = (low + high) / 2;
    mergesort2(low, mid);
    mergesort2(mid + 1, high);
    merge2(low, mid, high);
  }
}

void merge2(index low, index mid, index high)
{
  index i, j, k;
  keytype U[low .. high] // Merge에 필요한 local array
  i = low; j = mid + 1; k = low;

  while(i <= mid && j <= high) {
    if(S[i] < S[j]) {
       U[k] = S[i];
       i++;
    }
    else {
       U[k] = S[j];
       j++;
    }
       k++;
  }
  if(i > mid)
    move S[j] through S[high] to U[k] through U[high];
  else
    move S[i] through S[mid] to U[k] through U[high];
  move U[low] through U[high] to S[low] through S[high];
}

2.3 Quicksort(Partition Exchange Sort)

- Quicksort는 배열을 둘로 분할하고, 분할한 배열에 대해 각각 재귀 호출을 통해 정렬한다는 점이 Mergesort와 유사하다.

- 그러나, 빠른 정렬은 pivot을 설정하여 이 수보다 작은 원소는 왼쪽 배열로, 큰 원소는 오른쪽 배열로 가도록 하는 점에서 Mergesort와 다르다. 이에 pivot을 잘 설정하는 것이 중요하다.

void quicksort(index low, index high)
{
  index pivotpoint;
  
  if(high > low) {
    partition(low, high, pivotpoint);
    quicksort(low, pivotpoint - 1);
    quicksort(pivotpoint + 1, high);
  }
}

void partition(index low, index high, index& pivotpoint)
{
  index i, j;
  keytype pivotitem;

  pivotitem = S[low]; // pivotitem으로 첫번째 원소를 선택함.
  j = low;

  for(i = low + 1; i <= high; i++){
    if(S[i] < pivotitem){
      j++;
      exchange S[i] and S[j];
    }
  }
  pivotpoint = j;
  exchange S[low] and S[pivotpoint]; // pivotitem 값을 pivotpoint에 저장함.
}

- Partition은 첫째 원소를 제외한 모든 원소를 비교하므로, 시간복잡도는 아래와 같다.

$$T\left(n\right)=n-1$$

- 위의 Quicksort는 완전히 정렬된 배열을 정렬하는 경우가 Worst-case이다. (pivot이 항상 S[low])

$$T\left(n\right)=T\left(0\right)+T(n-1)+n-1,n>0T\left(0\right)=0$$

T(0) : 왼쪽 배열을 정리하는데 걸리는 시간
T(n-1) : 오른쪽 배열을 정리하는데 걸리는 시간
n-1 : 분할(Partition) 하는데 걸리는 시간

$$T\left(n\right)=\frac{n(n-1)}{2}W\left(n\right)=\frac{n(n-1)}{2}\in \mathrm{\Theta }\left(n^2\right)$$

- 위의 Quicksort의 Average Time Complexity는,

$$A\left(n\right)=\sum _{p=1}^n\frac{1}{n}[A(p-1)+A(n-p)]+n-1$$

A(p-1) + A(n-p) : pivotpoint가 p일 때 부분 배열들을 정렬하는데 걸리는 평균시간
n-1 : 분할하는데 걸리는 시간

$$A\left(n\right)\approx (n+1)2\ln n=(n+1)2(\ln 2)(\lg n)$$

$$\approx 1.38(n+1)\lg n\in \mathrm{\Theta }(n\lg n)$$

2.4 Strassen's Matrix Multiplication Algorithm

- 기본적인 행렬곱셈 알고리즘의 시간복잡도는,

$$T\left(n\right)=n^3-n^2$$

이므로, 실용적으로 사용하기 힘들다. 이에 Strassen은 곱셈을 기준으로 하든, 덧셈/뺄셈을 기준으로 하든지에
상관없이 시간복잡도가 3차보다 좋은 알고리즘을 발표하였다.

void strassen(int n, nxn_matrix A, nxn_matrix B, nxn_matrix& C)
{
  if(n <= threshold)
    compute C = A X B using the standard Algorithm.
  else {
     partition A into four matrices A11, A12, A21, A22;
     partition B into four matrices B11, B12, B21, B22;
     compute C = A X B using Strassen's method;
     // example recursive call;
     // strassen(n/2, A11 + A22, B11 + B22, M1);
  }
}

- Strassen에서의 곱셈의 수의 시간복잡도는 아래와 같다.

$$T\left(n\right)=7T\left(\frac{n}{2}\right)n>1이며,n은2의거듭제곱$$

$$T\left(1\right)=1$$

$$T\left(n\right)=n^{\lg 7}\approx n^{2.81}\in \mathrm{\Theta }\left(n^{2.81}\right)$$

- Strassen에서의 덧셈/뺼셈의 수의 시간복잡도는 아래와 같다.

$$T\left(n\right)=7T\left(\frac{n}{2}\right)+18{\left(\frac{n}{2}\right)}^{2}n>1이며,n은2의거듭제곱$$

$$T\left(1\right)=0$$

$$T\left(n\right)=6n^{\lg 7}-6n^2\approx 6n^{2.81}-6n^2\in \mathrm{\Theta }\left(n^{2.81}\right)$$

2.5 분할정복법을 사용할 수 없는 경우

아래와 같은 두 경우에는 분할정복법을 피해야 한다.
1. 크기 n인 instance(사례)가 거의 n에 가까운 크기의 두 개 이상의 사례로 분할된다.
2. 크기 n인 instance(사례)가 n/c 크기의 거의 n개 사례로 분할된다.

​첫번째 사례의 경우는 exponential-time(지수시간) 알고리즘이 나오고,
두번째 사례의 경우는 n^(theta(lgn))의 알고리즘이 나오게 된다.

-Reference-
Neapolitan, Richard E., 『Foundation of algorithms FIFTH EDITION』

CHAPTER 1 - Algorithms : Efficiency, Analysis, and Order

1.1 알고리즘 (Algorithm)

- 리스트(list)란 어떤 원소를 특정 순서로 나열해 놓은 것이다.
(ex) S = [10, 7, 11, 5, 13 ,8]

- 순차검색 ( Time Complexitiy : O(n))
: 반복문을 통해 배열의 start index부터 end index까지 한번씩 검색하는 알고리즘.

void seqsearch(int n, const keytype S[]. keytype x, index& location)
{
  location = 1;
  while(location <= n && S[location] != x)
    location++;

  if(location > n)
    location = 0;
}

- 교환 정렬(Exchange Sort)
: 반복문을 통해 배열의 start index부터 end index까지 한번씩 검색하는 알고리즘.

void exchange(int n, keytype S[])
{
  index i, j;
  for (i = 1; i <= n-1; i++)
    for(j = i+1; j <= n; j++)
        if(S[j] < S[i])
          exchange S[i] and S[j];
}

1.2 효율적인 알고리즘 개발의 중요성

* 순차검색 대 이분검색

- 순차 검색(Sequential Search)보다 이분 검색(Binary Search)를 통해 효율적으로 Search 할 수 있다.

- 이분 검색(Binary Search) : 배열이 정렬되어 있다는 가정이 필요.
1. 찾고 싶은 수를 x라고 할 때, 배열의 정중앙에 위치한 원소 y와 비교한다.
2. 만약 x를 찾았다면, 검색을 종료한다.
3. 만약 x를 찾지 못했을 때 x가 y보다 크면 배열의 앞부분을, x가 y보다 작다면 배열의 뒷부분을 이분 검색한다.

void binsearch (int n, const keytype S[], keytype x, index& location)
{
  index low, high, mid;
  
  low = 1; high = n;
  location = 0;

  while(low <= high && location == 0) {
    mid = (low + high) / 2;

    if(x == S[mid])
     location = mid;
    else if(x < S[mid])
     high = mid - 1;
    else
     low = mid + 1;
  }
}

- 크기가 n인 배열에 대해 순차 검색에 의한 비교 횟수는 n 이고, 이분 검색에 의한 비교 횟수는 log(n) + 1 이다.

* 피보나치 수열

▶ 재귀함수를 사용하는 방법 (Divide and Conquer 기법)
- 피보나치 수열의 n번째 수는 재귀(Recursively)로 정의한다.

$$f_0=0$$

$$f_1=1$$

$$f_n=f_{n-1}+f_{n-2}(ifn\ge 2)$$

int fib (int n)
{
  if (n <= 1)
   return n;
  else
   return fib(n-1) + fib(n-2);
}

- T(n)을 n에 대한 Recursion Tree의 항의 개수라고 할 때,

$$\begin{gathered} T(n)>2\times T(n-2) \\ >2\times 2\times T(n-4) \\ >2\times 2\times 2\times T(n-6) \\ >2\times 2\times 2\times ...\times T(0) \end{gathered}$$

- 따라서, 재귀함수를 사용하여 피보나치 함수를 구현하면 구하는 항의 갯수 T(n)은 아래 관계를 만족한다.

$$T(n)>2^{\frac{2}{n}}$$

▶ 배열과 반복문을 사용하는 방법 (Dynamic Programming 기법)

- 이에 재귀함수를 사용하는 대신, 배열과 반복문을 사용하여 좀 더 효율적이게 피보나치 수를 구하는 알고리즘을 작성할 수 있다.

int fib2 (int n)
{
  index i;
  int f[0..n];

  f[0] = 0;
  if ( n > 0) {
    f[1] = 1;
    for ( i = 2; i <= n; i++)
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

- 이 방법은 n번째 피보나치 항을 구하기 위해서 (n+1) 개의 항을 계산한다.

1.3 알고리즘의 분석 (Analysis of Algorithms)

* 시간복잡도 분석(Complexity Analysis)

- 일반적으로 알고리즘의 실행시간은 입력의 크기가 커지면 증가하고, 총 실행시간은 ​단위 연산이 몇 번 수행되는가에 비례한다.
- 알고리즘의 시간복잡도 분석(Time Complexity Analysis)는 입력크기를 기준으로 단위 연산을 몇번 수행하는지 구하는 것이다.
- 교환정렬(Exchange Sort)의 시간복잡도는,

$$T(n)=(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}$$

- 크기가 n이어도, 단위 연산을 수행하는 횟수가 달라질 수 있다. (ex) 순차검색
- 이에 시간복잡도를 측정할 때, 알고리즘이 실행할 단위연산의 최대 횟수를 사용하여  최악 시간복잡도(Worst-case Time Complexity)를 구하여 사용할 수 있다.
- 순차 검색(Sequential Search)의 Worst-case time Complexity W(n) = n이다.

- 알고리즘이 평균적으로 얼마나 실행하는지를 알면, 더 효율적인 경우도 존재한다.
- 이 경우에는, 평균 시간복잡도(Average-case Time Complexity)를 구하여 알고리즘을 분석하는 경우가 더 합리적일 수 있다.
- 평균 시간복잡도를 구하기 위해서는 n개의 입력에 확률을 각각 부여해야 한다.
- 순차검색(Sequential Search)에서 찾고자 하는 수 x가 배열 S에 있는 경우는,
  (x가 k번째 위치에 있을 확률 : 1/n)

$$A\left(n\right)=\sum _{k=1}^n(k\times \frac{1}{n})=\frac{1}{n}\times \sum _{k=1}^{n}k=\frac{1}{n}\times \frac{n(n+1)}{2}=\frac{n+1}{2}$$

- 순차검색(Sequential Search)에서 찾고자 하는 수 x가 배열 S에 없는 경우에는,
  (x가 k번째에 위치할 확률 p/n, x가 배열에 없을 확률 1-p)

$$A\left(n\right)=\sum _{k=1}^n(k\times \frac{p}{n})+n(1-p)=n(1-\frac{p}{2})+\frac{p}{2}$$

- 알고리즘이 실행할 단위연산의 최소 횟수를 통해 최선 시간복잡도(Best case Time Complexity)를 구할 수 있다
- 순차 검색(Sequential Search)의 Best-Case Time Complexity B(n) = 1이다.

1.4 차수 (Order)

- 시간복잡도(Time Complexity)가 n, 100n과 같은 경우 linear-time Algorithm 이라고 한다.
- 시간복잡도(Time Complexity)가 (n^2), (0.01n^2)과 같은 경우 quadratic-time Algorithm이라고 한다.

* 차수의 직관적인 소개(An Intutive Introduction to Order)

$$\theta (\lg n)<\theta \left(n\right)<\theta (n\lg n)<\theta \left(n^2\right)<\theta \left(n^3\right)<2^n$$

* 차수의 정식 소개 (Rigorous Introduction to Order)

1. Big-O

- 주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는
  양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

$$g\left(n\right)\le c\times f\left(n\right)$$

 - Big O는 함수의 asymptotic upper bound(점근적인 상한)을 정한다.

2. Omega

- 주어진 복잡도 함수 f(n)에 대해서 Omega(f(n))은 N이상의 모든 n에 대해서 다음 부등식을 만족하는
양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

$$g\left(n\right)\ge c\times f\left(n\right)$$

 - (Big-O)와 Omega와 Theta

-Reference-
Neapolitan, Richard E., 『Foundation of algorithms FIFTH EDITION』