탐색의효율 12 장. 탐색알고리즘 삽입, 삭제에우선하여탐색의효율을높이기위한알고리즘 학습목표 이진탐색, 보간탐색, 이진탐색트리등기본탐색방법의효율을이해한다. 기수탐색트리의두가지구현방법과효율을이해한다. 선형탐사, 제곱탐사, 이중해시의방법과효율차이를이해한다. 버켓, 별도체인등닫힌어드레싱방법을이해한다. 상황에따른자료구조선택방법을이해한다. 1
레코드, 키 Section 01 키, 레코드, 탐색 - 탐색의대상 개인별폴더를하나의레코드로간주해당폴더를찾기위한이름은일종의키필드레코드의집합에서주어진키를지닌레코드를찾는작업을탐색주어진키값을목표키 (Target Key), 또는탐색키 (Search Key) 외부탐색, 내부탐색모든레코드가메인메모리내부에들어와있는상태에서이루어지는탐색레코드가보조기억장치, 메인메모리를오가며이루어지는탐색 [ 그림 12-1] 레코드와키 2
코드 12-1: 이진탐색 Section 02 이진탐색 - 이진탐색 void BinarySearch(int A[ ], int First, int Last, int Key, int& Index) { if (First > Last) 탐색키를가진레코드가없을때 index = -1; 에일리어스변수 Index를 -1로표시 else { int Mid = (First+Last)/2; 가운데인덱스계산 if (Key = = A[Mid]) 탐색키가가운데키와같으면 Index = Mid; 에일리어스변수 Index를해당인덱스로 else if (Key < A[Mid]) 탐색키가가운데키보다작으면 BinarySearch(int A[], First, Mid-1, Value, Index); 왼쪽에서찾음 else 탐색키가가운데키보다크면 BinarySearch(int A[], Mid+1, Last, Value, Index); 오른쪽에서찾음 } } 3
Section 03 보간탐색 - 보간탐색 인덱스 1 2 3 4 5 6 7 8 9 10 11 12 키 20 42 55 62 78 92 112 132 140 145 150 170 [ 표 12-1] 배열레코드분포 키값 150 인레코드를찾기이진탐색한가운데인인덱스 (1+12)/2 = 6 에서탐색을시작보간탐색 1 + (12-1)(150-20)/(170-20) = 10.5. 인덱스 10 또는 11 에서찾기시작인덱스공간 (12-1) 을 1 로볼때, 탐색키가 (150-20)/(170-20) = 0.86 정도에크면오른쪽, 작으면왼쪽으로범위를축소하는방식은이진탐색과동일선형보간인덱스값의증가에따라키값도이에정비례하여증가한다고간주부동소수나눗셈을위한시간효율 O(lg(LgN)) 으로서이진탐색의 O(lgN) 보다는빠르지만키값이선형으로분포한다는조건 4
트리모습에좌우 Section 04 이진탐색트리 - 이진탐색의효율 비교적균형잡힌트리의높이는 lgn. 검색효율은 O(lgN) 이다. 최악의경우연결리스트에가까운트리라면검색효율은 O(N) 확률적으로분석한이진탐색트리의평균효율은 O(1.38 lgn) 평균효율트리의내부경로길이에의해근사적으로표시키 3 인노드의내부경로길이는 3. 이를대략적인비교의횟수로간주 (Level 0:0) + (Level 1: 1 + 1) + (Level 2: 2 + 2) + (Level 3: 3) = 9. 평균적인비교회수는대략 9/6 = 1.5 회가된다. [ 그림 12-2] 내부경로 5
게으른삭제이진탐색트리삭제 중위후속자또는선행자를삭제된노드로옮김으로인해트리모습이변함. 삭제가빈번할수록트리의균형이무너질확률이높아짐. 게으른삭제 (Lazy Deletion) 실제로삭제하지말고해당노드에 삭제됨 표시만함. 나중에몰아서한꺼번에 (Batchwise) 삭제삭제전까지는이전의트리모습, 이전의효율을계속유지 6
간접이진트리레코드는배열에, 트리는키또는인덱스정보만함유삽입, 삭제시간이감소 Index 1 2 3... Key 25 16 12 Data Kim Cho Park [ 표 12-2] 간접트리를위한배열 [ 그림 12-3] 간접이진트리 7
Section 05 기수탐색 - 디지털탐색트리디지털탐색트리 (Digital Search Tree) 비트값을기준으로자식노드를분기 5비트키필드를가정하고알파벳순서를비트값으로할당 A는첫문자이므로 00001 입력순서 A = 00001, S = 10011, E = 00101, R = 10010, C = 00011, H = 01000, X = 11000 [ 그림 11-4] 탐색트리에의한우선순위큐 8
효율 O(lgN) 디지털탐색트리 어떤키내부의비트값이 0 이될확률이나 1 이될확률이 1/2 로동일 새로삽입되는노드가왼쪽으로삽입될확률이나오른쪽으로삽입될확률이거의동일하므로균형트리. 트리높이는 lgn 에근접 최악의경우에는비트수만큼 O(N) 9
일명트라이 (TRIE) 기수탐색트리 탐색또는검색을의미하는 ReTRIEval 의가운데스펠디지털탐색트리의레코드가내부노드또는외부노드모두에분포트라이의레코드는모두외부노드에분포 입력순서 A = 00001, S = 10011, E = 00101, R = 10010 E 가들어올때, 첫비트가 0 이므로루트에서왼쪽으로. A 와 E 의키비트열을비교. 두번째까지는 00, 세번째비트에서서로가달라짐. 두번째비트까지경로를공유해야하므로그경로상에내부노드를추가. [ 그림 12-5] 기수탐색트라이구성 10
트라이균형잡힌트라이 효율은 O(lgN) 이경우의효율은키비교횟수가아님. 키자체의비트열중처음 lgn 개의비트값을검사 트라이의모습 레코드의키값의입력순서와무관 A, R, E, S 순으로레코드가들어와도최종결과는동일 키내부의비트패턴자체가삽입위치를결정 S 와 R 처럼여러비트에걸쳐비트패턴이같아지면트리가한쪽으로만분기 (One-Way Branch) 되어균형이무너짐. 빈외부노드가다수발생하여공간적효율이저하됨. 11
다중링크트라이 다중링크트라이 하나의노드에서뻗어나가는링크의숫자를 M 으로늘림으로써높이를줄임 예를들어, 링크를 4 개로놓고비트패턴 00 이면가장왼쪽, 01 이면그오른쪽 해시보다더좋은효율을보일수도있음. 해시에서키를구성하는모든요소를검사. 트라이는키일부만검사하고도원하는레코드를찾아갈수도있음. [ 그림 12-6] 다중링크트라이 12
다중링크트라이공간낭비의우려 레벨 1에서 1개, 레벨 2에서 4개의노드가존재하면레벨 3에서 4 2 = 16 리프노드근처에지나치게많은외부노드. 미사용으로인한공간낭비루트근처에서는 M을크게하고, 리프근처에서 M을작게하여효율을개선 13
탐색의효율 Section 06 해시 - 해시함수의필요성 O(lgN) 의탐색효율이라면 100,000 개의레코드중하나를찾는데필요한비교의횟수는 lg100,000 17. 매우빠른알고리즘. 그러나이속도도느릴수있음. 119 데이터베이스라면비상시전화접속즉시주소확인. 예 : 실시간응용프로그램에서는검색속도가결정적. 해시 효율면에서근본적인차이를지향한다. O(logN) 이아니라 O(1) 을지향 데이터개수 N 과무관하게단번에찾아내겠다는것 주어진키를사용해서실제레코드의주소를직접적으로계산해내는것을해시라고함. 배열을사용한다면이주소는배열의인덱스를의미 해시함수를가하여채운도표를해시테이블 (Hash Table) 이라함. 14
해시함수 해시함수 = 인덱스계산기 [ 그림 12-7] 인덱스계산기 15
전화번호키 충돌 445-3800 이라는전화번호를키로하는레코드키자체를인덱스로하여이레코드를 T[4453800] 에저장이경우의해시함수는자체매핑 (Identity Mapping) 메모리크기는제한적이므로배열인덱스의범위를줄일필요가있음. 같은동네라면국을생략 T[3800] 에저장. 이경우해시함수는 4453800 에서 3800 으로가는매핑. 스트리핑 (Stripping) 메모리크기인덱스 0...999 로매핑. 전화번호의처음네자리를떼어버리면 T[800] 에 445-3800 이나 445-7800 이나모두동일한인덱스로매핑충돌 (Collision) 서로다른키에해시함수를가한결과동일한인덱스로매핑되는현상 메모리에여유공간이있음에도불구하고, 해시함수자체의특성으로인해발생 16
자릿수선택 (Digit Selection) 해시함수 일부자릿수만골라냄. 13 자리주민등록번호중홀수자릿수만선택. h(8812152051218) = 8112528 만약처음네자리를선택하면출생년월이같은사람들은모조리충돌 자릿수접기 (Digit Folding) 각각의자릿수를더해버리는방식. h(8812152051218) = 8 + 8 + 1 +... + 8 = 44 메모리인덱스의범위는 0 h(key) 0 9*13 = 117 의사이에존재메모리가더크면 h(8812152051218) = 88 + 12 + 15 +... + 8 방식도가능 모듈로함수 (Modulo Function) h(key) = KEY mod TableSize. Key 를해시테이블크기로나눈나머지를인덱스로. 해시테이블크기로나눈나머지는항상그보다작으므로반드시인덱스 0..(TableSize-1) 안으로매핑됨. 1236 % 100 이나, 3636 % 100 이나모두동일한인덱스로매핑 충돌을최소화하기위해서 TableSize 숫자의선택에유의. 통계에의하면이숫자는소수 (Prime Number) 로하는것이유리함. 17
문자열키자릿수접기 문자값은 ASCII 코드값을할당 EACH = 69 + 65 + 67 + 72 = 273, WALL = 87 + 65 + 76 + 76 = 304 코드 12-2: 문자열폴딩 I int HashByFold(stringClass Key) { int HashVal = 0; for (int i=0; i < Key.Length( ); i++) HashVal += Key[i]; return HashVal } 18
문자열키 자릿수접기코드 12-3: 문자열폴딩 II int HashByFold(stringClass Key) { int HashVal = 0; for (int i=0; i < Key.Length( ); i++) HashVal = HashVal << 3 + Key[i]; return HashVal } << 비트쉬프트연산자 (Bitwise Left Shift Operator) 비트열을왼쪽으로 3 비트이동이전 HashVal 에다가 8 을곱한다음에그다음문자값을더함. 문자마다 8 진법형태의자릿수가있다고전제 ABC 라는문자열을 'A *8 2 + 'B * 8 + 'C' 로간주. 이방식으로 KIM 이라는문자열을 10 진수로나타내면 K * 10 2 + I * 10+ 'M' 이됨. 19
호르너규칙 긴문자열키 HWANG" = 8 * 10 4 + 23*10 3 + 1*10 2 + 14*10 + 7 곱셈의횟수는총 10 번 호르너규칙 ((((8 *10 + 23)*10 + 1)*10 + 14)*10) + 7 로변형곱셈의횟수는총 4 번. 연산속도향상. 부동소수점연산일경우에는계산결과의정밀도향상 정수오버플로우숫자가너무커질경우. 95 % 7 = ((7 + 2)*10 + 5) % 7 = (2 * 10 + 5) % 7 로변환 7 이라는인수에 10 이나다른수가몇번곱해지건간에 7 로나누어떨어지므로모듈로계산의결과에아무런영향을주지못함. 긴문자열의모듈로 ( 예 : HWANG ) 먼저 8 을 7 로나눈나머지 1 만취한다. 여기에그다음숫자인 23 을붙여서 123 을만든다. 이를 7 로나눈나머지인 4 만취한다. 여기에그다음숫자인 14 를붙여서 414 를만든다. 이를 7 로나눈나머지인 1 만취한다. 여기에그다음숫자인 7 을붙여 17 을만든다. 이를 7 로나눈나머지인 3 이전체키에모듈로 7 을가한결과가된다 20
충돌해결방법충돌 어떤해시함수를사용하든피해갈수없는문제해결책 (Collision Resolution) 이필요. 충돌해결방법 열린어드레싱 (Open Addressing) 충돌이일어나면자기자리가아닌곳으로들어갈수있도록허용 다른키를가진레코드가해시되어들어가야할자리까지도오픈 선형탐사, 제곱탐사, 이중해시 닫힌어드레싱 (Closed Addressing) 자기자리가아니면절대로못들어가게함 버켓, 별도체인 21
선형탐사 (Linear Probing) 충돌이일어나면그다음빈곳 T[h(KEY)] 가점유되어있을때, T[h(KEY) + 1], T[h(KEY) + 2],... 의순서로빈곳이있을때까지찾아감. 배열의끝을만나면다시처음으로되돌아와서거기서부터빈자리를찾음 h(key) = h % 31 선형탐사 [ 그림 12-8] 선형탐사 22
필요성 선형탐사의태그 65, 34, 127 까지들어간상태에서키 34 인레코드를삭제. 인덱스 4 의위치는빈칸이후, 키 127 을가진레코드를탐색시, 인덱스 4 가 빈칸이니찾는레코드가없다 라고결론지을수는없음. 인덱스 5 에찾는레코드가있기때문. 배열아이템을세가지상태로분류 사용중 (Occupied), 삭제됨 (Deleted), 미사용 (Empty) 탐색도중미사용칸을만나면탐색을중지하고찾는레코드가없다고결론탐색도중삭제됨칸을만나면탐색을계속함. [ 그림 12-8] 선형탐사 23
선형탐사의최대단점 클러스터현상 클러스터 (Cluster, 군집, 群集 ) 현상선형탐사의클러스터는 1 차클러스터 (Primary Cluster) 클러스터 = 레코드가분산되지않고떼지어몰려다님키 34 인레코드는사실상 34 % 31 = 3 에들어가야할레코드가오른쪽에밀린것이고, 키 127 인레코드도사실은 127 % 31 = 3 에들어가야하는레코드 [ 그림 12-9] 1 차클러스터 24
선형탐사의최대단점 클러스터현상 97, 170 삽입 : 인덱스 3, 4, 5, 6, 7 로이어지는클러스터가형성어떤레코드의해시결과가이인덱스범위안으로들어오기만하면그레코드는클러스터끝에가서붙고, 클러스터의크기는하나증가클러스터가커짐으로인해이제어떤레코드가클러스터안으로해시될확률이더높아짐. 이런식으로클러스터는급속도로팽창한다 [ 그림 12-9] 1 차클러스터 25
해시테이블의부담 부하율 부하율 ( 負荷率, Load Factor) λ(lambda) 테이블크기 M, 레코드개수 N 일때부하율 λ = N / M 테이블크기가클수록, 또레코드수가적을수록부하율은낮아짐. 부하율이커질수록클러스터가형성될확률이높아짐 크누스 (Knuth, 1962) 선형탐사의삽입시비교회수는 (1 + 1/(1-λ)2)/2 에, 탐색시비교회수는 (1 + 1/(1-λ))/2 에접근따라서부하율이 1 에가까울수록비교회수는급증테이블크기 M 을늘리면배열의빈공간이많아져메모리가낭비 M 이너무작으면작은클러스터끼리서로붙어큰클러스터가형성선형탐사에서 M 2N 정도로할때대략상수시간 (Constant Time) 에삽입과탐색이가능 26
제곱탐사 (Quadratic Probing) 제곱탐사 충돌이일어날때바로그뒤에넣지않고조금간격을두고삽입 T[h(KEY)] 가점유되어있을때, T[h(KEY) + 1 2 ], T[h(KEY) + 2 2 ], T[h(KEY) + 3 2 ],... 의순서로제곱간격을두고빈곳을찾아감. 정확하게는 T[h(KEY) + K 2 ] % M 이다음찾을인덱스위치 65, 34, 127 의삽입 h(key) = h % 31 65 인레코드가인덱스 3 으로들어감. 키 34 인레코드가인덱스 3 으로해시어충돌. 1 의제곱은 1 이므로이레코드는인덱스 4 로키 127 인레코드가역시인덱스 3 으로해시됨. 이후 4, 7, 2 순으로탐사 [ 그림 12-10] 제곱탐사 27
제곱탐사와클러스터 제곱탐사의빈칸중간에빈칸을두는이유는그곳으로해시되는레코드들이들어갈공간을비워둠으로서오른쪽끝에가서붙는클러스터를방지인덱스 5 나 6 으로해시되는레코드는끝으로밀려나지않고제자리를찾아먹음. 빈공간을찾는순서가 2, 3, 4 의제곱으로점프하므로사이에넓은공간이확보됨. 만약두개의레코드가같은키로해시되면비록띄엄띄엄하기는하지만같은위치를반복해서찾아가게됨. 158 을키로하는레코드를삽입하려면인덱스 3, 4, 7, 12, 0 등정해진순서를따라감. 이들인덱스에있는레코드들만으로볼때는여전히클러스터된상태이며이를 2 차클러스터 (Secondary Cluster) 라함. [ 그림 12-11] 2 차클러스터 28
1 차클러스터, 2 차클러스터 개념상차이인덱스 X 로해시될레코드가충돌에의해 Y 로밀려나면 X, Y 가클러스터를형성 X, Y 둘중하나로해시되는모든것이클러스터되는것이 1 차클러스터 X 로해시되는레코드는다음빈곳을찾기위해동일한곳을찾아나가기때문에그순서를따라서형성되는클러스터가 2 차클러스터 2 차클러스터 1 차클러스터보다는완화된모습인덱스 4 로매핑되는레코드는 4, 5, 8, 13 의순으로다른인덱스순서를따름 [ 그림 12-11] 2 차클러스터 29
이중해시이중해시 (Double Hash) 제곱탐사의단점인 2차클러스터를방지선형탐색과제곱탐색에서의탐사순서가키값과는무관하게규칙적키값에따라서탐사순서를달리함으로써탐사순서의규칙성을제거두개의해시함수 h1, h2를사용 h1은주어진키로부터인덱스를계산하는해시함수 h2는충돌시탐색할인덱스의간격 (Step Size) 을의미 [ 그림 12-12] 해시이전의배열 30
h1 = KEY % 13, h2 = 1 + KEY % 11 키 14 인레코드의삽입 14 % 13 = 1 에서충돌. (1 + (14 % 11)) = 4 를간격으로탐사순서는 1, 5, 9, 0 으로진행. 인덱스 0 에서빈곳을찾았으므로거기에삽입키 27 인레코드의삽입 27 % 13 = 1. (1 + (27 % 11)) = 6. 탐사순서는 1, 7, 0, 6 인덱스 6 에삽입키 18 인레코드의검색 18 % 13 = 5. (1 + (18%11)) = 8. 탐사순서 5, 0, 인덱스 0 에서빈곳이므로그런레코드없다고결론. h2 함수의선택 이중해시 어떤키에대해서도 h2 의결과는 0 이되어서는안됨. 0 이면계속같은자리에서찾는꼴 h1 과동일한함수여서는안됨. 모든키에대해서간격이같아지기때문. 2 차클러스터를제거. 그러나두개의해시함수를계산해내는데따른시간적손실을전제로함 31
선형탐사, 이중해시 선형탐사, 이중해시 선형탐사 이중해시 부하율 50% 66% 75% 90% 탐색 1.5 2.0 3.0 5.5 삽입 2.5 5.0 8.5 55.5 탐색 1.4 1.6 1.8 2.6 삽입 1.5 2.0 3.0 5.5 [ 표 12-6] 부하율에따른선형탐사와이중해시의효율비교 32
버켓버켓 (Bucket) 배열요소가다시여러개의요소로이루어짐이경우자료구조는배열의배열 (Array of Array) 로서 2차원배열충돌되는레코드를하나의인덱스안에둘수는있음해당인덱스로가서다시키가일치하는레코드를찾아야하는시간적부담사용되지않는배열공간이낭비됨 [ 그림 12-13] 배열의배열 33
별도체인 (Separate Chaining) 별도체인 배열요소가연결리스트를가리키는헤드일명분산테이블 (Scatter Table) 충돌이일어날때마다해당레코드를연결리스트의첫위치에삽입동적구조 (Dynamic Structure) [ 그림 12-14] 별도체인 34
별도체인의효율 체인의길이에비례 별도체인 평균적으로체인길이는부하율 (N/M) 과동일 부하율 λ 일때별도체인에서의평균키비교회수는 (1 + λ/2) 부하율 1 이하의별도체인에서는상수시간삽입및검색이가능 노드공간을할당하는함수를불러야하는시간, 포인터를따라가는시간, 포인터변수자체가차지하는공간을요함 버켓과별도체인 닫힌어드레싱 해시된인덱스안에서다시배열이나연결리스트등의또다른자료구조를사용함으로써충돌을해결 35
유니버설해시좋은해시함수 레코드를메모리공간에골고루분포시킴으로써충돌을최소화입력데이터패턴과무관하게이러한특성을보여야함. 그러나실제로이런함수를만들기가어려움 유니버설해시 다양한해시함수를준비해놓고선택적으로사용 해시함수의선택은랜덤 (Random) 하게이루어짐. 응용프로그램이시작할때하나를골라서끝날때까지사용 유니버설 (Universal, 보편적 ) 테이블크기 M 일때, 서로다른키가같은인덱스로매핑될확률이 1/M 이하인해시함수 36
재해시재해시 ( 再해시, Rehash) 삽입이계속되면부하율이일정한계를넘음부하율을낮추는테이블크기 M을키우는것. 힙공간에동적배열생성한꺼번에기존테이블의 2 배크기의배열을생성이전데이터를복사 재해시를가하는시기 테이블이반정도찰때부하율이미리정해진어떤값을넘을때삽입이실패할때 37
판매촉진아이디어 Section 07 자료구조의선택 - 자료구조의선택 아이디어가제기되는순서대로리스트에삽입정렬된순서로탐색할필요가없음. 정렬안된배열이나연결리스트가유리배열이라면배열의마지막에, 연결리스트라면연결리스트의처음에삽입배열이라면대략적으로최대몇개의아이디어가나올것인가를예측 문서편집기의사전기능 삽입이나삭제는거의없음, 탐색작업이위주정렬된배열의이진탐색에의해 O(lgN) 의효율균형잡힌이진탐색트리를구성해놓으면효율은 O(lgN) 삽입, 삭제가거의없으므로한번균형잡힌트리의모습이변형되지않음정렬된연결리스트 : 이진탐색이어려움 38
도서관의문헌카탈로그 자료구조의선택 탐색위주. 사서에의한삽입, 삭제도적지않음정렬된배열은이진탐색에의해 O(lgN) 의효율정렬된배열은삽입, 삭제에있어서크게불리. O(N) 의이동때문. 정렬된연결리스트에서평균적으로 N/2 의위치에서찾으므로대략 O(N). 정렬된연결리스트에서삽입삭제는앞뒤포인터만조정하므로 O(1). 정렬된배열이유리한가정렬된연결리스트가유리한가. 이진탐색트리가 O(lgN) 으로서최적의효율을보임. 균형트리에가까울수록탐색에 O(lgN) 에가까워짐. 삽입삭제에걸리는시간은인근노드의포인터만조정하면되므로 O(1) 39
선택기준 ( 예시 ) 자료구조의선택 활용할수있는컴퓨터의시간적, 공간적리소스가충분한가. 입력데이터의크기와특성및분포는어떠한가. 삽입삭제검색중어떤것이가장많이이루어지며그작업이얼마나빨리이루어져야하는가. 결과데이터가정렬될필요성이있는가없는가. 데이터를순차적으로접근하는가아니면랜덤한순서로접근되는가 40
Thank you 41