Page 96 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

는 방법입니다. b 의 선형 리스트에서의 검색은 09장에서, c 의 이진검색트리에서의 검색은

10장에서 소개합니다. 또 그림 3-1에는 없지만 문자열에서 일부 문자열을 검색하는 기법도
있습니다. 이 내용은 08장에서 배웁니다.

a 배열 검색
6 4 3 2 1 9 8

2를 검색

b 선형 리스트 검색

64 23 53 65 75 21

53을 검색
c 이진검색트리 검색
5
2 7
1 4
3 4를 검색
[그림 3-1] 검색이란 어떤 조건을 만족하는 데이터를 찾는 것입니다.

이 장에서 학습하는 내용은 a 의 ‘배열 검색’이며 구체적으로 다음의 알고리즘을 활용합니다.

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.
2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.
3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다.
•체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
•오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

데이터 집합이 있을 때 ‘검색만 하면 되지!’라고 생각한다면 검색에 사용할 알고리즘은 계산
시간이 짧은 알고리즘을 선택하면 됩니다. 그러나 데이터 집합에 대한 검색뿐 아니라 데이터
의 추가, 삭제 등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가

하여 알고리즘을 선택해야 합니다. 예를 들어, 데이터 추가를 자주하는 경우에는 검색이 빠르
더라도 데이터의 추가 비용이 많이 들어가는 알고리즘은 피해야 합니다.

96 C 알고리즘