탐색 알고리즘

1. 탐색이란?

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 검색 엔진은 탐색 알고리즘을 사용하고 있는 거죠.

2. 탐색의 종류

1) 선형 탐색(리니어 서치) - O(N)

한쪽 끝에서 다른 한쪽 끝으로 순서대로 하나씩 확인해 나가는 것. 아무 생각도 요령도 필요없이 그냥 하나씩 확인해가면 된다. 대표적인 방법으론 반복문을 사용하는 것이다. 찾는 대상이 탐색을 시작하는 쪽에 가까우면 짧은 시간에 탐색할 수 있지만 반대인 경우 혹은 데이터가 없는 경우는 비효율적이다. 단순, 구현이 쉽지만 효율은 낮다.

 

2) 이진 탐색(바이너리 서치) - O(logN) 보장

이진탐색은 데이터가 미리 오름차순, 내림차순으로 정렬되어 있는 경우에 사용할 수 있다. 특정 데이터를 찾기 위해서 범위를 반으로 좁혀서 탐색하는 것. 선형탐색보다 평균적으로 이진 탐색이 빠르다. 하지만 상황에 따라 달라지니 고민해보고 선택

 

- 가운데 있는 요소를 먼저 탐색하고

- 조건이 가운데 요소보다 정렬순서가 빠른지 느린지를 보고, 탐색범위를 좁힌다.

- 좁힌 탐색 범위의 가운데를 다시 탐색, 정렬순서를 확인한다.

- 찾을 때까지 이 작업을 반복한다.

 

2-1) 파라메트릭 서치

최적화 문제를 결정 문제(예, 아니오)로 바꾸어 해결하는 기법. 예로, 특정한 조건을 만족하는 가장 알맞는 값을 빠르게 찾는 최적화 문제는 이진 탐색방법으로 해결할 수 있다. 특정 조건이 현재 범위에서 만족하는가? 아닌가? -> 탐색 범위 좁혀나가기.

 

3) 해시 탐색 - O(1), 해시 충돌의 경우 O(N)

앞의 선형, 이진 탐색은 어떤 데이터가 어떤 요소에 들어 있는지 전혀 모르는 상태에서 검색을 시작한다는 것이다. 하지만 해시 탐색법은 데이터의 내용과 저장한 곳의 요소를 미리 연계해둬서 짧은 시간 안에 탐색할 수 있도록 고안된 알고리즘이다. 다시 말해서, '데이터'를 '데이터와 같은 첨자의 요소'에 넣어두면 한 번에 찾을 수 있다는 아이디어에서 출발한 것이다. 10이라는 데이터는 첨자 10의 요소에 넣어둔다는 것.

 

문제는 100개가 '예상되는 데이터'를 단 2개만 저장하려고 해도 100개를 위한 저장공간을 만들어야 한다는 것. 공간 낭비가 심하다. 이 문제를 해결하기 위해서 좀 더 머리를 쓸 수 있다. 10을 저장하기 위해서 1부터 100까지의 공간을 만들지 않고, 100을 10으로 나누면 1이기 때문에 1~10까지의 공간만 만들고 매번 10을 나눠주는 방식으로 10을 저장할 수 있다. 즉 함수를 이용해서 적절한 값을 적절한 공간에 저장할 수 있다. 이렇게 어떤 값이 주어진 경우 그 값을 대표하는 숫자를 계산하는 함수 == 해시 함수. 해시 함수에 의해 산출된 값 == 해시값. 해시라는 단어는 잘게 썬다, 잘게 다른다는 의미인데 원래의 숫자를 변형해서 전혀 다른 값을 생성한다 정도로 이해하면 될 것 같다.

 

해시 탐색은 실행하기 위해서는 데이터의 저장 및 검색, 2개의 알고리즘이 필요하다.
- 먼저 해시 함수를 사용하여 데이터를 저장하는 알고리즘

- 저장을 했다면 탐색하는 알고리즘