1. Algorithm: efficiency, analysis and order

1-1. 순차검색 알고리즘

• pseudo code

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

• 시간 복잡도
  • 최악의 경우 n : 찾는 데이터가 없거나 맨 뒤에 있을 때
    • $O(n)$
  • 평균의 경우 (x가 배열안에 있을 때만 고려)
    • 단위연산은 S[location] != x 비교
    • x가 배열의 k번째 있을 확률 $\frac{1}{n}$
    • x가 배열의 k번째 있다면.. k번 수행해야함
    • $A(n) = \sum_{k=1}^{n}(k\times \frac{1}{n})=\frac{1}{n}\times \frac{n(n+1)}{2} = \frac{n+1}{2}$
  • 평균의 경우 (x가 배열안에 없을 때도 고려)
    • x가 배열 안에 있을 확률이 p
    • x가 배열의 k번째 있을 확률 $\frac{p}{n}$
    • x가 배열에 없을 확률 $1-p$
    • $A(n) = \sum_{k=1}^n(k\times\frac{p}{n})+n(1-p)=n(1-\frac{p}{2})+\frac{p}{2}$
  • 최고의 경우
    • $B(n)=1$

1-2. 배열의 수 더하기

• pseudo code

number sum(int n, const number S[])
{
	index i;
    number result;
    result = 0;
    for(i=1; i<=n; i++)
    {
    	result = result + S[i];
    }
    return result;
}

• 시간 복잡도
  • 덧셈이 단위연산: $T(n)=n$
  • 지정문이 단위연산: $T(n) = n+n+1$
  • 결론적으로는 $O(n)$

1-3. 교환정렬

• pseudo code

void exchangesort(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];
            }
        }
    }
}

• 시간 복잡도
  • 단위연산: S[j]와 S[i]의 비교
    • $T(n) = (n-1) + (n-2)+(n-3)+..+1 = \frac{n(n-1)}{2}$
  • 단위연산: exchange 연산
    • 최악의 경우 (거꾸로 배열이 정렬된 경우)
    • $W(n) = \frac{(n-1)n}{2}$
  • 결론적으로 $O(n^2)$

1-4. 행렬곱셈

• pseudo code

void matrixmult(int n, const number A[][], const number B[][], number C[][])
{
	index i,j,k;
    
    for(i=1; i<=n; i++)
    {
    	for(j=1; j<=n; j++)
        {
        	C[i][j] = 0;
        	for(k=1; k<=n; k++)
            {
            	C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
    	}
    }
}

• 시간 복잡도
  • $T(n) = n*n*n=n^3$
  • $O(n^3)$

1-5. 이분검색 알고리즘 (재귀 x)

• pseudo code (재귀 x)

void binsearch(int n, const keytype S[], keytype x, index& location)
{
	index low, mid, high;
    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;
    }
}

• 시간 복잡도
  • 최악의 경우에도 한번의 검색 시 절반씩 줄기 때문에
  • $lg\ n$ + 1

1-6. 피보나치 수열

• pseudo code (재귀)

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

• 시간 복잡도
  • recurrence relation (재귀) : $T(n) = T(n-1) + T(n-2) + 1$
    -> $2^{n/2}$
• pseudo code (재귀x)

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

• 시간 복잡도
  • recurrence relation (재귀x) : $T(n) = n+1$
    -> $O(n)$

1-7. 차수

1-8. 알고리즘 복잡도와 컴퓨터 능력

• ex1)
  • 알고리즘 복잡도가 cn일때 t시간동안 m개의 문제 해결
  • 처리속도가 2배가 된다면?
    • $c(m+x) = 2cm\ -> x = m\ -> m+m = 2m$
• ex2)
  • $cn^2$ 일때
  • 처리속도 4배가 된다면?
    • $c(m+x)^2 = 4cm^2\ -> x = m\ -> m+m = 2m$
• ex3)
  • $c2^n$ 일때
  • 처리속도 2배
    • $c2^{m+x} = 2c2^m\ -> c2^{m+x}= c2^{m+1}\ -> x = 1\ -> m+1$
• ex4: 15-1 기출)
  • $c2^n$ 일때 n=10 해결
  • 처리속도 10배
    • $c2^{n+x}=10c2^n\ -> c2^{n+x} = c2^{n+log_210}$
    • $log_210 =3.$xx -> 13 개
• ex5)
  • $O(n!)$ T시간 n=10 해결
  • 처리속도 1000배
    • $c(m+x)! = 1000*c(m)!$ -> $c(m+x)!=c(m+6.??)!$
    • 10+6 = 16개

2. Algorithm: divide and conquer

2-1. 이분검색 (재귀 o)

• pseudo code

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

• 시간 복잡도
  • 최악의 경우(검색하는 반쪽 배열의 크기가 n/2인 경우)
  • $W(n) = W(\frac{n}{2})+1$, $n>1,\ n=2^k, W(1)=1$
  • $W(n) = lg\ n+1$

2-2-1. 합병정렬 (공간 복잡도 2n)

• pseudo code

void mergesort(int n, keytype S[])
{
	const int h=n/2;
    const int m=n-h;
    
    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);
    }
}

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

• 시간 복잡도
  • 합병함에 있어서 최악의 경우 예시) U:4,5,6,7 V:1,2,3,8
  • W(h,m) = W(h)+W(m)+h+m-1
    -> $W(n) = 2W(\frac{n}{2})+n-1 \in \Theta(nlg\ n)$

2-2-2. 합병정렬 (공간 복잡도 n)

• pseudo code

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

void merge2(index low, index mid, index high)
{
	index i,j,k;
    keytype U[low..high];
    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)
  		copy S[j] through S[high] to U[k] through U[high];
    else
    	copy S[j] through S[mid] to U[k] through U[high];
    copy U[low] through U[high] to S[low] through S[high];
}

2-3. 빠른 정렬

• pseudo code

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

• 시간 복잡도
  • partition의 경우
    • T(n) = n-1
  • quicksort의 경우 (최악) - 비내림차순 정렬된 경우
    • T(n) = T(n-1)+n-1, T(0) = 0
      -> $T(n)=\frac{n(n-1)}{2}$
  • 평균의 경우
    • pivottiem이 p번째 데이터가 될 확률 1/n
    • $A(n) = \sum_{p=1}^{n}\frac{1}{n}[A(p-1)+A(n-p)]+n-1\in\Theta(nlg\ n)$
  • 최고의 경우
    • 문제가 매번 반 씩 나누어질때
    • $T(n) = 2T(n/2)+n-1\in\Theta(nlg\ n)$

2-4. 행렬 곱셈 (쉬트라쎈 방법)

• 단순한 곱셈의 시간복잡도
  • 곱셈을 단위 연산으로
  • $T(n) = 8T(\frac{n}{2})$, $n=2^k$, $T(1)=1$
  • $\in \Theta(n^3)$
• 쉬트라센의 방법
  • 곱셈을 단위 연산으로
  • $T(n) = 7T(\frac{n}{2})$, $n=2^k$, $T(1)=1$
  • $\in \Theta(n^{2.81})$

2-5. 큰 정수 계산법

• 단순 곱셈 : $n^2$시간

곱하는 수를 나눠서 계산

• pseudo code

large_integer prod(large_integer u, large_integet v)
{
	large_integer x,y,w,z;
    int n,m;
    
    n = max(u의 자리, v의 자리);
    if(u==0 || v==0)
    	return 0;
    else if(n<=threshold)
    	return u*v;
    else
    {
    	m = floor(n/2);
        x = u div 10^m;
        y = u mod 10^m;
        w = v div 10^m;
        z = v mod 10^m;
    }
    return prod(x,w)*10^(2m) + (prod(x,z)+prod(w,y))*10^m + prod(y,z);
}

• 시간 복잡도
  • 최악의 경우
  • $W(n) = 4W(\frac{n}{2}) + cn$
    -> $\in \Theta(n^2)$ : 단순 곱셈보다 좋아지지 않았음

개선된 방법

• r = (x+y)(w+z) = xw+(xz+yw)+yz
• p = xw
• q = yz

large_integer prod2(large_integer u, large_integet v)
{
	large_integer x,y,w,z;
    int n,m;
    
    n = max(u의 자리, v의 자리);
    if(u==0 || v==0)
    	return 0;
    else if(n<=threshold)
    	return u*v;
    else
    {
    	m = floor(n/2);
        x = u div 10^m;
        y = u mod 10^m;
        w = v div 10^m;
        z = v mod 10^m;
        r = prod(x+y, w+z);
        p = prod(x,w);
        q = prod(y,z);
    }
    return p*10^(2m) + (r-p-q)*10^m + q;
}

• 시간 복잡도
  • $3W(\frac{n}{2})+cn \le W(n) \le 3W(\frac{n}{2}+1)+cn$
  • $\in \Theta(n^{1.58})$

2-6. 도사 정리

3. Algorithm: Dynamic Programming

3-1. 이항계수 구하기

• recursive property
  • B[i][j] = B[i-1][j-1]+B[i-1][j] (0<j<i)
  • 1 (j=0 or i=0)
• pseudo code

int bin(int n, int k)
{
	index i, j;
    int B[0..n][0..k];
    for(i=0; i<=n; i++)
    {
    	for(j=0; j<=min(i,k); j++)
        {
        	if(j==0 || i==0)
            	B[i][j] = 0
            else
            	B[i][j] = B[i-1][j-1] + B[i-1][j];
        }
    }
    return B[n][k];
}

• 시간 복잡도
  • $1+2+3+..+k+(k+1)+...(k+1)=\frac{k(k+1)}{2}+(n-k+1)(k+1)=\frac{(2n-k+1)(k+1)}{2}\in \Theta(nk)$

3-2. 최단경로 찾기

• recursive property
  • $D^{k}[i][j] = min(D^{(k-1)}[i][j],\ D^{(k-1)}[i][k]+D^{(k-1)}[k][j])$

Floyd1

• pseudo code

void floyd(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] = min(D[i][j], D[i][k]+D[k][j]);
        }
    }
}

• 시간 복잡도
  $T(n) = n*n*n = n^3\in\Theta(n^3)$

Floyd2

• pseudo code

void floyd2(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] = l;
                    D[i][j] = D[i][k] + D[k][j];
        }
    }
    
}

3-3. 연쇄 행렬 곱셈

• recursive property
  $M[i][j] = min_{i<=k<=j-1}(M[i][k]+M[k+1][j]+d_{i-1}d_kd_j)$
  $M[i][i] = 0$
• pseudo code

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(diagoanl = 1; diagonal<= n-1; diagonal++)
    {
    	for(i=1; i<=n-diagonal; i++)
        {
        	j=i+diagonal
            
            //k가 i보다 크고 j-1보다 작은 동안
            M[i][j] = min(M[i][k]+M[k+1][j]+d(i-1)*dk*dj); 
            P[i][j] = 최소가 되도록 하는 K;
        }
    }
    return M[1][n];
}

• 시간 복잡도
  • k루프 j-1-i+1 = diagoanl
  • i루프 n-diagonal
  • $\sum_{diagonal = 1}^{n-1}(n-diagonal)(diagonal) = \frac{n(n-1)(n+1)}{6}\in \Theta(n^3)$

3-4. 최적 이진트리

• recursive property
  $A[i][j] = min_{i<=k<=j}(A[i][k-1]+A[k+1][j]+\sum_{m=i}^{j}p_m$
  $A[i][i] = p_i$
• pseudo code

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;
            //k가 i보다 크고 j보다 작을 동안
            A[i][j] = min(A[i][k-1]+A[k+1][j]) + p[k];
            R[i][j] = 최소로 하는 k값;
        }
    }
    minavg = A[1][n];
}

• 시간 복잡도
  • k루프 j-i+1 = diagonal+1
  • i루프 n-diagonal
  • $\sum_{diagonal=1}^{n-1}(n-diagonal)(diagonal+1) = \frac{n(n-1)(n-4)}{6}\in\Theta(n^3)$

3-5. DNA 서열 맞춤

• recursive property
  $opt(i,j) = min(opt(i+1,j+1)+penalty, opt(i+1,j)+2, opt(i,j+1)+2)$

4. Algorithm: Greedy Algorithm

4-1. 최소비용신장트리

prim 알고리즘

• pseudo code

void prim(int n, const number W[][], set_of_edges& F)
{
	index i, vnear;
    number min;
    edge e;
    index nearest[2..n];
    number distance[2..n];
    
    F=none
    for(i=2; i<=n; i++)
    {
    	for(j=2; j<=n; j++)
        {
        	distance[i] = W[1][i];
            nearest[i] = 1;
        }
    }
    repeat(n-1 times)
    {
    	min = inf;
        for(i=2; i<=n; i++)
        {
        	if(0<= distance[i]< min)
            {
            	min = distance[i];
                vnear = i;
            }
        }
        e = vnear와 nearest[vnear]를 잇는 edge;
        e를 F에 추가;
        distance[i] = -1;
        for(i=2; i<=n; i++)
        {
        	if(W[i][vnear] < distance[i])
            {
            	distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
        }
    }
}

• 시간 복잡도 분석
  $T(n) = 2(n-1)(n-1)\in\Theta(n^2)$

kruskal 알고리즘

• pseudo code

void kruskal(int n, int m, set_of_edges E, set_of_edges& F)
{
	index i,j;
    set_pointer p,q;
    edge e;
    
    E에 속한 m개의 edge의 가중치를 기준으로 비내림차순 정렬;
    F = none;
    initial(n);
    while(F에 속한 edge의 개수가 n-1보다 작다)
    {
    	e = 아직 점검하지 않은 최소 가중치를 가지는 edge;
        (i,j) = e를 edge로 만드는 vertex의 인덱스;
        p = find(i)
        q = find(j);
        if(!equal(p,q)
        {
        	merge(p,q);
            e를 F에 추가;
        }
    }
}

• 시간 복잡도 분석
  • edge정렬 $\Theta(mlg\ m)$
  • disjoint set 초기화 $\Theta(n)$
  • 반복문
    • 최대 m번 수행
      $\Theta(mlg\ n)$
  • 결론 적으로 가장 큰 항인 $\in \Theta(mlg\ m)$
  • 최악의 경우
    • $m = \frac{n(n-1)}{2}\in \Theta(n^2)$
      -> $\Theta(mlg\ m) = \Theta(n^2lg\ n)$