은둔형 공학자

1. 내부 정렬 (internal sort) 

 데이터를 키의 값에 따라 오름차순 또는 내림차순으로 일정하게 배열하는 것  

 데이터의 개수가 비교적 적어 컴퓨터의 주기억장치만으로 실행되는 경우  

 삽입 정렬(insert sort) 

 레코드 Ri의 정렬 키를 Ki라 하고 새로 삽입될 레코드 R의 키를 K라 할 때 이미 정렬되어 있는 일련의 i개 레코드 R1, R2 …, R(K1 < K2 < … < Ki )에 레코드 R이 삽입되어 크기가 i+1개 이고 역시 순서대로 정렬된다. 만약 정렬되고자 하는 파일의 레코드 수가 n개라면 한 개의 레코드 씩 차례로 삽입하여 n-1개를 삽입했을 때 완료되는 정렬 방식 

 장점 : 간단하고 안정적이다. 

 단점 : 정렬 횟수가 많다(n-1회의 정렬 횟수). 정렬 속도가 늦다. 

 삽입 정렬(insert sort) 

 정수형 데이터에 대한 삽입 정렬 알고리즘 

 Void insertion( int R[], int n ) 

{ 

        int I, j, v; 

        for(i=1; i<n; i++) { 

                v = R[i]; 

                j = i; 

                while ( R[i-j] > v ) 

                        R[j] = R[i–j]; j = j-1 

                        if ( i <= 0 ) break; 

                } 

                R[j] = v; 

        } 

} 

 레코드 수 n= 5 이고 초기 입력 데이터가 8, 3, 4, 9, 7일 때 

삽입 정렬 방식으로 순서 배열 과정을 나타내시오. 

 초기상태 : 8 3 4 9 7 

1  단  계 : 8 3 4 9 7 

2  단  계 : 8 3 4 9 7 

3  단  계 : 8 3 4 9 7 

4  단  계 : 8 3 4 9 7 

 쉘 정렬 (Shell sort) 

 삽입 정렬의 개념을 확대하여 일반화시킨 정렬 방법 

 초기 입력 파일을 어떤 매개 변수의 값으로 여러 개의 서브 파일을 구성하여 가면서, 각 서브 파일을 삽입 정렬 방식으로 순서  배열하는 과정을 반복하는 정렬 방식  

 셀 정렬 알고리즘 

 선택 정렬(selection sort) 

 n개의 레코드 중에서 첫 번째 값을 키로 하여 남은 데이터 중에서 최소값을 선택하여 비교한 후, 선택된 값이 키 값보다 작으면 서로 교환하고, 그렇지 않으면 다음 값을 키로 하여 n-1만큼 반복 수행하는 정렬 

 선택 정렬 알고리즘 

 ① n = 레코드의 수 

 ② 처음 값을 키로 지정한다. 

 ③ 처음부터 끝까지 키 값과 비교하여 키보다 작으면 서로 교환한다. 

 ④ 키 = 키 + 1 

 ⑤ n번 비교 되었으면 종료, 그렇지 않으면 ③을 수행한다. 

 선택 정렬 수행 예제 

n = 5 이고 초기 상태의 데이터가 8 3 4 9 7 일 때 선택 정렬을 수행하라. 

 초기상태 : 8 3 4 9 7 

1  단  계 : (3)(8 4 9 7) 

2  단  계 : (3 4)(8 9 7) 

3  단  계 : (3 4 7)( 8 9) 

4  단  계 : (3 4 7 8 9) 

 버블 정렬(bubble sort) 

 주어진 초기 입력 파일에서 인접한 레코드 쌍의 두 키를 비교하여, 그 키의 크기에 따라 레코드의 위치를 서로 교환하는 작업을 배열의 마지막까지 반복 수행하는 정렬 방법 

 플래그(flag)가 없는 버블 정렬 

 정의 : 버블 정렬의 일반적인 형태로 레코드 간의 키 값을 비교해서 위치를 서로 교환하면서 정렬하는 것이다.  

 플래그가 없는 버블 정렬 알고리즘 

① 인접한 두 개의 키를 비교한다. 

② 앞의 키가 뒤의 키 값보다 크면 서로 교환하고, 아니면 그대로 수행한다. 

③ 한 레코드의 끝까지 비교 정렬한다. 

④ (n - 1)번 반복 수행한다. 

 플래그(flag)가 없는 버블 정렬 

 플래그가 없는 버블 정렬 예제 

n = 5 이고 초기 상태의 데이터가 8 3 4 9 7 일 때 버블 정렬을 수행하라. 

 초기상태 : 8 3 4 9 7 

 플래그가 있는 버블 정렬 

 정의 

버블 정렬로 정렬하는데 플래그를 사용함으로써 비교 횟수를 상당히 줄일 수 있으므로 인하여 정렬로 빠르게 할 수 있다.  

 플래그가 있는 버블 정렬 알고리즘 

① 플래그를 세트(set)시킨다. 

② 인접한 두 개의 키를 비교한다. 

③ 앞의 키가 뒤의 키 값보다 크면 서로 교환하고 플래그를 리셋(reset) 시킨다. 

④ 플래그가 원래의 값이면 종료, 아니면 ①로 간다. 

n = 5 이고 초기 상태의 데이터가 8 3 4 9 7 일 때 버블 정렬을 수행하라. 

 초기상태 : 8 3 4 9 7 (flag = 1) 

1  단  계 : 3 4 8 7 9 (flag = 0)으로 변화 

                                (flag = 1로 set) 

2  단  계 : 3 4 7 8 9 (flag = 0)으로 변화 

                                (flag = 1로 set) 

3  단  계 : 3 4 7 8 9 (flag = 1이 그대로 이므로, 수행중지) 

 퀵 정렬(quick sort) 

 정의 

 C. A. Hore가 고안한 정렬로 주어진 파일에서 어떤 특정한 값(제어 키)을 주어 왼쪽에는 제어 키 값보다 작은 레코드를 배열하고, 오른쪽에는 제어 키보다 큰 값을 놓이게 하여, 논리적으로 2개의 서브 파일로 재배열하고 각각의 서브 파일에서 위의 과정을 반복하는 정렬 방법 

 퀵 정렬 알고리즘 

 ① 주어진 파일의 중간 위치를 기준으로, 그 값보다  큰 값들은 우측, 작은 값은 좌측에 교환하여 서브 파일을 구성한다 

 ② 각 서브 파일에서 좌측의 서브 파일부터 다시 ①과 같은 요령으로 서브 파일을 구성한다  

 ③ 위의 ①과 ②의 과정을 오른쪽 서브 파일에 이르기까지 반복한다. 

 퀵 정렬 실행 예제 

n = 9 이고 초기 상태의 데이터가 15, 25, 45, 65, 22, 33, 9, 7, 55 일 때 퀵 정렬을 수행하라.

 2-원 병합 정렬 (2-way merge sort) 

 정의 

 정렬된 2개의 파일을 혼합하여 완전히 정렬된 하나의 파일로 합하는 정렬 방식 

 2-way 병합 정렬 알고리즘 

 2-way 병합 정렬 수행 예제 

초기 상태 : 6 9 2 12 8 34 23 33 56 17 56 32 

 2-way 병합 정렬 실행 시간 

 기억 장소 사용 공간 : S = 2n 

 단계(pass) 수 : log2n 

 실행 시간 : O(nlog2n) 

 기수 정렬 (radix sort, burket sort, digital sort) 

 정의 

 스택을 이용하여 자리수의 숫자에 따라 다중키(multi key)에 대한 정렬로서, 키 값을 비교하는 것이 아니라, 키를 구성하는 자리수를 분석하여 같은 것끼리 같은 장소에 분배하여 정렬 

 기수 정렬 알고리즘 

 ① LSB(Least Significant Bit)를 검토하여 적절한 큐에 저장한다. 

 ② 0에서 9번 큐의 내용을 순서대로 배열하여 리스트로 재구성 한다. 

 ③ 계속하여 다음 디지트를 대상으로 ①, ② 과정을 반복하여, 모든 자리수가 완료될 때까지 실행한다. 

 힙 정렬 (heap sort) 

 정의 

 주어진 파일의 레코드를 힙(heap)이라는 자료 구조를 이용하여 정렬하는 방법 

  힙(heap) 구조는 완전 이진 트리(complete binary tree)로서 각 노드의 키 값이 자식 노드들의 키 값보다 작지 않은 트리로서, 힙 루트(heap root)는 트리 중 가장 큰 값을 나타낸다. 

장점 : 삽입, 삭제가 용이하다. 

단점 : 이동할 때 힘 구조가 재구성되어야 한다. 

 힙 구조 알고리즘 

 ① 주어진 데이터를 이진 트리로 구성한다. 

 ② 제일 늦게 구성된 트리를 선택한다. 

 ③ 부모 노드와 자식 노드 중 가장 큰 값을 선택한다. 

 ④ 부모 노드와 자식 노드 중 가장 큰 값을 비교한다. 

if 부모 노드 > 자식 노드 중 큰 값 then 그대로 둔다. 

if 부모 노드 < 자식 노드 중 큰 값 then 서로 위치를 교환한다. 

 ⑤ ②, ③, ④의 과정을 반복 수행한다. 

 힙 정렬 실행 알고리즘 

 ① 근 노드의 값을 배열의 맨 마지막에 위치시킨다. 

 ② 빈 근 노드의 자리에는 자식 노드 중 가장 큰 값을 위치시킨다. 

 ③ 빈 자식 노드의 자리에는 서브 트리의 자식 노드 중 가장 큰 값을 위치시킨다. 

 ④ 맨 마지막 노드부터 차례로 없어진다. 

 ⑤ ①∼④의 과정을 반복 수행한다. 

1. 정렬의 개념 

 정렬이란? 

 일련의 자료들을 필요에 따라 자료 중에 포함된 몇 가지 항목을 우선 순서대로 지정하면 그 순서에 따라 모든 자료를 배열하는 방법 

 각 레코드의 특정한 항목을 정렬키(key)로 정하고, 키 값에 따라 오름차순, 내림차순으로 파일의 레코드를 재배열하는 것 

 정렬 장소에 따른 구분 

 내부 정렬(internal sort) 

 파일의 크기, 처리해야 할 자료의 양이 적을 경우 자료 이동 속도가 빠른 주 기억장치 내에 로드하여 재배열을 완료시키는 것 

 외부 정렬(external sort) 

 정렬하는 파일의 크기가 주기억 장치의 크기만으로 감당하기 어려울 때 파일 전체를 기억 장소에 로드할 수 없기 때문에 보조 기억 장치(auxiliary memory)를 이용하여 정렬하는 것 

 처리 순서에 따른 구분 

 오름차순 정렬(ascending sort)  

 지정된 정렬키를 작은 것에서부터 큰 것 순서로 정렬 하는 것 

 사전식 정렬 방식 

 내림차순 정렬(descending sort) 

 지정된 정렬키를 큰 것에서부터 작은 순서로 정렬하는 것 

 정렬 방식에 따른 구분(정렬 알고리즘에 따른 구분 방법) 

 비교식 정렬(comparative sorting) 

 비교하고자 하는 각 레코드의 키 값들을 한번에 두 개씩 비교, 교환하여 정렬하는 방법   

예: 

insertion sort, bubble sort, shell sort, quick sort,  2-way, merge sort, heap sort 등 

 분산식 정렬(distributive sorting) 

 레코드의 키 값을 기준으로 전체 레코드 집합을 다수의 부분  집합으로 분해하는데, 한 부분 집합에 속한 키값은 다른 부분 집합에 속한 레코드의 키값과 다르게 만든다. 즉 내용들을 한 비트씩 검토함으로써 정렬하는 방법의 키값과 다르게 만든다. 즉 내용들을 한 비트씩 검토함으로써 정렬하는 방법 

radix sort, radix exchange sort(=binary sort)등 

 주소 계산 정렬(address calculation sort) 

비교하고자 하는 키 값을 주소로 변환하여 정렬하는 방식 

 정렬 방식분류 

 삽입법 : insertion sort, shell sort 

 교환법 : bubble sort, quick sort, selection sort 

 선택법 : heap sort 

 병합법 : 2-way merge sort 

 분배법 : radix short, radix exchange sort 

 정렬 알고리즘을 선택할 때 고려해야 할 사항 

 사용하는 컴퓨터의 특성 

 정렬할 데이터의 양 

 초기 데이터의 배열 상태 

 키 값들의 분포 상태  

 소요 공간 및 작업 시간  

2. 외부 정렬(external sort) 

 정렬할 데이터의 양이 많아 주 기억 장치에서 한번의  

내부 정렬로 수행할 수 없는 경우, 보조기억장치로부터  

주기억장치로 처리할 수 있는 양의 자료를 옮겨서  

이를 병합, 정렬하는 방식 

 런의 수가 m 개인 병합 트리 

 다단계 병합 정렬(polyphase merge sort) 

 모든 파일을 동시에 병합 작업에 이용하며 파일의 수를 n개라 가정할 때, 피보나치 수열(fibonacci sequence)을 이용하여 모든 병합 단계에서 n-1 개의 파일을 항상 사용하여 n-1원 병합 정렬 반복 수행한다.  

 F0 = 1, F1 = 1 일 때 피보나치 수열 : Fi = Fi-1 + Fi-2  (i = 1, 2, …, n)  

 다단계 병합 정렬 알고리즘 

 하나의 파일에 정렬되지 않은 초기 원시 파일을 저장한 다음 나머지 (n-1)개의 파일에 피보나치 수열에 적합한 개수의 서브 파일을 분배한다. 

 분배된 (n-1)개의 파일 간에 (n-1)원 병합 정렬을 진행하다가 파일들 중에서, 특정 파일이 공백 파일이 되면 병합을 잠시 중지하고, 나머지 (n-1)개의 파일 간에 (n-1)원 병합 정렬을 다시 수행한다. 이와 같은 과정을 하나의 정렬된 파일이 될 때까지 반복 수행한다. 

 다단계 병합 정렬의 예  

 초기 자료로 정렬되지 않은 데이터가 9개 있을 때 이들을 다단계 병합으로 정렬하는 과정을 살펴보면 다음과 같다. 단, 테이프의 개수는 4개 이다. 

 균형 병합 정렬(balanced merge sort) 

 주어진 입력 파일을 동일한 크기의 서브 파일들로 분배하여, 반복적인 병합을 수행시켜, 하나의 정렬된 파일로 만든다. 이와 같이 동일한 크기의 서브 파일들로 분배하여 병합한다. 

 입력 파일을 6개의 서브 파일로 분할한 후,  4개의 테이프를 이용하여 균형 정렬하는 과정을 살펴보자. 

 ① 초기 파일을 여러 개의 서브 파일로 나누고 그 서브 파일을 내부 정렬하여 3개씩 보관한다. (T개의 테이프를 사용할 때 T/2개의 테이프에 똑같은 수의 서브 파일로 분배한다.) 

 ② 파일3과 파일4의 서브 파일을 병합하여 파일1과 파일2에 수록한다. 

 ③ 반복해서 파일1, 파일2의 서브 파일을 병합하여 파일3, 파일4에 수록한다. 

 ④ ②, ③ 작업을 반복하여, 하나의 정렬된 파일이 될 때까지 반복한다. 

 교대식 병합 정렬(oscillaring sort merge) 

 하나의 테이프를 제외한 모든 테이프에 한 개씩의 자료를 저장하여 비어있는 테이프에 병합하는 방식이다.  

 다음 자료는 테이프에 저장하여 병합 

 교대식 병합 정렬 알고리즘 

교대식 병합 정렬에서 k 개의 테이프 장치를 사용하여 정렬을 수행하는 경우에 대해 살펴보자. 

 ① 입력용 원시 파일을 저장하는 하나의 테이프와 병합된 서브 파일들을 저장할 출력용 공백 테이프를 제외한 (k-2)개의 테이프에 순방향으로 이동하면서 한 개씩의 서브 파일을 분배한다. 

 ② 분배된 (k-2)개의 테이프들을 역방향으로 이동하면서 출력용 공백 테이프에 서브 파일들을 (k-2)원 병합 정렬하여 저장한다. 

 ③ (k-2)개의 테이프를 순방향으로 이동하면서 한 개씩 서브 파일을 분배한 후 역방향에 의해 병합하므로, 새로운 공백 테이프들이 생긴다. 

 ④ 공백 테이프들 중에서 하나를, 출력용 공백 테이프로 선택하여 나머지 테이프에 한 개씩 서브 파일을 분배하, 병합하는 과정을 입력용 서브 파일들이 모두 분배되어 병합될 때까지 반복 수행한다. 

 계단식 병합 정렬 (cascade merge sort) 

 기본적으로 균형 병합과 유사하다. 이 방법은 모든 테이프를 동시에 작동하는데, 초기 자료 파일을 하나의 테이프를 제외한 나머지 테이프에 분배한 다음 이들의 병합을 반복한다. 테이프들 중에서 한 개의 테이프의 병합이 끝나면 병합 작업은 종료된다.  

 계단식 병합 정렬 알고리즘 

 ① 이용할 수 있는 파일의 수를 k 개라 가정하면, 하나의 파일에 정렬되지 않은 초기 원시 파일을 저장한 후 나머지 (k-1) 개의 파일에 내부 정렬을 수행하여 서브 파일들을 균등 분배한다. 

 ② 균등 분배된 (k-1)개의 파일 간에 (k-1)원 병합 정렬을 반복 수행하는데, 파일들 중에서 특정 파일이 공백 파일이 되면, 병합을 잠시 중지하고, 나머지 (k-2) 개의 파일 간에 다시 (k-2)원 병합 정렬을 반복 수행한다. 

 ③ 이와 같이 (k-3)원, (k-4)원, …, 2원 병합 정렬 순으로 병합을 반복 수행하다가, 마지막 한 개의 정렬된 파일로 저장하고 완료된다. 

1. 1. 그래프의 운행
   • 그래프를 구성하는 모든 정점들을 체계적으로 방문하는 방법
   • 스택을 이용한 깊이 우선 탐색 방법과
   • 대기열을 이용한 넓이 우선 탐색 방법이 있다.
2. 2. 그래프의 응용
   • 최단 경로(shortest path)
     • 단일 점 출발 최단 경로 문제 (single source shortest path problem)
     • 모든 노드 간의 최단 경로 문제 (all pairs shortest path problem)
   • 최소 비용 신장 트리(minimal cost spanning tree)
     • 신장 트리
     • 최소 비용 신장 트리 알고리즘
     • Kruskal의 방법
   • 작업 네트워크의 위상 정렬과 임계 경로

1. 1. 그래프의 표현 방법
   • 표를 이용하는 방법
   • 포인터를 이용한 표현 방법
   • 인접 행렬
   • 인접 리스트
   • 인접 다중 리스트
   • 직교 리스트
   • 이행적 폐쇄 행렬
   • 반사 이행적 폐쇄 행렬

*이산수학 그래프 항목을 참고하세요.

1. 그래프의 운행 

 그래프를 구성하는 모든 정점들을 체계적으로 방문하는 방법. 

  스택을 이용한 깊이 우선 탐색 방법과 

 대기열을 이용한 넓이 우선 탐색 방법이 있다 

  깊이 우선 탐색(DFS : depth first seatch) 

 무방향 그래프의 경우 운행 방법 

 시작 정점 V를 방문한다. 

 V에 인접하면서 방문하지 않은 정점 W를 선택하여 W를 시작 정점으로 하고  깊이 우선 탐색을 다시 시작한다. 

 모든 인접 정점들이 이미 방문된 정점에 도달하면, 방문하지 않은 인접 정점을 갖는 노드로 거슬러 올라가 그 정점부터 다시 깊이 우선 탐색을 시작한다. 

 방문하지 않은 어떤 정점을 도달할 수 없을 때 탐색이 끝난다. 

깊이 우선 탐색(DFS : depth first seatch) 

 [알고리즘] 인접 리스트로 표현된 그래프에 대한 DFS 알고리즘 

 #define N 50; 

struct node 

{ 

        int vertex; 

        struct node *next; 

} 

struct node *head[N]; 

main() 

{ 

        int visit[N], mark, V; 

        mark = 0; 

        for (V = 0; V < N; V++)  / *visit의 초기화 */ 

                visit[v] = 0; 

        for (V = 0; V < N; V++)   

                if(visit[V] == 0) DFS(V); 

}  /* end main */ 

 [알고리즘] 인접 리스트로 표현된 그래프에 대한 DFS 알고리즘 

 DFS(int V) 

{ 

        struct node * t; 

        mark++; 

        visit[V] = mark; 

        t = head[V] 

        while (t != NULL) 

        { 

                if (visit [t -> vertex] == 0) dfs(t -> vertex); 

                t = t -> next; 

        } 

} 

 넓이 우선 탬색(BFS : Breadth First Search) 

 무방향 그래프에서 운행방법 

 시작되는 정점 V를 결정하여 방문한다. 

 정점 V에 인접하면서 방문하지 않은 모든 정점을 방문하고 다시 이 정점에 대하여 인접하여 방문하지 않은 모든 정점에 대하여 너비 우선 탐색을 계속한다. 

 더 이상 방문할 정점이 없을 때 BFS는 끝이 난다. 

 BFS 방식은 큐를 이용한다. 

 [알고리즘] 인접 리스트로 표현된 그래프에 대한 BFS 알고리즘 

 #define N 50; 

struct node 

{ 

        int vertex; 

        struct node *next; 

} 

struct node *head[N]; 

main() 

{ 

        int mark, visit[N], V; 

        mark = 0; 

        for (V = 0; V < N; V++)   

                visit[v] = 0; 

        for (V = 0; V < N; V++)   

                if(visit[V] == 0) BFS(V); 

}   

 [알고리즘] 인접 리스트로 표현된 그래프에 대한 DFS 알고리즘 

 BFS(int V) 

{ 

        struct node * t; 

        queueinit();  /* intialize queue */ 

        addpue(V); 

        visit[t -> vertex] = mark; 

        do 

        { 

                V = depue(); 

                t = head[V]; 

                while (t != NULL) 

                { 

                        if (visit[t -> vertex] ==0) 

                        { 

                                 mark++; 

                                 addpue(t -> vertex); 

                                 visit[t -> vertex] = mark; 

                        } 

                 }         

        } while (! Queueempty()); 

} 

2. 그래프의 응용  

 최단 경로(shortest path) 

 그래프의 가지(branch)에 각각 거리(weight)가 주어져 있을 때, 원점으로부터 최종 목적지까지 연결하는 그래프를 통한 최단 경로를 찾는 문제 

 단일 점 출발 최단 경로 문제 (single source shortest path problem) 

 모든 노드 간의 최단 경로 문제 (all pairs shortest path problem) 

 단일점 출발 최단 경로 문제(single source shortest path problem) 

 방향 그래프 G = (V, E)와 가중치 함수 W(e)가 주어지고, 출발 정점 V0가 주어졌을 때 V0에서 G의 나머지 모든 정점으로의 최단 경로를 찾는 것 

 모든 노드간의 최단 경로문제 (all pairs shortest path problem) 

 [알고리즘] Floyd  최단 경로 알고리즘 

 Allcosts ( float A[n][n], float cost[n][n]) 

{ 

        // cost[n][n]은 비용 인접 행렬이고, A[i][j]는 i에서 j로의 최단 경로 비용이다. 

        Int i, j, k; 

        for (i=1; i <= n; i++) 

        for (j=1; j <= n; j++) 

                 A[i][j] = cost[i][j];  //cost를 A에 복사 

        for (i=1; I <= n; i++) 

                 A[i][j] = 0; 

        for (k=1; k <= n; k++) 

        for (i=1; j <= n; i++) 

        for (j=1; j <= n; j++) 

                 if (A [i][k] + A [k][j] < A [i][j] 

                      A [i][j] = A [i][k] + A [k][j]; 

} 

 (2) 최소 비용 신장 트리(minimal cost spanning tree) 

 그래프에서 각 경로상에 가중치가 주어졌을 때 가중치가 가장 작은 경로를 통해 순환을 허용하지 않으며, 모든 정점을 연결하는 트리 구조로 변환하는 알고리즘 

 (2) 최소 비용 신장 트리(minimal cost spanning tree) 

 신장 트리 

 연결 그래프 G=(V,E)에서 연결 간선의 일부를 사용하여 그래프의 모든 정점들이 연결되어 트리로 된 경우 

 완전 그래프와 3개의 신장 트리 

 최소 비용 신장 트리 알고리즘 

 Prim의 방법 

 가중치 그래프 G=(V, E)에서 V=1, 2, 3, …, n으로 구성되어 있다. 이때, 출발점을 노드 1로 선택하여 시작한다.  

 선택된 노드에서 가장 가까운 노드인 비용이 가장 낮은 노드 중 연결이 안된 노드를 찾아서 이 두 노드를 연결시키게 된다.  

 정점이 모두 연결될 때까지 앞의 방법을 계속 반복한다. 

 최소 비용 신장 트리 알고리즘 

 작업 네트워크의 위상 정렬과 임계 경로 

 [정의 6-1] 정점이 작업을 나타내고 그 간선이 작업 간의 우선 관계를 나타내는 방향 그래프를 정점 작업 네트워크(activity on vertex network) 또는 AOV 네트워크라 한다. 

  [정의 6-2] AOV 네트워크 G에서 만약 i에서 j까지의 방향 경로가 존재하면 정점 i는 정점 j의 선행자(predecessor)이다. 만약 <i, j>가 G의 간선이면 i는 j의 즉각 선행자(immediate predecessor)이다.  

만약 i가 j의 선행자라면 j는 후속자(successor)이다.  

i가 j의 즉각 선행자라면 j는 i의 즉각 후속자(immediate successor)이다. 

 최소 비용 신장 트리 알고리즘 

 작업 네트워크의 위상 정렬과 임계 경로 

 [정의 6-3] 관계는 집합 S의 어떤 원소 x에 대해서도 X, X인 경우가 성립되지 않을 때 그 집합 S에 대해 비반사적이다. 

이행적이면서 비반사적 관계를 부분 순서(partial order)라 한다. 

 AOV 네트워크상에서 위상 순서를 구하는 예 

1. 그래프의 표현 방법 

 표를 이용하는 방법 

 포인터를 이용한 표현 방법 

 인접 행렬  

 인접 리스트  

 인접 다중 리스트  

 직교 리스트  

 이행적 폐쇄 행렬 

 반사 이행적 폐쇄 행렬 

1. 그래프의 개념 

 표를 이용하는 방법 

 정점 리스트와 간선을 표현하는 정점쌍 리스트(vertex pair list)로 표현하는 방법 

 포인터를 이용한 표현 방법 

 그래프의 각 정점에 포인터를 주고 그 정점에 인접한 정점에 부속된 간선에 인덱스를 주어서 표현하는 방법 

 각 정점의 차수를 쉽게 알 수 있다. 

 인접 행렬(adjacency matrix) 

 방향그래프와 무방향 그래프의 물리적인 구조를 인접한 정점들간의 관계를 행렬 방식에 의해 표현한 것 

 2차원 n×n 배열 A로 정의할 수 있다. 

 배열 A[i][j]의 요소 값은 정의된 2차원 배열 내에 그래프의 정점i 와 정점j간에 간선 (i, j)이 존재하면,  인접 행렬의 i 번째 행과  

j 열 A[i][j] = 1을 표시하고, 연결 간선이 존재하지 않으면, A[i][j] = 0을 표시하여 구성한다. 

 [알고리즘] 무방향 그래프의 인접 행렬 표현 

 adjacencymatrix (int n, int m, int A[n][n])  // /* n:정점의 수, m:간선의 수 */ 

{ 

        int row, col, I, j; 

        for (i=1; j<=n; j++) 

                a[i][j]=0; 

//간선을 A[row][col]에 저장 

for (i=1; i<=m; i++) 

        { 

                scanf(“%d %d”, &row, &co);  /* 간선(row, col)의 입력 */ 

                        A[row][col] = 1; 

                        A[col][row] = 1; 

        } 

}

 인접 리스트(adjacency list) 

 정점 i와 인접한 정점들을 연결 리스트로 표현하는 방식 

  n 개의 정점으로 구성된 그래프의 경우에는 n개의 연결 리스트로 표현된다. 즉, 각 정점에 대해 하나의 리스트가 존재한다. 

 연결리스트 i에 있는 노드들은 정점 i와 인접한 정점들을 나타낸다. 각 노드는 적어도 2개의 필드, 즉 vertex와 link필드를 갖는다.  

 vertex 영역은 정점 i에 인접한 정점들을 표시하고, link 영역은 다음의 정점들을 연결하는 영역이다. 

 이행적 폐쇄 행렬(transitive closure matrix) 

 행렬 A가 그래프 G의 인접 행렬일 때 만약 길이가 양수인 경로에서 

 A+[i][j]=1 는 i에서 j로 가는 경로 길이가 0보다 큰 경우 

 A+[i][j]=1 는 그렇지 않은 경우 

 이행적 폐쇄 행렬(transitive closure matrix) 

 [알고리즘] 이행적 폐쇄 행렬 (A+)에 대한 Warshall 알고리즘 

 Transitive (int A[n][n], int C[n][n]) 

{ 

        int i, j, k; 

        for (i=1; j<=n; j++) 

        for (j=1; j<=n; j++) 

                A[i][j] = C[i][j]; 

        for (k=1; k<=n; k++) 

        for (i=1; i<=n; i++) 

        for (j=1; j<=n; j++) 

                if (A[i][k] == 0) 

                        A[i][j] = A[i][k] || A[k][j]; 

} 

 반사 이행적 폐쇄 행렬(reflexive transitive closure matrix) 

 행렬 A가 그래프 G의 인접 행렬일 때 

 A*[i][j]=1 는 i에서 j로 가는 경로 길이가 0보다 크거나 경로가 존재하는 경우 

 A*[i][j]=1 는 그렇지 않은 경우 

1. 1. 그래프의 개념
   • 그래프의 정의
     • 정점(vertex)이라고 불리는 원소들의 집합 V와 간선(edges)이라 불리는 V의 원소들의 비순서화된 쌍들의 집합 E로 구성
     • V는 공집합이 아닌 정점들의 유한집합
     • E는 간선, 즉 연결선의 집합
     • V(G)는 그래프의 정점의 집합
     • E(G)는 그래프의 간선의 집합
2. 2. 그래프의 종류
   • 무방향 그래프(undirected graph 또는 graph)
   • 방향 그래프(directed graph 또는 digraph)
   • 다중 그래프(multi graph 또는 multiple graph)
   • 단순 그래프(single graph 또는 tree graph)
   • 완전 그래프(complete graph)
   • 서브그래프(subgraph)
   • 정규 그래프(regular graph)
   • 연결그래프(connected graph)
     • 강력 연결 그래프
     • 약 연결 그래프
   • 단절그래프(disconnected graph)

1. 1. 트리의 산술식의 내부 표현
   • 산술식의 내부 표현(polish notation)
     
     • 중위 표기법(infix notation) : left - root - right 운행 -> 산술식의 표현에서 변수 - 연산자 - 변수의 순으로 표시된다.
     • 후위 표기법(postfix notation) : left - right - root 운행 -> 산술식의 표현에서 변수 - 변수 - 연산자의 순으로 표시된다.
     • 전위 표기법(prefix notation) : root - left - right 운행 -> 산술식의 표현에서 연산자 - 변수 - 변수의 순으로 표시된다.
2. 2. 이진 트리의 삽입
   • 어떤 새로운 노드를 입력한다면 그의 키를 이용하여 이진 트리의 성질을 만족 한 어떤 자식 노드가 될 것인가의 위치를 결정하여 저장하는데 키 값을 중심으로 키 값보다 큰 수는 오른쪽 자식 노드가 되고, 키 값보다 작은 수는 왼쪽 자식 노드가 된다.
3. 3. 이진 트리의 삭제
   • 삭제할 노드를 단 노드로 대치시킨다.
   • 대치시키기 위해 선택하는 단 노드는 삭제할 노드의 왼쪽 서브 트리 내에 있고, 맨 오른쪽에 있는 단 노드이다.
   • 먼저 삭제할 노드가 단 노드일 경우에는 바로 해당 노드를 삭제한다.
   • 삭제할 노드의 왼쪽 서브 트리에 오른쪽 노드가 없는 경우 해당 노드를 삭제 한 후 왼쪽 단 노드가 빈 자리로 옮겨 간다.
   • 삭제할 노드의 왼쪽 노드에 서브 트리가 있는 경우 해당 노드를 삭제한 후 왼쪽 서브 트리의 제일 오른쪽 노드를 삭제된 노드에 채워준다.

1. 그래프의 개념 

 산술식의 내부 표현(polish notation) 

 그래프의 정의 

 정점(vertex)이라고 불리는 원소들의 집합 V와 간선(edges)이라 불리는 V의 원소들의 비순서화된 쌍들의 집합 E로 구성 

 V는 공집합이 아닌 정점들의 유한집합   

 E는 간선, 즉 연결선의 집합 

 V(G)는 그래프의 정점의 집합 

 E(G)는 그래프의 간선의 집합 

 케인즈버그(Koenigsberg)의 다리 

*이산수학 그래프파트에서 수학적으로 자세히 다룹니다.

 그래프의 예 <그림 6-2> 

 그래프의 예 설명 

V(G1) = 1, 2, 3, 4 

E(G1) = (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 

V(G2) = 1, 2, 3, 4, 5, 6, 7 

E(G2) = (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7) 

V(G3) = 1, 2, 3 

E(G3) = <1, 2>, <2, 1>, <2,3> 

V(G4) = 1, 2, 3, 4 

E(G4) = (1, 2), (1, 3), (2, 4), (3, 4), <2,3> 

 그래프의 용어 

 인접(adjacent)과 부속(incident) 

 무방향 그래프에서 간선(V1, V2)가 E(G)에 존재한다면 V1 과 V2는 인접(adjacent) 한가고 하며, 이 때 간선 (V1, V2)는 정점 V1 과 V2에 부속(incident) 된다고 한다. 

 방향성 그래프에서는 연결된 간선의 방향에 따라 인접 개념이 달라진다. 

즉, <V1, V2>가 하나의 연결 간선이라면 정점 V1은 정점 V2에 인접하다라고 하며, 정점 V2는 정점 V1로부터 인접 되었다고 한다. 

 차수(degree) 

 그래프의 어떤 특정한 정점에 연결된 간선의 수 

 정점의 진출 차수(out degree) 

해당 정점에서 나가는 간선의 수 

 정점의 진입 차수(in degree) 

해당 정점으로 들어오는 간선의 수 

 데이터 처리 과정 

 무방향 그래프에서는 진출차수와 진입 차수의 개념은 적용될 수 없으므로 각 정점의 차수는 정점과 직접적으로 연결된 간선들의 수가 된다.  

 무방향 그래프 

 경로(path) 와 사이클(cycle) 

 경로 

그래프에서 임의의 정점 Vi에서 Vi에 이르는 연결선 

 사이클 

방향성 그래프에서 처음 정점과 마지막 정점이 같은 다순경로 

 경로의 길이(length)   

경로를 구성하는 간선의 수 

 단순 경로(simple path)   

한 경로상에 있는 모든 정점들이 서로 다른 경로 

 연결 요소(connected components) 

 무방향 그래프의 경우 최대 연결 서브 그래프(maximum connected subgraph)를 의미 

 즉, 그래프를 운행했을 때 방문된 정점과 그것에 부속된 간선들로 구성 

 N개의 정점과 e개의 간선을 갖는 그래프 G에서 임의의 정점 i의 차수를 d라 하면 그래프의

간선(edge)의 수 e는 

2. 그래프의 종류 

 무방향 그래프 (undirected graph 또는 graph) 

 G1, G2에서 처럼 두 정점간에 연결된 간선들이 방향이 없는 지정되지 않은 그래프

 방향 그래프(directed graph 또는 digraph) 

 각 정점들간의 연결선인 간선들이 방향이 표시된 쌍으로 나타낸 그래프 

 다중 그래프(multi graph 또는 multiple graph) 

 다중 그래프는 같은 정점들을 연결한 간선이 여러 개 존재하는 그래프 

 순환(loop)를 허용 

 다중 그래프 

 단순 그래프(single graph 또는 tree graph) 

 정점을 연결한 간선들은 순환이 없고 연결한 간선이 한 개만 존재하는 그래프 

 서브그래프(subgraph) 

 그래프 G = {V, E}가 있을 때, 어떤 그래프 G’ = {V’, E’} 이고 

이 두 개의 그래프 G, G’의 관계에서 V(G’)⊆V(G) 이고 E(G’)⊆E(G)인 조건을 만족하는 그래프 G’ 

 서브 그래프 

 서브그래프(subgraph) 

 서브 그래프의 예 

 정규 그래프(regular graph) 

 그래프의 모든 정점이 같은 차수(degree)를 가진 그래프 

 모든 정점이 차수가 k이면, 그 그래프를 k 차 정규 그래프 (k-th regualr graph) 

 연결그래프(connected graph)와 단절그래프(disconnected graph) 

 그래프에서 모든 정점들에 대하여 서로 다른 두 개의 정점에 이르는 경로가 존재하면 그 그래프는 연결그래프라 하고, 그렇지 않으면 그 그래프를 단절 그래프 

 연결 그래프와 단절 그래프 

 강력 연결 그래프(strongly connected graph) 

 방향성 그래프에서 임의의 두 정점 V1과 V2에 <V1, V2> 그리고 <V2, V1>로 양방향 직접 경로가 존재할 경우 그래프 

 약 연결 그래프(weakly connected graph) 

 방향성 그래프에서 임의의 두 정점 V1과 V2에 <V1, V2> 그리고 <V2, V1>로 단방향 직접 경로가 존재할 경우 그래프 

1. 트리의 산술식의 내부 표현 

 산술식의 내부 표현(polish notation) 

 산술식의 표현 

 중위 표기법(infix notation) :  left - root - right 운행            

 산술식의 표현에서 변수 - 연산자 - 변수의 순으로 표시된다. 

 후위 표기법(postfix notation)  : left - right - root 운행 

 산술식의 표현에서 변수 - 변수 - 연산자의 순으로 표시된다. 

 전위 표기법(prefix notation) : root - left - right 운행 

 산술식의 표현에서 연산자 - 변수 - 변수의 순으로 표시된다. 

  산술식을 이진 트리로 변경하는 방법 

 먼저 산술식의 우선 순위를 결정한다. 

 이진 트리로 표현할 때는 상향식(bottom up) 방법으로 표현한다. 

 이때 산술식을 이진 트리로 표현할 때 산술식에서의 왼쪽 위치와  오른쪽 위치 순서는 이진 트리에서도 그대로 적용되어야 한다 

 산술식 내부 표현간의 상호 변환하는 방법 

 중위 표현을 전위 표현으로 상호 변환 (infix→prefix)하는 방법 

 주어진 infix의 수식에 대하여 연산 범위에 맞게 괄호를 표시한다.   

 a * b + c / d  의 수식에 대하여 괄호를 표시하고,  

( ( a * b ) + ( c / d ) )  

 ordinary prefix 표현은 각 연산자를 괄호 밖으로 빼고, 원래 연산자위치에 콤마(,)를 찍는다. 

  + ( * ( a , b ) , / ( c , d ) ) 

 cambridge polish 표현은 연산자를 다시 괄호 안의 맨 앞으로 보내고, 콤마를 없앤다. 

  ( + ( * a b ) ( / c d ) ) 

 polish 표현은 cambridge polish에서 괄호를 제거하여 표현한다. 

  + * a b / c d 

 중위 표현을 후위 표현으로 상호 변환 (infix→postfix)하는 방법 

 먼저 주어진 infix의 수식에 대하여 연산 범위에 맞게, 괄호를 표시한다. 

 a * b + c / d  의 수식에 대하여 괄호를 표시하고,  

  ( ( a * b ) + ( c / d ) )  

 ordinary postfix 표현은 각 연산자를 괄호 밖으로 빼고, 원래 연산자위치에 콤마(,)를 찍는다. 

  (  ( a , b ) * ,  ( c , d ) / ) + 

 cambridge reverse polish 표현은 연산자를 다시 괄호 안의 맨 뒤로 보내고 콤마 를 없앤다. 

  ( ( a  b ) * ( c d ) /  ) + 

 reverse polish 표현은 cambridge reverse polish에서 괄호를 제거하여, 표현한다. 

  a b *  c d / + 

2.  이진 트리의 삽입과 삭제 

 이진 트리의 삽입 

 어떤 새로운 노드를 입력한다면 그의 키를 이용하여 이진 트리의 성질을 만족한, 어떤 자식 노드가 될 것인가의 위치를 결정하여 저장하는데, 키 값을 중심으로 키 값보다 큰 수는 오른쪽 자식 노드가 되고, 키 값보다 작은 수는 왼쪽 자식 노드가 된다. 

 이진 트리의 노드 삽입 예 

 이진 트리의 삭제 

 삭제할 노드를 단 노드로 대치시킨다. 대치시키기 위해 선택하는 단 노드는 삭제할 노드의 왼쪽 서브 트리 내에 있고, 맨 오른쪽에 있는 단 노드이다. 

 먼저 삭제할 노드가 단 노드일 경우에는 바로 해당 노드를 삭제한다. 

 이진 트리에서 노드6의 삭제 

 삭제할 노드의 왼쪽 서브 트리에 오른쪽 노드가 없는 경우, 해당 노드를 삭제 한 후 왼쪽 단 노드가 빈 자리로 옮겨 간다. 

 이진 트리에서 노드2를 삭제 

 삭제할 노드의  왼쪽 노드에 서브 트리가 있는 경우 해당 노드를 삭제한 후  왼쪽 서브 트리의 제일 오른쪽 노드를 삭제된 노드에 채워준다. 

 이진 트리에서 노드4를 삭제 

 삭제시킬 노드가 오른쪽 서브 트리를 가졌으나 왼쪽 서브 트리가 없는 경우에는 해당 노드를 삭제한 후 삭제할 노드가 붙은 노드의 오른쪽 서브 트리를 위로 이동한다. 

 이진 트리에서 노드6을 삭제