[개념정리] 컴퓨터 구조 및 알고리즘

1. 알고리즘 개요

1.1 알고리즘 정의 및 표현 방법

1. 알고리즘

   어떤 특정한 문제를 해결하기 위한 명령어들의 집합

   알고리즘에 따라 문제를 해결할 수 있다는 것은 충분한 수행 시간과 기억 장소가 주어진 상태에서 어떤 입력에 대하여 올바른 답을 낼 수 있는 컴퓨터 프로그램이 존재함을 의미.

2. 알고리즘의 다섯가지 조건
   1. 입력 (0개 이상)
   2. 출력 (1개 이상)
   3. 명확성
   4. 유한성
   5. 효과성 (실행성; 논리적인 명령어들을 컴퓨터가 구현할 수 있어야함)
3. 알고리즘의 표현 방법
   1. 자연어 : 모호성을 내포함
   2. 순서도(플로우 차트), NS 차트 : 알고리즘이 복잡해질 수록 구현이 복잡해짐
   3. 의사코드(수도 코드) : 특정 언어와 무관하지만 주로 프로그래밍 언어와 유사한 언어를 사용함

1.2 기본적인 데이터 구조

1.2.1 배열

• 동일한 타입의 데이타 집단을 취급하는 경우에 사용할 수 있으며 기억 장소의 낭비를 막을 수 있음
  1. 1차원 배열
  • 가장 단순한 형태의 배열로서, 배열의 크기를 컴파일 중에 이미 알고 있는 경우에 사용함
    1. 2차원 배열
  • 행과 열이 있으며, 배열의 주소를 계산하는 일반적인 방법에는 행 우선순위와 열 우선 순위가 있음
  • A[m][n]에서 배열 내 원소 A[i][j]의 주소는?
  • A[0][0]의 기본 주소가 a 일 때, 데이타 크기는 고정된 크기인 1바이트로 가정함
    • 행우선 순위 : a + i*n + j
    • 열우선 순위 : a + j*m + i

1.2.2 연결 리스트

• 임의의 위치에 데이터를 삽입하거나 삭제할 때, 삭제와 삽입을 용이하게 하고 기억 장소를 낭비하지 않으면서 삽입, 삭제에 소요되는 시간을 절약하기 ㅜ이한 데이터 표현 방법
• 각 항목들은 리스트의 항목들을 순서대로 검색하기 위해 다음 항목을 가리키는 주소나 위치에 대한 정보를 가지고 있어야 함.

1.2.3 스택

• 모든 입력과 삭제가 한쪽 끝에서만 일어나는 선형 리스트
• 맨 마지막에 입력된 데이터가 가장 먼저 제거됨

1.2.4 큐

• 한쪽 끝에서 삽입되고 삭제는 다른 한쪽에서 발생됨
• 제일 먼저 입력된 데이터가 가장 먼저 제거됨
• 삽입 될 때는 뒤의 포인터(R)을, 삭제될 때는 앞의 포인터(F)를 1씩 증가시킴.
• 초기값은 -1

1.2.5 트리

• 루트라고 불리는 특별한 노드가 존재해야함
• 나머지 노드들은 분리된 집합체로 나누어지며, 여기서 각 집합체 역시 트리가 됨.
• 분리된 집합체는 서브 트리라고 부름
• 노드들의 서브 트리 수를 차수라고 부르며, 차수가 0인 노드들을 리프 노드, 단말 노드라고 부름.
• 차수가 0이 아닌 노드들을 내부 노드라고 부름.
• 형제 노드 : 같은 부모 노드를 갖는 노드들
• 레벨은 층수를 말함

1.3 순환(Recurison)

1.3.1 순환 알고리즘

• 함수가 자신을 호출함
• 간접 순환 : 함수 A가 또 다른 함수 B를 호출하고 B함수가 A함수를 다시 호출하는 방식
• 직접 순환 : 함수 A가 함수 A를 호출하는 방식
• 모든 프로그래밍 언어에서 이러한 순환이 사용 가능한 것은 아님
• 현재 처리되던 함수를 나중에 제개하기 위한 정보가 어디엔가 저장되어야 하기 때문에 속도가 늦음

1단원 연습문제

1. 컴퓨터를 이용한 문제 해결 과정에서 알고리즘과 데이터 구조 사이의 관계성을 설명하시오
   1. 알고리즘은 문제를 어떻게 해결할지에 대해서 초점을 둔다면, 데이터 구조와 같은 경우에는 데이터의 효율성을 따진다. 예를 들어서 어떤 문제를 해결하는 데에는 배열이 더 효율적인 것을 파악하는 것이 데이터 구조라면, 어떤 문제를 해결 할 때 구성은 어떻게 하면 좋은지, 순서는 어떻게 하는 것이 더 효율적인지를 보는 것이 알고리즘이다.
2. 일반적으로 알고리즘이 가지는 특성을 나열하고 이러한 특성을 만족하는 알고리즘 표현 방법들에 대해서 설명하시오
   1. 일반적으로 알고리즘이 가지는 특성은, 입력 0개이상 출력 1개이상 명확성 유한성 효과성이 있다. 이러한 특성을 만족하는 알고리즘 표현 방법들은 자연어와 순서도, NS차트, 수도코드가 있는데 수도코드가 가장 적합하다고 볼 수 있다.

3. 1차원 배열에 문자열 ‘fractal’을 저장하고 출력하는 C언어 함수를 구성하시오. 이 때 저장된 문자열의 기억 장소의 내부 구조를 그리시오

    #include<iostream>
    using namespace std;
    int main(){
        char fractal[9] = "fractal";
        cout<<fractal<<endl;
    }
   

4. 다차원 배열에 대하여 다음 물음에 답하시오. A[10][20], B[20][10]
   1. 배열 A, B의 원소의 수는?
      1. 200
   2. B[10][8]의 행 우선 시작 주소를 구하라(단, 배열의 시작 구조는 120번지이고, 한 원소는 2 바이트를 차지한다)
      1. 120+10102+8*2

5. 단순 연결 리스트의 첫번째 노드 p 에서 시작하여 그 길이를 계산하는 알고리즘을 작성하시오

    int length(NODE *last){
    	NODE *temp; // 일시적으로 temp 만듦
        int count = 0;
        if (last) {
        	temp = last; 
            do {
            	count++;
                temp = temp -> link; //temp 를 계속 다음 노드를 가리키게 만듦. 다시 돌아올 때 까지
            } while (temp != last);
        }
        return count;
    }
   

6. A + B(C/D%EF/G)-H를 후위 표기식으로 바꾸고, 스택을 사용하여 계산하는 과정을 그림으로 나타내시오
   1. A +B(Temp1%EF/G)-H
   2. A +B(Temp2F/G)-H
   3. A +B*(Temp3/G)-H
   4. A +B*(Temp4)-H
   5. A +Temp5-H
   6. Temp6-H
   7. Temp7

7. 피보나치 수열을 효과적으로 계산하기 위하여 큐를 이용할 수 있다. 큐에는 처음에 Fib[0]과 Fib[1]의 값이 들어가 있어서, Fib[2]를 계산할 때 Fib[0]을 큐에서 제거한다. 그 다음 계산된 Fib[2]를 다시 큐에 넣는다. 이를 구현하는 프로그램을 작성하시오

    #include<iostream>
    using namespace std;
    int Fibo(int n){
        if(n==1) return 1;
        else if(n==0) return 1;
        else return Fibo(n-1)+Fibo(n-2);
    }
    int main(){
        cout<<Fibo(3)<<endl;
    }
   

8. 트리의 노드 수를 찾아내는 순환 알고리즘을 작성하시오

    typedef struct TreeNode {
      int data;
      struct TreeNode *left, *right;
    }
    TreeNode;
        
       
        
    int get_node_count(TreeNode *root) { // 트리에 존재하는 모든 노드의 갯수를 구한다.
      if (!root)
        return 0;
      else
        return get_node_count(root->left) + get_node_count(root->right) + 1;
    }
        
    int main() {
      TreeNode n4 = { 500, NULL, NULL };
      TreeNode n5 = { 200, NULL, NULL };
      TreeNode n3 = { 100, &n4, &n5 };
      TreeNode n2 = { 50, NULL, NULL };
      TreeNode n1 = { 0, &n2, &n3 };
        
      printf("모든 노드 개수 = %d\n", get_node_count(&n1));
    }
   

9. 순환이 모든 경우에 효과적인가? 만약 아니라면 그 이유를 밝히라
   1. 순환은 중간에 끊김이 발생하기 때문에, 끊긴 지점을 저장해야함. 그렇기 때문에 모든 경우에 효과적이라고 판단할 수는 없음. (현재 처리되던 함수를 나중에 제개하기 위한 정보가 어디엔가 저장되어야 하기 때문에 속도가 늦음)
10. 하노이탑 문제 : 3개의 탑이 있는데 첫번째 탑에는 반경이 서로 다른 10개의 원판이 쌓여있다. 또한 각 원판은 반경이 큰 순서대로 아래에서부터 쌓여있다.
    1. 한번에 한개의 원판을 다른 탑으로 옮길 수 있다.
    2. 쌓아놓은 원판은 항상 아래의 것이 위의 것보다 반경이 커야한다.

    위의 두 규칙을 지키며 첫번째 탑에서 세번째 탑으로 모든 원판을 옮기려고 한다. 이 작업을 위한 프로그램을 작성하시오. 단, 원판 이동 과정을 모두 출력할 수 있어야 한다.

02. 알고리즘 분석 및 설계 방법

2.1 알고리즘 분석

1. 주어진 문제를 분석하는 데에 고려해야할 것들
   1. 크기(데이터의 양)
   2. 자원(수행 시간)
      • 입력데이터를 처리하는 시간, 즉 평균의 경우와 입력 구성상의 모든 사항을 고려하여 처리하는 수행 시간, 즉 최악의 경우로 나누어서 고려해야함
2. 알고리즘 분석 시 프로그래머가 미칠 수 있는 영역이 아닌 중요한 요소들
   1. 프로그램이 특정 컴퓨터에서 기계어로 번역될 때 하나의 명령문이 실행되기 위해서 얼마나 많은 코드를 산출하는가
   2. 입력 데이터에 대해 민감하게 살펴보아야함. 평균의 경우는 프로그램 사용 시 실제 데이터를 대표하지 않는 수학적 가설을 기본으로 분석하고, 최악의 경우는 프로그램 수행시 실제로는 발생하지 않을 수 있는 색다른 상황을 고려해서 분석해야함
   3. 수학적 결과를 이용하지 못하는 프로그램들이 실제로 많음
   4. 주어진 문제를 해결하기 위한 프로그램들에 대하여 모두 비교를 할 수 없음
3. 알고리즘 분석 단계
   1. 알고리즘에 입력될 데이터의 특성을 명세하고 적절한 분석 형태를 결정함.
      1. 수행 시간의 분포를 얻는 것이 가장 이상적인 분석 형태임
      2. 각 입력 데이터에 대한 알고리즘 수행 시간이 정확하게 확률 분포를 일치시키지는 못하기 때문에, 대개 어떤 입력에 대해서도 수학 시간이 Upper Bound보다는 적게 수행되도록 하고, 임의의 입력 데이터를 사용하여 평규 ㄴ수행 시간을 유도하는데 관심을 갖는 분석 형태를 취하도록 해야함
   2. 알고리즘 구현과 독립적으로 알고리즘 내의 추상적 연산을 규정해야함 .
      1. 알고리즘 성능에 관련되는 연산만을 일반적으로는 규정함
   3. 각 연산 횟수에 대하여 평균의 경우와 최악의 경우로 분리하여 수학적 분석을 수행해야함.

*알고리즘 분석은 분석가가 요구하는 수준에 도달할 때까지 분석에 대한 분석, 평가, 정련과정을 순환적으로 수행함

2.1.1 알고리즘 분석 기준

1. 알고리즘을 분석하는 데에 사용되는 일반적인 기준 5개
   1. 정확성 : 귀납적 증명이며, 기본 필수적인 조건임. 모든 경우에 정확한 답을 내는지 확인 필요
   2. 작업량 : 시간적 비용. 주로 중요 연산 기준
      1. 실행 시간은 컴퓨터에 따라 상이할 수 있기 때문에 적절한 기준이 아님
      2. 명령어의 개수 역시 프로그래머와 프로그래밍 언어에 따라서 달라질 수 있기 때문에 저절하지 못함
      3. 중요 연산들의 합으로 구할 수 있음
   3. 기억 장소 사용량 : 공간적 비용
      1. 명령어들, 상수와 변수, 입력자료를 위한 기억공간에 따름.
   4. 단순성 : 이해도, 수정 가능성
   5. 최적성 : 상한, 하한 개념 사용
      1. 어떤 알고리즘이 최적이다라고 말하는 것은, 그 알고리즘보다 중요 연산이 적은 알고리즘이 없다는 것을 의미함
      2. 어떤 문제를 해결하려는 데 필요한 작업량이 하한을 설정하는 정리를 증명하는 방법
         1. 효과적이라고 생각되는 알고리즘을 고안해 낸 뒤, 그 알고리즘을 분석하여 최악의 경우 W(n)을 찾아낸다.
         2. 입력데이터의 크기가 n인 경우 어떤 함수 F에 대해 고안된 알고리즘과 동일한 문제를 해결하려는 부류에 속하는 어떠한 알고리즘도 최소한 F(n)의 작업량을 수행해야 함을 증명함
         3. F(n)==W(n)이인 경우, 고안된 알고리즘은 최적이 됨.

   *주로 작업량(시간) 기억장소(공간)을 중점적으로 분석함

2.1.2 평균과 최악의 경우 분석

알고리즘의 작업량에 관한 분석에 있어서, 분석의 결과를 간결하게 표현하는 것이 필요함.

알고리즘을 통해 해결하려는 문제와 입력 데이터의 양이 고려되어야 하는데, 알고리즘의 평균 행동 양식을 통해서 알고리즘을 분석할 수 있다. 하지만, 이 또한 어떤 입력이 다른 입력보다 더 잘 등장할 수 있기 때문에 가중 평균을 생각할 수 있음.

2.1.3 점근적 복잡도 및 중요성

중요 연산들만 이용하여 작업량을 정하는데, 어떤 연산들을 포함시키고 어떤 연산들을 제외시킬지에 대해서 생각해 보아야함. 중요 연산의 선택은 수행되는 전체 연산의 개수와 비례 가능함

• 상수만 다른 두 함수는 일반적으로 동일한 차수를 가진다.
• 예제) 순차 탐색
  • 크기가 n인 배열 L에서 특정한 값 찾기

    index = 0; //할당 연산
    while(index<n && L[index]!=x) //비교연산, 논리연산, 비교연산 // L[index]!=x가 중요연산
    	index ++; //증가 연산
    if(index>=n) //비교 연산 
    	index =-1; //치환 연산
  

귀납적 증명

f(n)=g(n) n은 0보다 큰 자연수를 증명

1) n =1일 때 성립함을 보인다

2) n=i 일 때 위의 수식이 성립한다고 가정하면, n = i+1일 경우에도 성립함을 보임

즉, 모든 n에 대해 수식 성립

예제 : 최대값 찾기

• 배열 원소 가운데 최대값 찾기(p.42)
• 문제 크기:
  • 크기가 n인 배열 L을 입력 대상으로 하므로 n
• 중요 연산 : 원소 비교 연산(비고 : ++, = 연산)
• 최적성: 상한/하한 일치 → 최적
  • 이것보다 더 빠른 알고리즘이 없음을 보임

max = L[0];
for(index = 1; index<n; index ++)
	if(max<L[index]) max = L[index];
//작업량은 언제나 n-1번임. 

예제 : 행렬의 곱

• 2개의 n*n 행렬의 곱셈
• 문제 크기 : n (차원이 n, 원소 개수 n^2)
• 중요 연산 : 원소 곱셈
• 최적성 분석
  • 상한 : n^3
  • 하한 : n^2
• 결론 : 최적성 판단 불가
  • 더 낮은 상한 발견 (더 우수한 알고리즘 개발 가능성 존재)
  • 더 높은 하한 분석 (분석적인 방법 제안 가능)

for(i = 0; i<n; i++){//a의 열 개수
	for(j= 0; j<n; j++){//b의 열 개수이자 a의 행 개수
		c[i][j] = 0; //0으로 초기화
		for(k = 0; k<n; k++)
			c[i][j]+= a[i][k]*b[k][j]; // 곱해서 더하는거
	}
}
//많아봤자 n^3걸림

알고리즘 복잡도

• 점근적 복잡도 함수 사용
  • 차수의 중요성 :
    • 계수보다는 차수가 더욱 중요함
  • 점근적 복잡도를 나타내는 함수
    • 빅오 빅 세타 빅 오메가 함수
  • 함수의 표기의 정의 및 의미
    • 빅오 : f(n)보다 차수가 같거나 낮은 함수들
      • ex ) o(n^2) = {3n^2, 3n^2 + 3n + 4, …) // 기껏해야 n^2
    • 오메가 : f(n)보다 차수가 같거나 높은 함수들
      • ex ) 오메가(n^2) = {5n^2, n^4 , …) // 적어도 n^2
    • 빅 세타 : f(n)과 차수가 같은 함수들
      • ex ) 빅세타(n) = {3n+2, 2n , n + 4, …) // 딱 n
    • 사용시 다른 해석 : 등호 사용, 계수 및 낮은 차수항 무시, 가장 근접한 차수를 사용함

알고리즘의 선택

• 최종 선택시 주의점
  • 분석적 평가 :
    • 복잡도 분석, 우수한 것 선택
    • 실제 n값에 따른 선택 필요(현실적 판단)
      • 분석적으로 좋아도 실험 시 안좋을 수 있음
  • 실험적 평가 :
    • 실제의 실행 시간 측정, 평가
  • 문제 크기의 적절한 예측 :
    • 혼합 알고리즘 개발
      • 중간 규모에서 a 알고리즘이 좋고, 대규모에서는 b알고리즘이 좋다면 둘을 혼합할 수 있음
    • 계수의 효과도 중요
    • 정확성, 신뢰성, 해독성 등을 고려
    • 기타(1회용?)

순환 알고리즘의 복잡도

• 알고리즘 종류별 복잡도 계산
  • 순환 vs 반복
• 반복 알고리즘의 복잡도
  • 주로 반복문에 의해 차수 결정
• 순환 알고리즘의 복잡도
  • 순환 방정식을 이용한 해법 사용

하노이타워

def HT(n, A, B, C)
	{
		if(n == 1) move A to C; //여기서 move가 중요 연산임 
		else 
			{
				HT(n-1, A, C, B); //T(n-1)번 이동
				move A to C; //1번 이동
				HT(n-1, B, A, C); //T(n-1)번 이동
			}
	return;
}

//T(1) = 1, T(2) = 2*1+1 = 3, T(3) = 2*3+1 = 7, ...

순환 방정식 유도

\[T(n) = T(n-1)+1+T(n-1)\]

T(n)의 수식 구하기

\[T(n-1) = 2T(n-2) + 1\] \[T(n) = 2T(n-1) + 1\]

=2{2T(n-2) + 1} +1

= 2^2*T(n-2) +2 + 1

= 2^2{2*T(n-2)+1} + 2+ 1

= 2^3 * T(n-2) + 2^2 + 2 + 1

…

= 2^k {2*T(n-k) + 1 } + 2^(k-1) + 2 ^(k-2) ..

\[=1-2^(k+1)/(1-2)\]

이원 합병 정렬

• 전체 n개의 데이터를 정렬시키는 것이 목표임
• 2개를 나눠서 합침. n개의 데이터를 무조건 반씩 나눔.
• n이 홀수일 때는 홀/짝으로 구성
• 1, 2를 반복함
  1. 일단 두개로 나눈다
  2. 2개로 나누어진 것들을 각각 정렬함

def Merge_Sort(A, a, c){
	int A[ ], a, c;
		{
			int b;
			if(a < c) //만약 c가 a보다 크다면
			{
				b = ⌊(a+c)/2⌋; //중간값을 구함
				Merge_Sort(A, a, b); //a, b, c는 배열의 인덱스임 
				Merge_Sort(A, b+1, c);
				Merge(A, a, b, c); //합병 . 대략적으로 n번정도 비교가 필요함. 
			}
	}
}

T(1) = 0

T(n) = T(n/2)+ T(n/2) + n (n>1)

= 2T(n/2) + n

= 2*{2T(n/4) + n/2) + n

= 2^2T(n/(2^2)) + 2n

= 2^kT(n/(n^k)) + kn

• 복잡도 :

\[O(nlog_2n)\]

순환 방정식 계산

• 대입법
• 반복법
• 일반법

알고리즘의 선택

• 최종 선택시 주의점
  • 분석적 평가
    • 복잡도 분석, 우수한 것 선택
    • 실제 n값에 따른 선택 필요(현실적 판단)
      • 분석적으로 좋아도, 실험시 안좋을 수 있음.
  • 실험적 평가
    • 실제의 실행 시간 측정, 평가
  • 문제 크기의 적절한 예측
    • 혼합 알고리즘 개발?
      • A,B 알고리즘이 있고 중간 규모에서는 A, 대규모에서는 B가 좋다고 치자. 둘 다 쓸수 있으면 혼합해서 사용 가능
  • 계수의 효과도 중요
  • 정확성, 신뢰성, 해독성 등도 고려
  • 기타(1회용)

순환 알고리즘 분석

하노이 타워

HT(n, A, B, C)
{
	if(n == 1) move A to C;
	else 
	{
		HT(n-1, A, C, B);
		move A to C;
		HT(n-1, B, A, C);
	}
return;
}

1. 순환 방적식 유도

1. T = 1 // 하노이 타워의 원반이 움직인 개수
2. n>1일 때, T(n) = 2T(n-1) + 1

2. T(n)의 수식 구하기

T(n-1) = 2T(n-2) +1

= 2^k +

최대값 찾기

• 문제 크기 : 입력 데이터 개수
• 중요 연산 : 비교 연산의 개수
• 작업량 : 언제나 n-1 번
• 기억장소 사용량 : n

최대, 최소값 동시에 찾기

• 단순한 방법

    STRAIGHTMAXMIN(int max, int min)
    {
    	int i, n;
      
    	max = min = A[1];  // cf. A[0]
    	for(i = 2; i <= n; i++)  // (cf) for (i = 1; I < n; n++) //2부터 n+1까지 n번 실행
    		{
    			if(A[i] > max) max = A[i];
    			/* else */
    			if(A[i] < min) min = A[i];
    		}
    }
  

  • Else 를 넣는 것이 효율이 더 좋음

• 순환 알고리즘

    MAXMIN(int i, int j, int *fmax, int *fmin)
    /* A는 A[1], A[2], ..., A[n] 배열, 1 ≦ i ≦ j ≦ n */
    {
    	if(i == j) // 원소가 하나일 때 
    		*fmax = *fmin = A[i];
    	else if(i == j-1) //원소가 붙어있을 때
    		*fmax = max(A[i], A[j]);
    		*fmin = min(A[i], A[j]);}
    	else if(i < j-1){ //원소가 3개일 때 
    		int mid, gmax, gmin, hmax, hmin;
    		mid = (i+j) / 2;   /* mid=⌊(i+j)/2⌋와 동일*/
    		MAXMIN(i, mid, &gmax, &gmin);
    		MAXMIN(mid+1, j, &hmax, &hmin);
    		*fmax = max(gmax, hmax);
    		*fmin = min(gmin, hmin);
    		}
    }
      
    main(){
    	int n, x, y;
    	MAXMIN(1, n, &x, &y);
    	printf("MAX = %d, MIN = %d", x, y);
    }
  

• 개선된 순환 알고리즘

    MAXMIN(int i, int j, int *fmax, int *fmin)
    /* A는 A[1], A[2], ..., A[n] 배열, 1 ≦ i ≦ j ≦ n */
    	{
    		if(i == j) 
    		*fmax = *fmin = A[i];
    		else if(i == j-1)
    		{
    			if(A[i] < A[j]) //함수호출 없이 비교
    			{
    				*fmax = A[j];
    				*fmin = A[i];
    			}
    			else 
    			{
    				*fmax = A[i];
    				*fmin = A[j];
    			}
    	}
    		else if(i < j-1)
    	{
    		int mid, gmax, gmin, hmax, hmin;
    		mid = (i+j) / 2;   /* mid=⌊(i+j)/2⌋와 동일*/
    		MAXMIN(i, mid, &gmax, &gmin);
    		MAXMIN(mid+1, j, &hmax, &hmin);
    		*fmax = max(gmax, hmax);
    		*fmin = min(gmin, hmin);
    	}
    }
  

• 더욱 효과적인 순환 알고리즘

    MAXMIN(int i, int j, int *fmax, int *fmin)
    	/* A는 A[1], A[2],..., A[n] 배열, 1≦i≦j≦n */
    	{
    		if(i >= j-1) /* 즉, j-1≦i≦j, 원소가 1~2개 */
    		{
    			if(A[i] < A[j])
    			{
    				*fmax = A[j];
    				*fmin = A[i];
    			}
    			else 
    			{
    				*fmax = A[i];
    				*fmin = A[j];
    			}
    		}
    		else /* if(i < j-1) => 불필요 */
    		{
    			mid = (i+j) / 2;
    			MAXMIN(i, mid, &gmax, &gmin);
    			MAXMIN(mid+1, j, &hmax, &hmin);
    			*fmax = max(gmax, hmax);
    			*fmin = min(gmin, hmin);
    		}
    }
  

정렬

정렬의 중요성 및 정렬 종류

내부 정렬

• 정렬 데이터가 크지 않고, 배열로 선언해서 다룰 수 있음.
• 입력데이터가 적절히 작음
• 보통 정렬이라고 함

삽입 정렬

• 주요 특징
  • 하나씩 삽입하여 정렬
  • k 번째 자료에 대해 생각할 때, 앞의 k-1 개 자료는 이미 정려로딤
• 복잡도 분석
  • k번째 자료의 비교 회수
    • 최상 1회
    • 최악 k-1 회
    • 평균 k/2회
  • 전체 비교 회수
    • 최상 n-1
    • 최악 1+2+3+… n-1 = O(n^2)
    • 평균 O(mn)
      • m = 순서가 틀린 자료의 개수

    void insertion_sort(data A[], int n)
    	{
    		int i, j;
    		data temp;
    		for(i = 2; i <= n; i++).  //2부터 n까지 
    	{
    		temp = A[i]; //A[i-1]까지는 정렬되어 있음. 값 복사하는 부분 
    		j = i; //j 는 i  부터 시작
    		while(j > 1 && A[j-1] > temp) //j가 1보다 크고, A[j-1]이 기존 데이터보다 클 때 
    		{
    			A[j] = A[j-1]; //한칸씩 땡겨주는 작업 
    			j--;
    		}
    		A[j] = temp; //j는 새로운 데이터가 들어갈 자리임
    	}
    }
  

//삽입정렬 2
void insertion_sort(data A[], int n)
	{
		int i, j;
		data temp;

		for(i = 2; i <= n; i++){ //2부터 n까지임 
			temp = A[i]; //temp에 해당 값 저장
			for(j = i; j > 1; j--)// j가 1보다 클 때까지 반복 
				if(A[j-1] > temp) A[j] = A[j-1]; // 만약 A[j-1]이 tmp 보다 크면, 교환  
				else break;
			A[j] = temp;
		}
}

선택 정렬

• 주요 특징
  • 삽입 정렬에 비해 이동량 감소
  • 한번에 하나의 자료를 선택하여 해당 위치에 배정
    • 전체 데이터 중 가장 큰 데이터를 찾아서 그 원소를 제일 뒤로 보냄
• 복잡도 분석
  • k 번째0 단계의 비교 회수 : n-k 회
  • 전체 비교 회수 : n-1, n-2, n-3… 2+1 = O(n^2)
  • 자료 교환 회수 : 각 단계에서 1회 교환, 이동 3회 , 총 이동 회수 : 3(n-1)회 = O(n)
    • 이동 3회는 tmp 를 사용하기 때문

//최소값 이용
void selection_sort(data A[], int n)
	{
		int i, j, min;
		data temp;

		for(i = 1; i < n; i++)
	{
		// A[i]~A[n] 중 최소값의 인덱스 찾기
		min = i; 
		for(j = i+1; j <= n; j++)
			if(A[j] < A[min]) min = j; //비교연산. 중요 연산임. min이 최소값을 가르키는 인덱스

		// A[i]와 A[min]을 교환
		temp = A[min]; //원소이동은 3번, 전체 이동수는 n-1 곱하기 3
		A[min] = A[i];
		A[i] = temp;
	}
}

//최대값 이용
void selection_sort(data A[], int n)
	{
		int i, j, max;
		data temp;

		for(i = n; i > 1; i--) 
		{
		// A[1]~A[i] 중 최대값의 인덱스 찾기
			max = 1; 
			for(j = 2; j <= i; j++)
				if(A[j] > A[max]) max = j;
		
		// A[i]와 A[max]를 교환
		temp = A[max]; 
		A[max] = A[i];
		A[i] = temp;
	}
}

버블 정렬

• 주요 특징
  • 인접한 두 원소를 비교, 필요할 때 교환
  • 각 단계에서 대상 원소 중 최대값이 제일 뒤로 이동
  • k번 적용 후, 뒤 쪽 k개는 이미 정렬됨
• 복잡도 분석
  • k번째 단계의 비교 회수 : n-k회
  • 전체 비교 회수 : O(n^2)회// 위에 선택정렬과 식 같음
• 문제점 및 개선
  • 한 자료가 여러번 교환될 수 있음
  • 이미 정렬된 경우에도 계속 수행될 수 있음

void bubble_sort(data A[], int n)
{
		int i, j;
		data temp;
		for(i = n; i > 1; i--) // i >= 1 
			for(j = 2; j <= i; j++)
				if(A[j-1] > A[j])
					{   // A[j]와 A[j-1]을 교환
						temp = A[j-1]; 
						A[j-1] = A[j];
						A[j] = temp;
					}
}

• k단계 결과 : 뒤쪽 k개는 이미 정렬됨
• 이미 정렬된 경우에도 계속 비교가 진행됨. 해결 방안은 플래그를 만드는 것

//플래그가 있는 버블 정렬
int A[15] = {...};
int n = 15;

void bubble_sort()
{
		int i, j, flag;
		int temp;

		for(i = n-1; i > 0; i--) 
		 {   
				flag = 0;
				for(j = 1; j <= i; j++)
					if(A[j-1] > A[j])
						{   // A[j]와 A[j-1]를 교환
							temp = A[j-1]; 
							A[j-1] = A[j];
							A[j] = temp;
							flag++; // 정렬이 다되면 flag를 올림 ! 
							}
		    if(flag == 0) break;  //만약 정렬할게 없으면 break 함 = 정렬다되면 멈춤 
		}
}

쉘 정렬

• 주요 특징
  • 어차피 교환.이동할 원소라면 미리 멀리 떨어서 이동시킴
    • h만큼 떨어진 자료들끼리만 정렬
      • 그룹 속에는 n/h개가 포함됨
    • h 정렬 방법으로는 주로 삽입정렬 기법을 사용함
      • 이유: 삽입 정렬 계열은 계속 진행하면 다음 단계에 더 적은 시간이 소요되기 때문
      • h = 1인 h 정렬은 우리가 기존에 알고 있던 삽입 정렬임
• 복잡도 분석
  • O(n(logn)2) , O(n1.5)로 알려짐
  • h-수열을 121, 40, 13 , 4, 1로 할 때 가장 효과적임
• 상당히 큰 규모의 입력에 대해서도 적절한 수행시간을 보임

void shell_sort(data A[], int n)
{
	int i, j, h;
	data temp;

		// h 값을 미리 계산 
	for(h = 1; h <= n/e; h=3*h+1) //h를 키우는 작업. n값에 따라서 h가 커짐 
		; // do nothing
	for( ; h > 0; h = h / 3) // h 수열에 대해
		for(i = h+1; i <= n; i++) // i값을 지정
		{
			temp = A[i];
			j = i; //j는 i 의 값
			while(j > h && A[j-h] > temp) //j가 h보다 크고,  A[j-h]가 tmp 보다 클 때 
			{
				A[j] = A[j-h];
				j = j - h;
			}
			A[j] = temp;
	}
}

퀵정렬

• 주요 특징
  • 기준 자료(피봇)을 선택하여, 이 자료를 기준으로 좌, 우 두 그룹으로 분리함
  • 피봇보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 배정함
    • 파티션 알고리즘을 적용하여 배정
    • 분할 알고리즘을 적용하여 배정
  • 피봇 선택 방법은 다양함
  • 분리된 두 그룹을 각각 독립적으로 정렬하는데, 주로 순환 알고리즘을 사용함
• 복잡도 분석
  • 파티션 과정 : n번 가량의 비교(정확히는 n+1)
  • 최상의 경우
    • O(nlogn)
      • 2T(n/2) + (n+1)
      • 반으로 자른거 두번 비교 + 파티션 과정
  • 최악의 경우
    • O(n^2)
      • T(n-1) + (n+1)
      • 모든거 비교 + 파티션 과정
  • 평균의 경우
    • O(nlogn)
• 분할 함수, 파티션 알고리즘의 기능
  • 피봇을 기준으로 좌우를 정렬해줌
• 장단점
  • 소규모 자료 집단에서는 부적합
  • log2(및)n개의 스택 사이즈가 필요함
• 고려사항
  • 구체적인 파티션 중단 조건 필요
  • 피봇 선택 기법
    • 특히 중간값 선택했을 때 이점이 많음
  • ㅅ고규모 자료에 대한 개선책으로 하이브리드 방식이 있음

void quick_sort(data A[], int L, int R)
{
	int i;
	
	if(R > L) 
		{
			i = partition(L, R); //L과 R 의 피봇을 설정해줌 
			quick_sort(A, L, i-1); //i-1은 왼쪽 배열
			quick_sort(A, i+1, R);
		}
}

퀵정렬 응용- 선택알고리즘

• 배열에서 k 번째 큰 자료를 선택하는 알고리즘
• 방법
  • 퀵 정렬에서 사용된 파티션 함수를 이용
    • 만약 i == k이면 A[i] 이고
    • i>k 이면 1~i-1까지 찾고
    • i<k이면, i~ n 까지 찾음

// 마지막 원소를 Pivot으로 할 경우
void quick_sort(data A[], int L, int R)
{
	int i, j;data temp, t;

	if(R > L) 
	{
		temp = A[R]; i = L-1; j = R;
		do {/* compare L, ..., (R-1) */ 
		do {i=i+1;} while (A[i] < temp);//기존 데이터보다 현 데이터가 작으면 건너 뛰어라 
		do {j=j-1;} while (j>L &&A[j] > temp); //기존 데이터보다 현 데이터가 크면 건너 뛰어라 
		if (i < j) { /* swap A[i]&A[j] */
	    t=A[i]; A[i]=A[j]; A[j]=t;
	}
} while(j > i) //j가 i보다 클 때, 즉 배열의 길이가 2 이상일 때 

	/* swap A[R] and A[i] */
	t = A[i]; A[i] = A[R]; A[R] = t;
	quick_sort(A, L, i-1);
	quick_sort(A, i+1, R);
	}
}

//퀵정렬 변형, 첫번째 원소가 피봇
void quick_sort(data A[], int L, int R)
{
	int i, j;data temp, t;
	
	if(R > L) 
	{
		temp = A[L]; i = L; j = R+1;
		do { // compare L+1, ..., R 
		do {i=i+1;} while (i <= R && A[i] < temp);
		do {j=j-1;} while (A[j] > temp);
		if (i < j) { // swap A[i] and A[j] 
			t = A[i]; A[i] = A[j]; A[j] = t;
		}
	} 
	while(j > i)
	// swap A[L] and A[j] 
	t = A[j]; A[j] = A[L]; A[L] = t;
	quick_sort(A, L, j-1);
	quick_sort(A, j+1, R);
	}
}

//반복적 퀵정렬 수정
//스택 사용. 순환 알고리즘 사용안함
void quick_sort(data A[], int n)
{
	int i, L, R;

	L = 1; R = n; 
	stack_init();
	push(L); push(R); //스택 설정 

	while(!stack_empty()) 
	{
		R = pop(); L = pop(); //pop 하면 위에 꺼가 먼저 튀어 나옴

		while(R > L) //원소가 2개 이상이면, 
		{
			i = partition(L, R); //좌우를 i를 기준으로 정렬함 
			if((i - L) > (R - i))// 작은걸 먼저 하겠다는 뜻. l이 작으면 l 먼저 하겟다
				push(L); push(i-1); L = i+1;
			else 
				push(i+1); push(R); R = i-1;
				}
		} 
}

선택 알고리즘

// k번째 데이터 찾기
data select(data A[], int L, int R, int K) //L~R중 K번째 수를 찾아라 
{
	if (R > L) //원소가 2개 이상이라면
		{ //인덱스로 맞추려고 K가 L+K-1로 바뀜 
			i = partition(L, R);
			if(i > L+K-1) select(A, L, i-1, k);
			elseif(i < L+K-1) select(A,i+1,R,(L+k-1)-i);
			else return(A[i]); // if(i == L+K-1) 불필요
	}
}

2원 합병 정렬

• 복잡도 분석을 보면, 좋은 알고리즘이지만 성능이 좋다는 말은 순환 알고리즘 때문에 말하기 힘듦
• 퀵정렬에 바탕을 둠
• 주요 특징
  • 자료를 거의 동일한 크기의 2개의 그룹으로 나누고, 각각을 별도로 정렬한 후 합병함
  • 순환 알고리즘 방식
• 복잡도 분석
  • 합병에 따른 비교 회수 : n 번
  • 순환 방정식 : T(n) = 2(T/2) + n
  • 전체 비교 회수 : O(nlogn)
• 장단점
  • 추가 기억장소 사용량
  • 퀵정렬도 log2(지수)n개의 stack 메모리 필요

void merge_sort(data A[], int L, int R) //L이 시작, R이 끝 
{
	int m;

	if(R > L) 
	{
		m = (R+L) / 2; //중간값을 내림하여 구함 
		merge_sort(A, L, m);
		merge_sort(A, m+1, R);
		merge(A, L, R, m);
	}
}

합병알고리즘 1

void merge(data A[], int L, int R, int m)
{
	int i, j, k; 
	data B[];

//아래 for문 2개는 쭉 복사하는 코드
	for(i = L; i <= m; i++) B[i] = A[i]; 
	for(j = m; j < R; j++) B[R+m-j] = A[j+1];

	i = L; j = R;
	for(k = L; k <= R; k++)
		A[k] = (B[i]<B[j]) ? B[i++]:B[j--]; //B[i]가 B[j]보다 작으면 값을 넣고 아니면 둘의 인덱스를 바꿈
}

합병알고리즘 - 이원 합병 말고 일반적인 알고리즘

//정렬된 입력:B[M],C[N], 합병된 출력:A[L],L=M+N 
merge(data A[], data B[], data C[], int L, int M, int N) //M은 B의 길이, N은 C의 길이
//합병 결과가 A
{
	int i, j, k; 

  i = j = k = 1;
	while (i <= M && j <= N)
		{
			if (B[i] < C[j]) A[k++] = B[i++]; //A[k]에 B[i]를 주고, k와 i를 이후에 증가 
			else A[k++] = C[j++];
			}
	if (j > N) /* B[]의 나머지 처리 */
		while(i <= M) //B의 범위 내에서 실행함 
			A[k++] = B[i++];
	else /* C[]의 나머지 처리 */
		while (j <= N) 
			A[k++] = C[j++];
}

일반적인 합병 알고리즘 2

//일반적 합병 알고리즘 1 과는 다르게, 입력 데이터가 B 하나임
//정렬된 입력: B[1..M],B[M+1..N], 합병된 출력: A[1..N] 
void merge(data A[], data B[], int M, int N) 
{
	int i, j, k; 

  i = k = 1; j = M+1;
	while (i <= M && j <= N)
		{
			if (B[i] < B[j]) A[k++] = B[i++];
			else A[k++] = B[j++];
		}
	if (j > N) /* 앞부분 나머지 처리 */
		while(i <= M) 
			A[k++] = B[i++];
	else /* 뒷부분 나머지 처리 */
		while (j <= N) 
			A[k++] = B[j++];
}

히프 정렬 - 가장 좋고 빠름

• 주요 특징 :
  • 최대 히프 구조의 특성을 최대한 활용
  • 최대 히프 구조는 특정 조건을 만족하는 이진 트리
    • 부모 노드의 값은 자식 노드의 값보다 크거나 같음
    • 레벨 최소
  • 결과적으로 루트 노드가 가장 큰 값을 가짐
  • 최대 히프 구조를 계속 재구성 하면서 루트 노드를 한번에 하나씩 차례대로 추출
  • 밑에서부터 올라가면서 확인함
• 복잡도 분석
  • 최대 히프 구조 초기 생성 O(nlogn)
  • 최대 히프 재구성
    • 매회 최대 O(logn), 총 n-1회
    • 전체 비교회수 O(nlogn)
  • 장단점
    • 재귀함수를 사용안하기 때문에 이원 합병보다 더 좋은 성능을 보임
    • 퀵정렬과는 다르게 추가 기억공간이 불필요함
  • Max heap, Min heap이 있음
  • 최대값을 찾기에 유리한 완전 이진 트리
  • 자식노드를 왼쪽 먼더 만듦!!! 그래서 왼쪽은 꼭 있음

void Heap_Sorting(data A[], int n) //n이 전체 데이터 길이임
{
// 최대 히프 구조 생성 
	for (i = n/2; i > 0; i--) //마지막 부모노드부터, 루트노드가 될 때 가지 부모 자식간의 문제 해결
	Max_heap(A, i, n);//MAx_heap 이 되면 제일 큰 데이터가 루트에 있음 

// 실제 정렬 
	for(i = n-1; i > 0; i--) 
	{
// 두 원소 A[1], A[i+1] 교환
		swap(A[1], A[i+1], temp); //로트노드와 마지막 노드를 바꿈
		Max_heap(A, 1, i); // 1부터 i까지 정렬하라. 즉, 1번부터 n-1까지 정렬하라. 지금 n에는 최대값이 있음 
	}
}

void Max_heap(data A[], int root, int n)
{
	root_data = A[root]; 
	child = root * 2; //왼쪽 child
	while (child <= n)//자식노드가 있으면 ! 
	{
		if(child < n && A[child] < A[child+1]) //자식이 2개면~, 왼쪽자식<오른쪽 자식이면  
			child = child + 1;
		if(root_data > A[child]) break
		else {   //그게 아니라면 위로 이동 ,root에 제일 큰 것이 저장되어 있으니까 이동시켜주는 것 
	    A[child/2] = A[child];  //부모노드값에 자식 노드의 값을 넣어라
		  child = child * 2; //자식 노드의 인덱스에 부모노드의 인덱스를 넣음 
		}
	}
	A[child/2] = root_data;
}

기수 정렬

• 숫자 정렬임. 학번처럼
• 주요 특징
  • 자리수는 최대 3자리
  • 십진수의 경우, 숫자의 개수
  • LSD, MSD 순으로 정렬
    • LSD : 가장 낮은 자리수
      • 차수로 정렬가능 . 정리는 셤 1에 pg 68
    • MSD : 가장 높은 자리수

#define MAX_DIGIT 3// 최대숫자자리수, 즉 0-999
#define RADIX 10// 진수, 즉 10진수
struct list_node {
int key[MAX_DIGIT];
struct list_node *link;
};

void radix_sort(struct list_node *ptr)
{
	struct list_node *front[RADIX], *rear[RADIX];

	for(i = MAX_DIGIT-1; i >= 0; i--) // 각 단계별 
		{
			front[i] = rear[i] = NULL; // 초기화
	
			while(ptr) // 모든 노드에 대해 반복
			{
				digit = ptr->key[i];

				if(front[digit] == NULL) front[digit] = ptr;
				else rear[digit]->link = ptr; // 뒤에 연결
			
				rear[digit] = ptr
				ptr = ptr->link;
				rear[digit]->link = NULL; // 필요?
				}
// 전체 리스트 재구성
		ptr = NULL;
		for(j = RADIX-1; j >= 0; j--)
			if(front[j] != NULL) {
				rear[j]->link = ptr;
				ptr = front[j];
			}
		}
}

내부정렬 분류 및 성능 비교표 있음

외부 정렬

• 용어:
  • 런 : 기억 장소 내에서 정렬할 수 있는 적정 크기의(최대 크기의 ) 부분 리스트
  • 내부정렬로 해결 가능한 데이터가 기억장소 내에서 정렬할 수 있는 적정 크기의 부분 리스트임
• 입 출력 자료
  • 입 출력 자료는 대규모 자료로서 파일이나 테이프 등에 보관
  • 여러개의 런으로 구성, 각 런은 이미 내부 정렬 알고리즘을 통해서 정렬되어 있다고 가정
• 파일 읽고 쓰는게 테이프가 오래걸릴 수 있음

외부정렬-2원 합병 정렬, 다단계 합병

균형 2원 합병 정렬 예시 그림 치면 셤1에 나옴

4장. 탐색

• 기본 탐색
  • 선형 탐색, 개선된 선형 탐색
• 이진 탐색
• 트리 탐색
  • 이진 탐색 트리, 균형 탐색 트리
• 외부 탐색
  • 통상적인 방법은 내부탐색임
• 해싱 기법
  • 무엇을 빨리 찾는 기법

탐색 개요

• 주요 용어
  • 키 : 다른 데이터와 구별되는 값
    • 이름은 동명이인이 있기 때문에 키 역할을 못함
    • 주민번호나 학번 같은 것
    • 유일한 값
    • 꼭 하나만 있는 것이 아니라 여러개가 있을 수 있음
  • 화일, 파일:레코드들의 집합
    • 한 학생에 관한 자료 : 레코드
    • 여러개의 정보로 이루어짐. 학번, 이름, 핸드폰 번호 등
  • 필드: 하나의 논리적인 데이터 정보단위
    • 각각의 데이터들을 말함
    • 강지수, 0102037,
  • 탐색 : 키(필드값)가 일치하는 데이터(레코드)를 찾는것
    • 외부 탐색은 데이터가 너무 많아서 하드디스크에 들어있는 것 중 원하는 데이터를 찾는 것
  • 내부 탐색과 외부 탐색이 있음

기본 탐색

• 선형 탐색
  • 순차 비교
  • 처음부터 하나씩 비교
  • 개선점
    • 자주 탐색되는 자료를 속도 증가를 위해서 앞에 배치
    • 비교 회수 갑소
    • 최상의 경우 1번만 비교
    • 최악의 경우 n번 비교
    • 평균은 둘의 평균값

  • 코드

      //처음부터 하나씩 비교. 키와 일치하면 정보를 얻고 일치하지 않으면 next 함 
      class SNode {
      	public:
      		int key_data;
      		char info[128];
      		SNode *next;
      };
            
      SNode *
      Sequential_Search(SNode *Head, int key)
      {
      	SNode *ptr;
            
      	for(ptr = Head; ptr; ptr = ptr->next) //ptr이 null이 아닐 때까지 함 
      			if(ptr->key_data == key) return(ptr);
      	return(ptr); // returns NULL ; 찾지 못함
      }
    

      //배열 이용
      #define TBL_SIZE 120
            
      class SNode {
      	int key_data;
      	char info[128];
      	} DATA[TBL_SIZE];
            
      int 
      Sequential_Search(int key)
      {
      	int i;
      	for(i = 0; i < TBL_SIZE; i++)
      	/* if found, return Table Entry # */
      		if(DATA[i].key_data == key) return(i);
      	return(-1); // 찾지 못함의 의미로 -1 반환
      }
    

• 개선된 선형 탐색
  • 전진 이동법
    • 한번 탐색된 자료는 맨 앞으로 이동
    • 지역성 고려
      • 공간적 지역성
      • 시간적 지역성 고려
  • 전위 이동법
    • 한번 탐색된 자료는 바로 앞 자료와 교환
    • 균등 분포 시 유리
  • k-전진 이동법 (전진, 전위 혼합)
    • 한번 탐색시 k번 앞으로 이동
  • 계수법
    • 탐색 회수를 계수, 내림 차순으로 정렬
    • 매번 정렬하기 힘들고 변수 count를 두어서 호출회수를 비교할 수 있도록 함

이진 탐색

• 적용 대상 : 정렬되어 있는 배열 만!
  • 연결 리스트는 안됨
  • 배열도 정렬되어 있을 때 적용 가능. 제한된 상황에서만 사용가능하지만 성능이 뛰어남
• 논의
  • 정렬이 안된 자료의 이진 탐색?
    • 정렬 후 탐색을 하는 것이 m과 n이 클수록 나음.
    • n : 데이터 수
    • m : 탐색 회수

• 코드

    //배열 사용 
    int  Binary_Search(int key) //key 는 찾으려는 key 
    {
    	int from, to, mid; //to는 테이블의 사이즈 , from은 시작점 
      
    	from = 0; to = TBL_SIZE;
    	while(to >= from)
    	{
    		mid = (from + to) / 2; //중앙값을 구함
    		if(key > DATA[mid].key_data) //만약 키가 데이터의 중앙 값보다 크다면
    			from = mid+1;//from을 0에서 중앙+1로 이동
    		else if(key < DATA[mid].key_data)
    			to = mid-1;
    		else return(mid);//to와 from이 바뀌는 경우에 mid를 반환 
    }
    	return(-1); // 찾지 못함의 의미로 -1 반환
    }
  

탐색 트리

• 이진 탐색 트리
  • 처음에는 몰라도, 데이터가 추가, 삭제가 반복될 시 한쪽으로 치우칠 수 있음
  • 이진 탐색 트리는 위치에 따라 크기 순서를 알 수 있음
  • 왼쪽 서브 트리에는 작은 값, 우측에는 큰 값
  • 자식 노드의 수를 2 이하로 둠
  • log n~ n번 비교
    • 레벨 최소화, 루트 가까이
    • 레벨 수만큼 비교하게 될 수 있기 때문에 레벨을 최소화함
• 균형 이진 트리
  • skew 기울기, 치우침 없이 레벨 수를 최소화 해서 관리하기 위함임
  • AVL, BB
    • 좌우 서브 트리의 깊이의 균형을 지속적으로 유지
    • 탐색 속도의 편차를 일정하게 유지함
  • Splay
    • 자주 탐색되는 것은 루트에 가깝게 함
  • AVL, BB, Splay 트리 구조
    • 자료 삽입 시 회전 기법 이용
    • 약간의 추가 작업으로 지속적인 균형을 유지함
• 추가설명

  • 트리의 모든 노드 탐색, 특정한 값을 찾을 경우

    (중위순회, 후위순회, 전위순회, 등)

  • 이진 탐색 트리의 성질

    (1) 1 또는 2개의 자식 노드

    (2) 왼쪽 서브트리는 작은 값, 오른쪽은 큰 값

  • [알고리즘 4.6] P.133

    • 성능분석 : 탐색 수는 트리의 깊이와 관련
    • 균형 트리 탐색 :

    (1) 자주 접근하는 데이터를 root 가까이

    (2) 균형된 트리 지속적 구성

    • AVL, BB트리, Splay트리 :

    자료의 삽입시 회전 기법 이용

    => 지속적인 균형 실현 (AVL, BB)

    => 탐색된 자료를 루트 가까이로 이동(Splay)

이진 트리 탐색 - 순환 알고리즘

• 실제로 트리 구조 사용
• 순환 알고리즘 사용

class KNode {
	int key_data;
	char info[128];
	KNode *left, *right;
};

KNode *
B_Search(KNode *Node, int key)
{
	if(Node == NULL) return(NULL);
	else if(key < Node->key_data) 
		return(B_Search(Node->left, key));
	else if(key > Node->key_data)
		return(B_Search(Node->right, key));
	else return(Node);
} 

void main()
{
	.... /* 데이타 입력 또는 초기화 */
	entry = B_Search(Root, key); /* 탐색 */
	.... /* 탐색된 데이타 처리 */
}

이진 트리 탐색 - 비순환 알고리즘

• 추천하는 알고리즘

class KNode {
	int key_data;
	char info[128];
	KNode *left, *right;
};

KNode *
B_Search(KNode *Node, int key)
{
	while (Node != NULL)
		if(key < Node->key_data)  //작으면 왼쪽으로 이동
			Node = Node->left;
		else if(key > Node->key_data) //크면 오른쪽으로 이동
			Node = Node->right;
		else return(Node);
	return (NULL); /* Not Found */
} 

void main()
{
	.... /* 데이타 입력 또는 초기화 */
	entry = B_Search(Root, key); /* 탐색 */
	.... /* 탐색된 데이타 처리 */
}

AVL 트리

• 균형 탐색 트리의 한 종류
• 각 노드에 대해, 좌, 우 서브 트리의 깊이(레벨)의 차이가 1이하인 이진 탐색 트리
  • 이게 깨지면 특수한 회전 연산을 적용
    • LL,LR, RR, RL

RR, LL

중간의 것을 뾰족점으로 둠

LR

제일 밑 오른쪽에 있는 것을 맨 위로 이동시키고, 맨 위에 있는 것을 오른쪽으로 이동시킴

RL

제일 밑 왼쪽에 있는 것을 맨위로 이동시키고, 맨위에 있는 것을 왼쪽으로 이동시킴

Splay

• 자주 사용하는 값을 루트 가까이 유지
• 좌우의 균형보다는 한번 탐색된 데이터를 루트로 가지고 옴
• 2가지 회전 연산(Zig, Zag)를 통해서 재구성함
• 포인터 몇개만 바꿔주면 나머지 서브트리들은 건들일 필요 없음

외부 탐색

• 외부 장치가 필요한 대규모 탐색
• m원 탐색 트리
  • 최대 m개의 자식 노드를 허용
• B 트리, B*트리, B+-트리
  • 특정 조건을 만족하는 m원 트리
  • B, B*은 데이터가 모두 노드에 저장되어 있는 형태임
  • B트리보다 강화된 게 B*트리
  • B+트리는 모든 데이터는 단말 노드에 존재하고, 인덱스 부분과 데이터 부분이 분리되어 있음

m원 트리

키가 n개 있으면 포인터가 n+1개 있음.

n+1을 m이라고 생각

해싱기법

• 해싱
  • 키를 테이블 주소로 변환하는 해시함수 사용
    • 데이터를 인덱스로 변환하는 해시함수 사용
    • 데이터가 어느 위치에 있던 상관없음
    • 원칙을 정하는 것
  • 해싱 기법을 위한 한가지 가정
    • 데이터를 무조건 저장하는 것이 아니라, 저장과 탐색을 통일한 원칙으로 함
  • 비교적 고정된 탐색 시간
  • 삽입과 삭제 시 용이
  • 문제점 : 충돌 발생, 기억장소 낭비 가능

해싱 함수

• 해시 함수의 성능 조건
  • 계산이 빠르고 간단
  • 테이블 크기 내 고른 분포
  • 충돌 회수 최소화
    • 해결방안 있음
  • 소수 활용
• 종류
  • 나눗셈법 가장 많이 사용
    • 나머지를 키값으로 사용
    • 경험적으로 N은 테이블 크기보다 약간 적은 소수를 사용
    • N = 나누는 수
  • 중간 제곱법
    • 키의 값을 제곱한 다음 적당한 중간 부분을 발췌하여 사용
  • 폴딩법
    • 키값을 2진수로 생각하여 두 부분으로 나눈 후, 두부분을 비트 연산함
  • 해시 함수
    • 진법을 변환하여 나온 수를 적절히 활용
    • 2진법→4진법 등 변환한다는 말임
  • 자리수 분석법
    • 키 값의 자리수 중 중복이 제일 적은 자리수를 선택하여 사용
    • 중복되는 수를 모두 다 제거
  • 등등. 어떤게 좋은지는 모름

충돌 해결 방안- 충돌은 반드시 일어남

• 충돌 해결
  • 선형 검색법 - 쓰면안됨. 심각한 문제 있음
    • 매우 간단
    • 동일 집단의 키가 뭉치는 경향, 탐색 시간 길어질 가능성 증가
    • 삭제시 문제가 발생할 수 있음
      • 삭제하면 빈칸이니까 그 아래 데이터를 못찾을 수 있음
    • 아직 없는 데이터를 찾는 경우 시간이 오래걸림
  • 2차 검색법
    • 뭉치는 경향을 방지, 단 모든 버킷이 검색안될 수 있음
    • 2의 배수로 뛰어서 저장하는 등, 중복시 몰려서 저장안함
  • 해시 체이닝법 0 완벽한 방법, 연결리스트 사용
    • 빠른 해결, 그러나 부가적인 기억 장소 필요
    • 새로운 데이터를 앞쪽에 위치하게 함

5장. 스트링매칭 (문자열 탐색)

• Brute-Force
• KMP
• Boyer-Moore
• Rabin-Karp

기법소개

• Brute-Force
  • 차례로 문자열 비교
  • 복잡도 O(M*N)
  • M : 찾으려고 하는 문자열 길이
  • N : 문제 크기, 데이터 개수
• KMP
  • 패턴의 반복을 응용
  • 복잡도 : O(M+N)
  • 개선된 KMP 알고리즘이 있음
• Boyer-Moore 알고리즘
  • 아래 두가지를 모두 적용하고 우수한 것을 선택함
    • 오른쪽에서 왼쪽으로 비교
    • 불일치 문자의 존재 여부 활용
    • O(N+M) vs O(N/M) 운이 좋은 경우가 후자임
• Rabin-Karp
  • 해싱 기법 활용
    • 해시값이 일치한 경우, 문자열 실제 비교 필요
    • 최악(N*M) vs 실제O(N+M)

Brute-Force 기법

• 전체 문장에서 P 문자열과 일치하는 부분을 찾기
• 함수 strcmp(A,p,M)등을 이용
  • A : 원본
  • M : P의 길이
  • P : 찾을 문자열
• 비교 실패시 다음 M개의 문자열과 비교-반복
• 동일한 조건에서 문자 단위로 설명(한글자 단위로 설명)
  • strcmp 사용안하는경우
    • 두문자를 차례대로 비교 후, 두 문자가 일치하면 다음 문자 비교
      • i++, j++
    • 실패하면, 다음 비교할 두 문자는?
      • i = i-j+1
        • i 는 원본 데이터에서의 인덱스
        • j 는 비교할 데이터의 인덱스
      • j = 0

• 코드 1

    //문장/파일 중에서 원하는 문자열 p를 찾은 다음,
    // 찾은 문자열의 시작 위치를 반환. 
    //p: 찾고자 하는 문자열/패턴, 
    //a: 주어진 문장/파일/문자열 
      
    int 
    BruteForce_Search1(char *p, char *a)
    {int i, j, M, N;
      
    M = strlen(p); //strlen은 글자수임 
    N = strlen(a);
    for(i = 0; i < N-M+1; i++)
    if(!strncmp(a+i, p, M)) return(a+i); /* 일치 */
    return(N); /* or return (-1), 불일치 */
    }
      
    //=> O(MN), 최악임 
  

• 코드2 - 문자 단위

    int BruteForce_Search2(char *p, char *a) /* 문자 단위 */
    {
    	int i, j, M, N;
    	M = strlen(p); //찾고자하는 문자열의 길이
    	N = strlen(a); //원본 문자열의 길이 
    	i = j = 0;
    	while(j < M && i < N)
    		if(a[i] != p[j])
    		{/* 다음 비교할 문자열의 시작 위치 계산 */
    			i = i - j + 1; 
    			j = 0;
    		}
    		else
    		{i++; j++; /* 다음 문자 비교 */
    			}
    		if(j == M) return(i-M); /* 일치 문자열의 시작 위치 */
    		else return(N); /* 또는 return (-1),  불일치 */
    }
      
    //=> O(MN)
  

KMP 알고리즘

• 전체 문장에서 p 문자열과 일치하는 부분을 찾기
• 문자 단위로 비교
• 특징 : p의 특성에 대해 약간의 사전 조사 실시 후, 탐색
  • p의 각 문자에 대해, 그 문자의 next 문자를 미리 추출
  • 각 문자의 next 값을 이용하여 검색 속도를 향상함
  • next 배열을 미리 탐색전에 구해놓고, 검색을 빨리하자는 취지
• 중요 : next 구하는 방법과 활용 방법 이해
  • 개념적인 이해, 예를 통한 이해, 알고리즘 이해
  • 일치하면 i++, j++
  • 불일치하면 다음 비교 대상은 A[i]와 p[0]
  • next[0]=-1임
• a[i]하고 p[i] 비교 후 틀리면 a[i]와 p[next[j]]를 비교함

• 코드

    int KMP_Search(char *p, char *a)
    {
    	int i, j, M, N;
      
    	M = strlen(p); N = strlen(a);
    	InitNext(p); /* next[] 초기화 */
    	for(i = 0, j = 0; j < M && i < N; i++, j++)
    		while(j >= 0 && a[i] != p[j]) //next[0]=-1로 설정하기 때문
    			j = next[j];  /* cf. i=i-j+1; j=0; */ 
    	if(j == M) return(i-M); /* 일치 문자열 시작 위치 */
    	else return(N); /* return (-1), 불일치 */
    }
      
    InitNext(char *p) 
    {
    	int i, j, M;
      
    	M = strlen(p);
    	next[0] = -1; /* 첫 문자 불일치시 한칸 이동 */
    	for(i = 0,j = -1; i < M; i++, j++, next[i] = j)
    		while(j >= 0 && p[i] != p[j])
    			j = next[j];
    }
  

개선된 KMP 알고리즘

• KMP 기법에서 추가적인 향상 기법 적용
• p의 어떤 문자의 next 문자가 동일한 문자인 경우, 단계를 뛰어넘을 수 있음

• 코드

    int KMP_Search2(char *p, char *a)
    {
    	int i, j, M, N;
      
    	M = strlen(p); N = strlen(a);
    	InitNext2(p); /* next[] 초기화 */
    	for(i = 0, j = 0; j < M && i < N; i++, j++)
    		while(j >= 0 && a[i] != p[j])
    			j = next[j];
    	if(j == M) return(i-M); /* 일치 문자열 시작 위치 */
    	else return(N); /* return (-1), 불일치 */
    }
      
    InitNext2(char *p)
    {
    	int i, j, M;
      
    	M = strlen(p);
    	next[0] = -1; /* 첫 문자 불일치시 한칸 이동 */
      for(i = 0, j = -1; i < M; i++, j++,
    		next[i] = (p[i]==p[j]) ? next[j] : j)//만약 두개가 같으면 next[j]를 넣고 아니면 j를 넣어
    			while(j >= 0 && p[i] != p[j])
    				j = next[j];
    }
  

• FSM
  • 유한상태의 대기임.
  • 시스템 동작시 어떤 상태에 있는지를 도표에 나타냄
  • 화살표 꼭 써야함

Boyer-Moore 알고리즘

• 전체 문장에서 p 문자열과 일치하는 부분 찾기
• 문자 단위로 비교 + 오른쪽 부터 비교
• 특징
  • 오른쪽부터 차례대로 비교
  • 개선된 KMB 개념 이용
    • 이건 사용안함
  • 불일치 문자 이용
• 일치하면, i—, j++
• 불일치하면,
  • i = i+(M-j)
  • j = M-k
    • 오른쪽으로 j를 k칸 이동함.
    • k는 skip[j]에 해당하는 값
• skip[j] 에 값을 넣음

• 코드

    int BM_Search(char *p, char *a)
    {
    	int i, j, t, M, N;
      
    	M = strlen(p), N = strlen(a);
    	InitSkip(p); /* skip[] 초기화 */
      
    	for(i = j = M - 1; j >= 0; i--, j--)
    		while (a[i] != p[j])
    			{
    				t = skip[index(a[i])]; 
    				i = i + max(M-j, t); /* 둘중 큰것 선택 */
    				if(i >= N) return(N); /* 매칭안됨 */
    					j = M - 1;  /* p의 마지막 문자 위치 */
    				}
    	return(i+1); /* 일치된 문자열의 시작 위치 */
    }
    InitSkip(p) {
    	for(각 알파벳 문자 k에 대해)  skip[k] = M; // 패턴 내에 존재하지 않는 문자에 대해 초기화
    	     //보통은 (int k=0; k < 26; k++) skip[k] = M;
    	// p에 포함된 각 문자에 대해,
    	for(int j = 0; j < M; j++) skip[index(p[j])] = M-j-1; 
    }
    index(char c) {
    	if(c가 소문자로 변경) return (c-'a');
    	else if(c가 대문자이면) return(c-'A');
    }
  

Rabin-Carp 알고리즘

• 해싱 기법 사용
• 동일한 키는 해시값도 당연히 같음
• 해시값이 같다고 해서 동일한 키는 아님
• 두 키의 해시값이 다르면, 두 키는 다름
• 먼저 두키의 해시값을 비교하여 일치하는지 검사
• 해시값이 일치하면 자세히 두 문자열을 비교
• 불일치하면 건너뜀
• 최악 O(N*M), 실제 O(N+M)

• 코드

    #define q  33554393 //큰 소수 사용 
    #define d  32  /* 상이한 숫자 또는 문자의 개수 */ //숫자면 10 가능 
      
    int RK_Search(char *p, char *a)
    {
    	int i, dM;
    	int M = strlen(p), N = strlen(a); 
    	int h1 = 0;  /* p의 해시값 */
    	int h2 = 0;  /* 대상 스트링의 해시값 */
      	
    	dM = 1; 
    	for(i = 1; i < M; i++) /* dM = d(M-1) 계산 */
    		dM = (d * dM) % q; //해시값 구하기 
      	
    	for(i = 0; i < M; i++)
    	{/* p의 해시값 및 첫 문자열의 해시값 계산 */
    		h1 = (h1 * d + index(p[i])) % q; 
    		h2 = (h2 * d + index(a[i])) % q;
    	}
    	for(i = 0; i < N-M && h1 != h2; i++) // 해시값이 같은 것을 찾을 때까지 문자열 비교 
    	{/* 다음 문자열에 대한 해시값 계산 */
    		h2 = (h2 + d * q - index(a[i]) * dM) % q; //음수를 나누느 상황을 대비해서 큰 수를 더함
    // 첫번째 문자열에 대한 것을 빼줌. 즉 왼쪽으로 이동
    		h2 = (h2 * d + index(a[i+M])) % q;
    //남아있는 것을 더해주는 파트 
    }
    	return(i);
    }
      
    //(Note) (a + b) % q = ((a % q) + (b % q)) % q 
      a % q = (k * q + a) % q
  

비교

1. Brute-Force
   • a[i] != p[j]이면, i = i – j + 1, j = 0;
   • a[i] == p[j]이면, i++, j++;
2. KMP
   • a[i] != p[j]이면, i(불변*), j = next[j];
   • a[i] == p[j]이면, i++, j++;
3. 역방향 Brute-Force
   • a[i] != p[j]이면, i = i + (M-j), j = M-1;
   • a[i] == p[j]이면, i—, j—;
4. Boyer-Moore (역방향 비교)
   • a[i] != p[j]이면, i = i + max(M-j,skip[index(a[i])]), j = M-1;
   • a[i] == p[j]이면, i—, j—;
5. Rabin-Karp
   • 패턴과 본문 문자열의 해시값이 일치하면, 문자단위 비교후 판단
   • 해시값이 다르면, 다음 본문 문자열과 패턴 비교

06. 그래프

• 용어정의 및 표현법
• 그래프의 순회
  • BFS, DFS,
• 신장 트리
  • DFS, BFS의 신장트리, 최소비용 신장 트리
• 최단경로
• 연결성
• 위상 정렬
• 임계 경로

용어 정의

• 정점 = 노드 = V
• 간선 = 엣지, 아크 = E
• 그래프 G = {V,E} , VE 는 집합
• 주요 용어
  • 다중그래프
    • 두개의 노드가 있는데, 엣지가 2개인 경우
    • 거의 통상적으로 그래프라고 생각안함
  • 방향그래프
    • 간선에 방향이 있음
  • 무방향 그래프
    • 간선에 방향이 없음
    • 대칭행렬을 보임 모든 i, j에 대해
      • i,j = j, i
      • 메모리가 중요할 때는 반만 저장하기도 함
  • 가중 그래프
    • 엣지에 가중치가 있음
    • 즉 간선에 가중치가 있음
  • 차수
    • 노드에 연결된 간선의 개수
  • 인접
    • 엣지로 연결된 두개의 노드를 인접해 있다고 함
  • 경로
    • 선택된 엣지의 집합
  • 사이클
    • 한 노드에 출발해서 자기자신으로 다시 돌아올 수 있는 경우
    • 트리 구조는 사이클이 없고, 그래프는 사이클이 있을 수 있음
  • 연결성
  • 가중치

그래프 표현법

• 인접 행렬
• 인접 리스트
• 인접 다중 리스트

그래프의 순회

• 깊이 우선 탐색 DFS
  • 순환 함수 사용
  • 스택 사용
  • 백트랙킹 사용할 수 있음

  • 순환 알고리즘 - DFS 코드

      #define MAX 50
      class Node {
        public:
      		int vertex;
      		Node *link;
      } *graph[MAX], *w;
      int visited[MAX];
            
      main()
      {
      	int i, s;
      	for(i = 0; i < MAX; i++)
      		visited[i] = FALSE;
      	s = 시작 노드; // s = 0;
      	DFS(s);
      }
            
      void DFS(int v)
      {
      	visited[v] = TRUE;
      	print_node(v);
      	for(w = graph[v]; w; w = w->link)
      		if(!visited[w->vertex])
      			DFS(w->vertex);
      }
    

  • 새로운 방법 - DFS 코드

      #define MAX 50
      class Node {
         public:
      	int vertex;
      	Node *link;
      } *graph[MAX], *w;
      int visited[MAX];
            
      main()
      {
      	int i, s;
      	for(i = 0; i < MAX; i++)
      		visited[i] = FALSE;
      	s = 시작 노드; // s = 0;
      	NEW_DFS(s);
      }
            
      void NEW_DFS(int v)
      {
      	if(visited[v]) return;
      	else visited[v] = TRUE;
      	print_node(v);
      	for(w = graph[v]; w; w = w->link)
      		if(!visited[w->vertex])
      			NEW_DFS(w->vertex);
      }
    

• 너비 우선 탐색 BFS
  • 순환 함수 사용 불가
  • 큐 사용

  • 스택이용 코드

      void
      DFS(int v)
      {
      	push(v);
      	while(!stack_empty())
      {
      	v = pop();
      	visited[v] = TRUE;
      	print_node(v);
      	for(w = graph[v]; w; w = w->link)
      		if(!visited[w->vertex]) 
      			push(w->vertex);
      }
      }
    

  • 수정된 방법 코드 스택

      void NEW_DFS(int v)
      {
      push(v);
      	while(!stack_empty())
      {
      	//if(VisitAllNodes()) return;
      	v = pop(); //방문했다!
      	if(visited[v]) continue;
      	else visited[v] = TRUE;
      	print_node(v);
      	for(w = graph[v]; w; w = w->link) //인접노드들에 대해서 
      		if(!visited[w->vertex]) //방문한 적 없다면 
      			push(w->vertex);
      }
      }
    

  • 큐이용 코드

      void BFS(int v) 
      {
      	visited[v] = TRUE;
      	print_node(v); 
      	add_queue(v);
      	while(!queue_empty())
      	{
      		v = delete_queue();
      		for(w = graph[v]; w; w = w->link)
      		if(!visited[w->vertex])
      			{
      				print_node(w->vertex);
      				visited[w->vertex] = TRUE;
      				add_queue(w->vertex);
      			}
      		}
      }
    

  • 수정된 방법 코드 큐

      void NEW_BFS(int v)    
      {
      	add_queue(v);
      	while(!queue_empty())
      {
      	//if(VisitAllNodes()) return;
      	v = delete_queue();
      	if(visited[v]) continue;
      	else visited[v] = TRUE;
      	print_node(v);
      	for(w = graph[v]; w; w = w->link)
      		if(!visited[w->vertex])
      			add_queue(w->vertex); //얘를 큐에 넣음
      	}
      }
    

신장 트리

• 그래프 G의 모든 노드와 일부 간선을 포함하는 트리로서 다음의 조건을 만족
  • G = {V,E}
  • ST= {V, E`}
    • ST = 신장 트리, spanning Tree
  • 노드수가 n개일 때 간선의 수는 n-1
  • 모든 노드가 연결됨
  • 두 노드사이에는 단일 경로 존재, 사이클 없음
• 최소 비용신장트리
  • 실생활에 적용가능
  • prim
    • 무리 중에 자기가 선택할 수 있는 가장 적은 비용을 선택함
  • kruskal
    • 가장 작은 가중치부터 선택해 나가자
    • 사이클이 생기면 다른거 선택해야해
  • sollin

최단거리, 경로 찾기 알고리즘

• 종류
  • 단일 출발점의 경우에 대한 최단 경로
  • 모든 쌍에 대한 최단 경로
• 출발점과 도착점이 결정된 경우
  • Cost(i,j) : 인접 행렬 원소 Aij
  • Dist(w) : 출발점에서 w까지의 최단 거리
  • 기본 발상
    • 출발점을 s, 도착점을 d라고 할 때
      • Dist(d) = min{Cost(s, d) , Dist(w) + cost(w, d)}
  • 수정
    • 집합 S : 최단 경로가 이미 발견된 노드 집합
      • 위의 발상은 최단 경로를 모르고 있는 애들이 있을 수 있기 때문
    • Dist(w)
      • S 내의 노드만을 통한 최단 거리의 비용

  • 코드1

      Shortest_Path (v) /* 출발점 v */
      {
      	// DIST 초기화
      	for(i = 0; i < n; i++)
      	{
      		S[i] = NOT_FOUND;
      		DIST[i] = COST[v][i];
      	}
      	S[v] = FOUND;
      	DIST[v] = 0;
      	for(i = 0; i < n-2; i++)
      	{
      		u = choose(DIST, n, S);
      		S[u] = FOUND;
      		for(w = 0; w < n; w++)
      			if(S[w] == NOT_FOUND)
      				DIST[w]=min(DIST[w],
      			   DIST[u]+COST[u][w]);
      	}
      }
            
      //☞ 복잡도 :  O(n2)
    

  • 코드 2 (코드1 과 내용은 같은데, p[w] = u;를 추가하기 위해서 변형

      Shortest_Path2 (v) /* 출발점 v */
      {
      	// DIST 초기화
      	for(i = 0; i < n; i++)
      	{
      		S[i] = NOT_FOUND;
      		DIST[i] = COST[v][i];
      		P[i] = v; 
      	}
      	S[v] = FOUND;
      	DIST[v] = 0;
      	for(i = 0; i < n-2; i++)
      	{
      		u = choose(DIST, n, S);
      		S[u] = FOUND;
      		for(w = 0; w < n; w++)
      			if(S[w] == NOT_FOUND)
      				if(DIST[w] > DIST[u]+COST[u][w])
      					{ 
      						DIST[w] = DIST[u]+COST[u][w];
      						P[w] = u;
      					}
      			}
      }
    

위상 정렬

• 위상 순서라고도함
• 사이클이 없는 방향 그래프에서 노드의 순서를 정하는 문제

임계 경로

• 임계경로: 가장 긴 경로
  • 전체 일정을 단축하려면 임계 경로가 단축되어야 함
  • 임계경로는 EST = LST 인 노드들로 구성됨