C언어 응용 제 15 주 검색

다음 주 과제 기말시험 필기 : 2014년 12월 15일 1교시, C226 실기 : 2014년 12월 17일 5,6교시, E323, E561 시험 범위 : 7장 ~ 11장

검색 검색 순차 검색 이진 검색 이진 트리 검색 해싱

자료에 대한 검색의 개념을 이해한다. 순차 검색의 개념과 알고리즘을 알아본다. 이진 검색의 개념과 알고리즘을 알아본다. 해시에 대해 알아보고 다른 검색 알고리즘과의 차 이를 이해한다.

검색(search) 컴퓨터에 저장한 자료 중에서 원하는 항목을 찾는 작업 탐색 키를 가진 항목을 찾는 것 검색 성공 - 원하는 항목을 찾은 경우 검색 실패 – 원하는 항목을 찾지 못한 경우 탐색 키를 가진 항목을 찾는 것 탐색 키(search key) - 자료를 구별하여 인식할 수 있는 키 삽입/삭제 작업에서의 검색 원소를 삽입하거나 삭제할 위치를 찾기 위해서 검색 연산 수행

검색 방법 수행 위치에 따른 분류 검색 방식에 따른 분류 검색 방법의 선택 내부 검색 - 메모리 내의 자료에 대해서 검색 수행 외부 검색 - 보조 기억 장치에 있는 자료에 대해서 검색 수행 검색 방식에 따른 분류 비교 검색 방식(comparison search method) 검색 대상의 키를 비교하여 검색하는 방법 순차 검색, 이진 검색, 트리 검색 계산 검색 방식(non-comparison method) 계수적인 성질을 이용한 계산으로 검색 하는 방법 해싱 검색 방법의 선택 자료 구조의 형태와 자료의 배열 상태에 따라 최적의 검색 방법 선택

순차 검색(sequential search, 선형 검색(linear search)) 일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법 가장 간단하고 직접적인 검색 방법 배열이나 연결 리스트로 구현된 순차 자료 구조에서 원하는 항목을 찾는 방법 검색 대상 자료가 많은 경우에 비효율적이지만 알고리즘이 단순하여 구현이 용이함

정렬되지 않은 순차자료구조에서의 순차 검색 검색 방법 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다. 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패 순차 검색 예) 검색 성공의 경우 [그림 11-1] 순차 검색의 예

순차 검색 예) 검색 실패의 경우 [그림 11-1] 순차 검색의 예

정렬되어있지 않은 자료에 대한 순차검색 알고리즘 비교횟수 - 찾고자 하는 원소의 위치에 따라 결정 찾는 원소가 첫 번째 원소라면 비교횟수는 1번, 두 번째 원소라면 비교횟수는 2번, 세 번째 원소라면 비교횟수는 3번, 찾는 원소가 i번째 원소이면 i번, … 정렬되지 않은 원소에서의 순차 검색의 평균 비교 횟수 = 1/n(1+2+3+ … + n) = (n+1)/2   평균 시간 복잡도 : O(n) sequentialSearch1(a[],n, key)      i←0;      while (i<n and a[i]≠key) do {         i←i+1;       }     if (i<n) then return i;     else return -1; end sequentialSearch()

정렬되어있지 않은 자료에 대한 순차검색 C 프로그램 검색 대상 자료 : {8, 30, 1, 9, 11, 19, 2} - 7개 검색 1 : 탐색키 9 검색 ☞ 검색 성공! 검색 2 : 탐색키 6 검색 ☞ 검색 실패! 실행 결과

순차 검색 – 정렬되어 있는 순차자료구조에서의 순차 검색 검색 방법 순서대로 검색하면서 키 값을 비교하여, 원소의 키 값이 찾는 키 값보다 크면 찾는 원소가 없는 것이므로 더 이상 검색을 수행하지 않고 검색종료 정렬되어있는 자료에 대한 순차 검색 예) [그림 11-2] 정렬되어 있는 자료에서의 순차 검색의 예

정렬되어있는 자료에 대한 순차검색 알고리즘 sequentialSearch2(a[],n, key) i←0; 비교횟수 - 찾고자 하는 원소의 위치에 따라 결정 검색 실패의 경우에 평균 비교 횟수가 반으로 줄어든다. 정렬되어있는 원소에서의 순차 검색의 평균 비교 횟수 = 1/n(1+2+3+ … + n) x 1/2 = (n+1)/4   평균 시간 복잡도 : O(n) sequentialSearch2(a[],n, key)      i←0;      while (a[i]<key) do {         i←i+1;       }     if (a[i]=key) then return i;     else return -1; end sequentialSearch2()

정렬되어있는 자료에 대한 순차검색 C 프로그램 검색 대상 자료 : {1, 2, 8, 9, 11, 19, 29} – 7개 검색 1 : 탐색키 9 검색 ☞ 검색 성공! 검색 2 : 탐색키 6 검색 ☞ 검색 실패! 실행 결과

색인 순차 검색(index sequential search) 정렬되어있는 자료에 대한 인덱스 테이블(index table)을 추가로 사용하여 탐색 효율을 높인 검색 방법 인덱스 테이블 배열에 정렬되어있는 자료 중에서 일정한 간격으로 떨어져있는 원소들을 저장한 테이블 자료가 저장되어있는 배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때, 배열에서 n/m 간격으로 떨어져있는 원소와 그의 인덱스를 인덱스 테이블에 저장 검색 방법 indexTable[i].key ≤ key < indexTable[i+1].key를 만족하는 i를 찾아서 배열의 어느 범위에 있는지를 먼저 알아낸 후에 해당 범위에 대해서만 순차 검색 수행

색인 순차 검색 예 검색 대상 자료 : {1, 2, 8, 9, 11, 19, 29} 크기가 3인 인덱스 테이블 작성 인덱스 테이블에서 먼저 탐색 키를 검색하여 검색 범위를 확인하고, 해당 범위에 대해서만 순차 검색 실행 [그림 11-3] 색인 순차 검색의 예

색인 순차 검색 C 프로그램 검색 대상 자료 : {1, 2, 8, 9, 11, 19, 29} – 7개 인덱스 테이블 크기 : 3 검색 1 : 탐색키 9 검색 ☞ 검색 성공! 검색 2 : 탐색키 6 검색 ☞ 검색 실패! 실행 결과

색인 순차 검색의 성능 인덱스 테이블의 크기에 따라 결정 색인 순차 검색의 시간 복잡도 : O(m + n/m) 인덱스 테이블의 크기가 줄어들면 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 검색해야하는 범위도 커진다. 인덱스 테이블의 크기를 늘리면 배열의 인덱스를 저장하는 간격이 작아지므로 배열에서 검색해야하는 범위는 작아지겠지만 인덱스 테이블을 검색하는 시간이 늘어난다. 색인 순차 검색의 시간 복잡도 : O(m + n/m) 배열의 크기 : n, 인덱스 테이블의 크기 : m

이진 검색 (binary search, 이분 검색, 보간 검색(interpolation search)) 자료의 가운데에 있는 항목을 키 값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방법 찾는 키 값 > 원소의 키 값 : 오른쪽 부분에 대해서 검색 실행 찾는 키 값 < 원소의 키 값 : 왼쪽 부분에 대해서 검색 실행 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 더 빠르게 검색 정복 기법을 이용한 검색 방법 검색 범위를 반으로 분할하는 작업과 검색 작업을 반복 수행 정렬되어있는 자료에 대해서 수행하는 검색 방법

이진 검색의 예 [그림 11-4] 이진 검색의 예

이진 검색 알고리즘 binarySearch(a[], low, high, key) middle ← (low+high)/2; 삽입이나 삭제가 발생했을 경우에 항상 배열의 상태를 정렬 상태로 유지하는 추가적인 작업 필요 시간 복잡도 : O( log 2 𝑛 ) binarySearch(a[], low, high, key)     middle ← (low+high)/2;     if (key = a[middle]) return i;     else if (key < a[middle]) then binarySearch(a[], low, middle-1, key);     else if (key > a[middle]) then binarySearch(a[], middle+1, high, key);     else return -1; end binarySearch()

이진 트리 검색(binary tree search) 8장에서 설명한 이진 탐색 트리를 사용한 검색 방법 원소의 삽입이나 삭제 연산에 대해서 항상 이진 탐색 트리를 재구성하는 작업 필요 [그림 11-5] 이진 트리 검색의 예

이진 트리 검색을 이용한 영어사전 검색 프로그램 영어 단어와 뜻을 입력하면 알파벳순서대로 이진 탐색 트리에 삽입 검색할 단어를 입력하면 이진 트리 검색으로 검색하여 단어의 뜻을 출력 사전 출력을 선택하면 트리를 중위 순회하면서 트리에 있는 모든 단어를 출력

단어입력 실행 결과

단어 검색과 삭제 실행 결과

해싱(hashing) 검색 방법 해싱 함수(hashing function) 해시 테이블(hash table) 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식 검색 방법 키 값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 이동 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패 해싱 함수(hashing function) 키 값을 원소의 위치로 변환하는 함수 해시 테이블(hash table) 해싱 함수에 의해서 계산된 주소의 위치에 항목을 저장한 표

해싱 검색 수행 방법 해싱의 예 도서관에서의 도서 검색 [그림 11-6] 해싱 검색의 수행 방법 [그림 11-7] 해싱의 예_위치 번호에 따른 도서 찾기

해싱의 예 강의실 좌석 배정 [그림 11-8] 해싱의 예_학번에 따른 강의실 좌석 배정

해싱 용어 정리 충돌 동거자 오버플로우 서로 다른 키 값에 대해서 해싱 함수에 의해 주어진 버킷 주소를 같은 경우 충돌이 발생한 경우에 비어있는 슬롯에 동거자 관계로 키 값 저장 동거자  서로 다른 키 값을 가지지만 해싱 함수에 의해서 같은 버킷에 저장된 키 값들 오버플로우 버킷에 비어있는 슬롯이 없는 포화 버킷 상태에서 충돌이 발생하여 해당 버킷에 키 값을 저장할 수 없는 상태 [그림 11-9] 동거자의 예_같은 좌석에앉은 짝꿍 [그림 11-10] 오버플로우의 예

키 값 밀도 적재 밀도 사용 가능한 전체 키 값들 중에서 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값의 개수 정도 해시 테이블에 저장 가능한 키 값의 개수 중에서 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값의 개수 정도

해싱 함수 해싱 함수의 조건 해싱 함수는 계산이 쉬워야 한다. 해싱 함수는 충돌이 적어야 한다. 비교 검색 방법을 사용하여 키 값의 비교연산을 수행하는 시간보다 해싱 함수를 사용하여 계산하는 시간이 빨라야 해싱 검색을 사용하는 의미가 된다. 해싱 함수는 충돌이 적어야 한다. 충돌이 많이 발생한다는 것은 같은 버킷을 할당 받는 키 값이 많다는 것이므로 비어있는 버킷이 많은데도 어떤 버킷은 오버플로우가 발생할 수 있는 상태가 되므로 좋은 해싱 함수가 될 수 없다. 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.

해싱 함수의 종류 중간 제곱 함수 키 값을 제곱한 결과 값에서 중간에 있는 적당한 비트를 주소로 사용하는 방법 제곱한 값의 중간 비트들은 대개 키의 모든 값과 관련이 있기 때문에 서로 다른 키 값은 서로 다른 중간 제곱 함수 값을 갖게 된다. 예) 키 값 00110101 10100111에 대한 해시 주소 구하기

제산 함수 승산 함수 함수는 나머지 연산자 mod(C에서의 %연산자)를 사용하는 방법 키 값 k를 해시 테이블의 크기 M으로 나눈 나머지를 해시 주소로 사용 제산함수 : h(k) = k mod M M으로 나눈 나머지 값은 0~(M-1)이 되므로 해시 테이블의 인덱스로 사용 해시 주소는 충돌이 발생하지 않고 고르게 분포하도록 생성되어야 하므로 키 값을 나누는 해시 테이블의 크기 M은 적당한 크기의 소수(prime number) 사용 승산 함수 곱하기 연산을 사용하는 방법 키 값 k와 정해진 실수 α를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기 M과 곱하여 그 정수 값을 주소로 사용

접지 함수 키의 비트 수가 해시 테이블 인덱스의 비트 수보다 큰 경우에 주로 사용 이동 접지 함수 각 분할 부분을 이동시켜서 오른쪽 끝자리가 일치하도록 맞추고 더하는 방법 예) 해시 테이블 인덱스가 3자리이고 키 값 k가 12341234123인 경우 [그림 11-11] 이동 접지 함수의 사용 방법

경계 접지 함수 분할된 각 경계를 기준으로 접으면서 서로 마주보도록 배치하고 더하는 방법 예) 해시 테이블 인덱스가 3자리이고 키 값 k가 12341234123인 경우 [그림 11-12] 경계 접지 함수의 사용 방법

숫자 분석 함수 키 값을 이루고 있는 각 자릿수의 분포를 분석하여 해시 주소로 사용하는 방법 각 키 값을 적절히 선택한 진수로 변환한 후에 각 자릿수의 분포를 분석하여 가장 편중된 분산을 가진 자릿수는 생략하고, 가장 고르게 분포된 자릿수부터 해시 테이블 주소의 자릿수만큼 차례로 뽑아서 만든 수를 역순으로 바꿔서 주소로 사용 예) 키 값이 학번이고 해시 테이블 주소의 자릿수가 3자리인 경우 [그림 11-13] 숫자 분석 함수의 사용 방법

진법 변환 함수 키 값이 10진수가 아닌 다른 진수일 때, 10진수로 변환하고 해시 테이블 주소로 필요한 자릿수만큼만 하위자리의 수를 사용하는 방법 비트 추출 함수 해시 테이블의 크기가 2k일 때 키 값을 이진 비트로 놓고 임의의 위치에 있는 비트들을 추출하여 주소로 사용하는 방법 이 방법에서는 충돌이 발생할 가능성이 많으므로 테이블의 일부에 주소가 편중되지 않도록 키 값들의 비트들을 미리 분석하여 사용해야 한다.

오버플로우 처리 방법 선형 개방 주소법 (선형 조사법(linear probing)) 해싱 함수로 구한 버킷에 빈 슬롯이 없어서 오버플로우가 발생하면, 그 다음 버킷에 빈 슬롯이 있는지 조사한다. 빈 슬롯이 있으면 - 키 값을 저장 빈 슬롯이 없으면 - 다시 그 다음 버킷을 조사 이런 과정을 되풀이 하면서 해시 테이블 내에 비어있는 슬롯을 순차적으로 찾아서 사용하여 오버플로우 문제를 처리하는 방법

선형 개방 주소 법을 이용한 오버플로우 처리 예 해시 테이블의 크기 : 5 해시 함수 : 제산함수 사용. 해시 함수 h(k) = k mod 5 저장할 키 값 : {45, 9, 10, 96, 25} ① 키 값 45 저장 : h(45) = 45 mod 5 = 0 ⇒ 해시 테이블 0번에 45 저장 ② 키 값 9 저장 : h(9) = 9 mod 5 = 4 ⇒ 해시 테이블 4번에 9 저장 ③ 키 값 10 저장 : h(10) = 10 mod 5 = 0 ⇒ 충돌 발생! ⇒ 다음 버킷 중에서 비어있는 버킷 1에 10 저장 ④ 키 값 96 저장 : h(96) = 96 mod 5 = 1 ⇒ 충돌 발생!                       ⇒ 다음 버킷 중에서 비어있는 버킷 2에 96 저장 ⑤ 키 값 25 저장 : h(25) = 25 mod 5 = 0 ⇒ 충돌 발생!                       ⇒ 다음 버킷 중에서 비어있는 버킷 3에 25 저장

선형 개방 주소 법을 사용하는 해시 테이블 [그림 11-14] 선형 개방 주소법을 사용하는 해시 테이블

체이닝 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 하는 방법 버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해서 연결 리스트 사용 각 버킷에 대한 헤드노드를 1차원 배열로 만들고 각 버킷에 대한 헤드노드는 슬롯들을 연결 리스트로 가지고 있어서 슬롯의 삽입이나 삭제 연산을 쉽게 수행할 수가 있다. 버킷 내에서 원하는 슬롯을 검색하기 위해서는 버킷의 연결 리스트를 선형 검색한다.

체이닝을 이용한 오버플로우 처리 예 해시 테이블의 크기 : 5 해시 함수 : 제산함수 사용. 해시 함수 h(k) = k mod 5 저장할 키 값 : {45, 9, 10, 96, 25} ① 키 값 45 저장 : h(45) = 45 mod 5 = 0 ⇒ 해시 테이블 0번에 노드를 삽입하고 45 저장 ② 키 값 9 저장 : h(9) = 9 mod 5 = 4 ⇒ 해시 테이블 4번에 노드를 삽입하고 9 저장 ③ 키 값 10 저장 : h(10) = 10 mod 5 = 0 ⇒ 해시 테이블 0번에 노드를 삽입하고 10 저장 ④ 키 값 96 저장 : h(96) = 96 mod 5 = 1 ⇒ 해시 테이블 1번에 노드를 삽입하고 10 저장 ⑤ 키 값 25 저장 : h(25) = 25 mod 5 = 0

체이닝을 사용하는 해시 테이블 [그림 11-15] 체이닝을 사용하는 해시 테이블