Do it 자료구조 책을 보고 정리

검색 알고리즘

데이터 집합에서 원하는 값을 가진 요소를 찾으려면 검색 알고리즘에 대해 알아야 한다. 주소록을 검색한다고 가정하면 다음 처럼 찾아 볼 수 있다.

1. 국적이 한국인 사람을 찾는다.
2. 나이가 21세 이상 27세 미만인 사람을 찾는다.
3. 찾으려는 이름과 가장 비슷한 이름의 사람을 찾는다.

위처럼 무언가 검색을 할 때 특정 항목에 주목을 하게 되는데 그 항목을 ‘키’라고 한다. 위의 키값은 이러하다.

1. 키 값과 일치하도록 지정(한국)
2. 키 값의 구간을 지정(21세 이상 27세 미만)
3. 키 값과 비슷하도록 지정(발음이 가장 비슷한 이름)

이러한 조합들을 논리곱이나 논리합을 사용해서 더 복합적으로도 사용할 수 있다.

검색의 종류

검색의 종류는 보통 이러하다.

1. 배열 검색
2. 선형 리스트 검색
3. 이진검색트리 검색

지금 알아 볼 것은 배열 검색이다. 배열 검색은 말그대로 배열을 활용하는 기법이고, 아래의 알고리즘을 활용한다.

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

여기서 그냥 아무거나 갖다 쓰면 되지 않을까 생각하지만, 경우에 따라 적절한 알고리즘을 가져다 써야 한다. 만약에 추가, 삭제가 빈번히 일어나는 환경인데 검색속도만 빠른 알고리즘을 쓰면은 낭패가 발생하기 때문이다.

선형 검색

배열을 활용한 선형 검색을 해보도록 하겠다. 선형 검색은 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다. 그렇기에 선형 검색(linear search) 또는 순차 검색(sequential search)라고 한다. 예를 들어 아래와 같은 배열이 있다. 여기서 내가 2를 검색한다 가정해보자. 6 4 3 2 1 3 8 그러면 6부터 시작해서 4, 3 순으로 비교하고 3번 인덱스에 있는 2를 발견하면 검색을 성공하고 종료하게 된다. 만약 내가 배열에 없는 값 9를 찾는다면 배열의 끝까지 가고 종료하게 된다. 선형 검색의 종료 조건은 2개가 있고, 하나라도 성립하면 검색이 종료된다.

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견할 경우