알고리즘 - Search 기초개념

어떤 알고리즘을 사용해야 검색이 빠른지 알아보자.

어떤 자료구조를 사용해야 하는지 배워야 하는 것처럼 어떤 알고리즘을 어떤 상황에 사용해야하는지,

자료구조와 알고리즘의 조합이 어떤게 가장 효율적인지 공부해야한다.

검색 관련 패밀리 종류

1. Binary Search (이진검색)
2. Linear Search (선형검색)

다른 종류로는 Sort (정렬)알고리즘이 있다.

먼저 선형검색 (Linear Search)는 가장 검색을 하기 위한 '자연스런' 방법일 수 있다.

선형검색은 자료를 나열해놓고, 0번째 인덱스부터 하나씩 차근차근 찾는값과 일치한지 확인하면서 넘어간다.

이런 선형검색의 최악의 경우는 찾는 값이 없거나, 마지막 위치에 있을 경우 이다.

이말인즉슨, 배열이 커지면 커질수록 선형검색을 하는 시간 또한 길어지게 된다.

 

이걸 Linear Time Complexity (선형 시간복잡도) 라고 한다. 즉 인풋이 많을수록 수행하는 시간 역시 선형적으로 증가한다는 이야기 이다.

 

이것의 발전된 형태가 바로 Binary Search (이진검색) 알고리즘이다. 하지만 모든 배열에 이진검색 알고리즘을 사용할 수 있는 것은 아니다. 이진검색 알고리즘을 사용하려면 Sorted Array(정렬된 상태의 배열)에서만 사용이 가능하다.

 

이처럼 어떤 알고리즘은 특정 자료구조에서만 사용이 가능하다. 만약 정렬인 안된 배열에서 이진검색을 수행할 경우 오히려 선형검색보다 더 오랜시간이 걸릴 가능성이 높다. 그렇기 때문에 이진검색 알고리즘의 경우 정렬이 수행된 다음 사용해야 효율성이 높다.

 

하지만 무조건 정렬된 배열이 성능이 좋다는 것은 아니다. Insert(삽입) 의 경우 정렬이 안된 배열에서는 빈칸이 있는 경우 마지막칸에 추가만 하면 되기때문에 step 이 적다.

그런데 정렬된 배열의 경우 삽입할 값이 첫번째 인덱스부터 비교해야 하고, 차근차근 비교하다가 조건과 일치하는 위치에 삽입되고 그 오른쪽으로 다른값들을 옮겨야하기에 많은 단계를 거치게 된다.

 

그러면 Binary 란? 절반의 위치 즉 정 가운데에서부터 찾기 시작한다.

그러면서 내가 찾는값 n 이 중간에서 작은값인지, 큰 값인지 비교하여 한칸씩 왼쪽, 오른쪽으로 다시 중간값의 위치로 이동하며 반대쪽 절반의 값을 가진 배열은 배제하게 된다.

 

이렇게 이진검색은 거대한 배열을 다룰 때 효율적으로 사용할 수 있다.

하지만 정렬된 배열에서만 효율적인 사용이 가능하기 때문에 자료구조와 알고리즘의 이해관계를 알아야 한다!

정렬된 배열(자료구조) 와 이진검색(알고리즘)의 연결 관계처럼 다양한 자료구조와 알고리즘의 이해도가 높아야한다!!