Computer Network Lab. Keimyung University

Presentation on theme: "Computer Network Lab. Keimyung University"— Presentation transcript:

1 Computer Network Lab. Keimyung University Juht@kmu.ac.kr
배열 응용 Computer Network Lab. Keimyung University

2 탐색 및 정렬 탐색(searching) 정렬(sorting) 자료의 집합에서 특정한 원소를 찾는 작업
많은 프로그램에서 자주 사용되는 작업 배열에서의 탐색은 자료의 집합이 배열에 저장됨 입력: 찾고자 하는 원소의 값 결과: 찾은 원소의 인덱스 정렬(sorting) 원소의 값을 정해진 순서로 배치하는 작업 오름차순: 배열의 원소 값이 증가하는 순서로 배치 내림차순: 배열의 원소 값이 감소하는 순서로 배치 배열에서의 정렬은 자료를 순서에 따라서 배열에 배치하는 작업 입력: 정렬되지 않은 배열 결과: 정렬된 배열 자료구조 제1장: 자료구조의 개념

3 선형 탐색 처음 원소부터 마지막 원소까지 탐색 값과 원소 값을 비교함 예: 문자열 포인터 배열에서의 탐색
학생의 이름이 문자열 포인터 배열 name에 저장되어 있음 학생의 이름을 lsearch 함수가 탐색을 함 lsearch 함수는 name에 저장된 학생 이름과 탐색하고자 하는 이름이 저장된 target을 비교함 탐색을 성공하여 찾으면 인덱스를 찾지 못하면 -1을 돌려 줌 두 문자열이 같으면 0을 같지 않으면 0 이외의 값을 돌려주는 문자열 비교 함수는 strcmp를 사용함 자료구조 제1장: 자료구조의 개념

4 문자열 포인터 배열에서의 탐색 #define NUM_OF_STD 5
char *name[NUM_OF_STD] = { "Hong Gil Dong", "Lee Mong Ryong", "Byun Gang Soe", "Sim Bong Sa", "Byun Hak Do" }; int main() { int i; i = lsearch(name, "Sim Bong Sa", NUM_OF_STD); if ( i != -1 ) printf("Found: %d\n",i); else printf("Not found\n"); } int lsearch(char **data, char *target, int size){ int r; for( r = 0 ; r < size ; r++ ) { if( strcmp(target,*data) == 0 ) return r; data++; return -1; /* not found */ 자료구조 제1장: 자료구조의 개념

5 문자열 포인터 배열에서의 탐색 자료구조 제1장: 자료구조의 개념

6 이진 탐색 선형 탐색의 수행 시간은 O(n)임 좀더 효율적인 탐색 방법은? 이진탐색 이진 탐색의 전제 조건 이진 탐색 방법
배열이 정렬이 되어 있어야 함 이진 탐색 방법 탐색 값과 정렬된 배열의 중간 원소의 값을 비교하면 탐색 공간을 반으로 줄일 수 있음 한번 비교할 때 마다 탐색 공간이 반으로 줄어 들기 때문에 O(lg n) 정렬은 O(n) 보다 많은 시간이 필요하므로 선형 탐색 보다 비효율적일 수 있음 한번 정렬하고 여러 번 탐색을 해야 하는 경우에 효율적임 자료구조 제1장: 자료구조의 개념

7 이진 탐색 예: 문자열 포인터 배열 문자열도 사전적 순서에 의하여 정렬될 수 있음
사전적 순서: 문자열을 이루는 문자의 ASCII 코드 값의 크기로 문자열의 크기를 결정하며 앞에 있는 문자가 더 중요함 자료구조 제1장: 자료구조의 개념

8 이진 탐색 예: 문자열 포인터 배열 #define NUM_OF_STD 5 char *name[NUM_OF_STD] = {
"Byun Gang Soe", "Byun Hak Do", "Hong Gil Dong", "Lee Mong Ryong", "Sim Bong Sa"}; int main() { int i; i = bsearch(name, NUM_OF_STD); if ( i != -1 ) printf("Found: %d\n",i); else printf("Not found\n"); } 자료구조 제1장: 자료구조의 개념

9 이진 탐색 예: 문자열 포인터 배열 int bsearch(char **data,char *target, int size){
int r; int left = 0; int right = size - 1; int middle, cmp; while ( left <= right ) { middle = (left + right ) / 2 ; cmp = strcmp(target,data[middle]); if( cmp > 0 ) left = middle + 1; else if ( cmp < 0) right = middle - 1; else return middle; } return -1; /* not found */ 자료구조 제1장: 자료구조의 개념

10 선택 정렬 하나의 원소씩 바른 위치에 있도록 집어 넣는 방법 시간 복잡도
오름차순의 경우 가장 작은 것부터 차례로 첫째 위치부터 채워 나감 차례로 찾는 방식은 선형탐색 방법을 사용함 시간 복잡도 첫째 원소를 찾기 위하여 n번, 둘째 원소를 찾기 위하여 n-1번,… 마지막 원소를 찾기 위하여 0번 비교를 수행함 (n) + (n-1) + (n-2) + …… + 0 = O(n(n+1)/2) = O(n2) 자료구조 제1장: 자료구조의 개념

11 선택 정렬 예 자료구조 제1장: 자료구조의 개념

12 문자열 포인터 배열의 선택 정렬 평균 수행시간이 가장 효율적인 알고리즘 수행 방법 시간 복잡도
임의로 기준 값을 정하고 기준 값 보다 큰 묶음과 작은 묶음으로 분류 다시 큰 묶음과 작은 묶음에 대하여 위와 동일한 방법을 재귀적으로 묶음의 크기가 1일 경우까지 적용 시간 복잡도 두개의 묶음으로 나누는 횟수는 lg n 까지 수행함 각 단계에서 n 만큼의 비교를 수행함 O(n lg n) 자료구조 제1장: 자료구조의 개념

13 퀵 정렬의 예 자료구조 제1장: 자료구조의 개념

14 문자열 포인터 배열의 퀵 정렬 int quicksort(char **data, int left, int right, int size){ char pivot[20]; int l=left, r=right; char *temp; if (size <= 1 ) return -1; strcpy(pivot, data[left+rand()%size]);; while ( 1 ) { while( (strcmp(data[l],pivot) < 0) && (l < r ) ) l++; while( (strcmp(data[r],pivot) > 0) && (l < r ) ) r--; if( l >= r ) break; temp = data[l]; data[l] = data[r]; data[r] = temp; } quicksort(data, left, r, r-left+1); quicksort(data, r+1, right, right-r); 자료구조 제1장: 자료구조의 개념

15 배열을 이용한 그래프 표현 그래프는 표현력이 강력하여 많이 사용됨 그래프 = 정점(vertex) + 간선(edge)
도로망, 비행기 노선도, 네트워크 구성, 시스템 상태도 그래프 = 정점(vertex) + 간선(edge) 정점: 점으로 표현 간선: 정점을 잊는 선 그래프의 종류 무방향 그래프: 간선의 방향이 없는 그래프 방향 그래프: 간선이 방향을 가진 그래프 자료구조 제1장: 자료구조의 개념

16 그래프의 표현 그림 표현 수학적 표현 V(G1) = {0,1,2,3,4},
E(G1) = {(0,1), (0,2), (0,4), (1,2), (1,4), (2,3), (3,4)} V(G2) = {0,1,2,3,4,5} E(G2) = {(0,1), (0,2), (1,2), (1,3), (1,4), (2,3), (2,4), (3,5), (4,5)} 자료구조 제1장: 자료구조의 개념

17 그래프의 표현 그래프 G에 대한 인접 행렬 A는 인접 행렬의 C 언어 표현: 이차원 정수 배열
n X n 행렬로 표현 ( n = | V(G | ) Ai,j = 1 (i,j) ∈ E(G) = 0 (i,j) ∈ E(G) 인접 행렬의 C 언어 표현: 이차원 정수 배열 int G1[5][5] = { {0, 1, 1, 0, 1}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 0, 1, 0, 1}, {1, 1, 0, 1, 0}}; int G2[6][6] = { {0, 1, 1, 0, 0, 0}, {0, 0, 1, 1, 1, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0}}; 자료구조 제1장: 자료구조의 개념

18 정점의 차수 차수 정점 i의 진출 차수는 인접 행렬에서 i 행의 합과 같음
그래프에서 정점에 연결된 간선의 수 진입차수: 정점에 도착하는 간선의 수 진출차수: 정점에서 출발하는 간선의 수 무방향 그래프는 진출 진입 차수가 같음 정점 i의 진출 차수는 인접 행렬에서 i 행의 합과 같음 정점 i의 진입 차수는 인접행렬에서 i 열의 합과 같음 자료구조 제1장: 자료구조의 개념

19 진출 차수 계산 프로그램 int outdegree(int *graph, int row, int size) {
int deg = 0; int *col; int i; col = graph+(row*size); for(i = 0 ; i < size ; i++) { deg = deg + *col; col++; } return deg; 자료구조 제1장: 자료구조의 개념

20 진입 차수 계산 프로그램 int indegree(int *graph, int colum, int size) {
int deg = 0; int *row; int i; row = graph + colum; for( i = 0 ; i < size ; i++) { deg = deg + *row; row = row + size; } return deg; 자료구조 제1장: 자료구조의 개념

21 오일러 경로 임의의 경로에서 출발하여 각 간선을 한번씩만 거치고 처음 출발점으로 돌아오는 경로 예 자료구조
제1장: 자료구조의 개념

22 오일러 경로 찾기 알고리즘 임의의 정점 i를 시작 정점으로 선택
i에 연결된 임의의 j 정점을 선택하며 연결된 정점이 없으면 수행 종료 인접 행렬 Ai,j와 Aj,i를 1에서 0으로 변경하여 (i,j) 경로를 지나갔음을 표현 i를 j로 대치하여 2의 과정을 수행 자료구조 제1장: 자료구조의 개념

23 오일러 경로 찾는 프로그램 int eulerpath(int *g, int visit, int size) { int *row;
int i; row = g + visit*size; for ( i = 0 ; i < size ; i++ ){ if ( *row != 0 ) { *row = 0; /* A[i][j] = 0 */ *(g + i*size + visit) = 0; /* A[j][i] = 0 */ printf("(%d,%d)",visit,i); eulerpath(g,i,size); } row++; 자료구조 제1장: 자료구조의 개념

24 그래프의 연결성 그래프 G에 대한 인접 행렬 A의 멱집합은 그래프의 연결성 표현 A는 하나의 간선을 거쳐서 갈 수 있는 경로
…. An은 n개의 간선을 거쳐서 갈 수 있는 경로 자료구조 제1장: 자료구조의 개념

25 행렬의 멱집합과 연결성 예 1 4 2 3 자료구조 제1장: 자료구조의 개념

26 행렬의 곱 int matrixpower(int *graph, int *power, int size) { int row, column, r, c,x; for( row = 0 ; row < size ; row++) { for(column = 0 ; column < size ; column++ ){ x = 0; for( r = 0, c = 0; r < size ; r++, c++ ) x += *(graph + row*size+ c) * *(graph + r*size + column); *(power + row * size + column) = x; } 수행 시간 복잡도는 O(n3) 자료구조 제1장: 자료구조의 개념

27 질의 및 토의 자료구조 제1장: 자료구조의 개념