알고리즘 라이프 - 선형탐색과 이진탐색

 

 

 

<알고리즘 라이프>는 알고리즘 개념을 일상 속 문제해결 상황에 적용해 쉽게 설명한 책이다. 처음보는 다양한 알고리즘이 등장하는데, 그 중 나는 내가 최근에 공부한 SQL 인덱스 검색과 비슷한 2장의 내용을 쉽고 흥미롭게 읽었다.

 

2장에서 배운 알고리즘 개념을 내가 알고있던 내용과 연결지어 쉽게 이해하고 싶어서 새로운 개념을 정리하며 읽었다. 여기서 새로 알게 된 개념은 선형탐색과 이진탐색, 선형시간과 로그시간이다.

 

이야기는 주인공이 폭탄세일을 진행하는 백화점 문이 열리자마자 사이즈에 맞는 셔츠를 모두 쓸어담아서 빠르게 나오는 방법을 찾는 내용이다. 셔츠가 몇 장 없다면 진열된 셔츠를 왼쪽부터 오른쪽까지 순서대로 하나하나 찾아보는 선형탐색 방법을 사용하면 된다. 하지만 셔츠가 엄청나게 많다면 선형탐색 방법은 하나하나 확인하느라 선형시간이 소요되어서 빠르게 세일현장을 나오려는 목표를 달성하기 어려워진다. 이 선형탐색 방법이 SQL에서 정렬되지 않은 데이터를 처음부터 끝까지 검색하는 풀스캔 방법과 같은 내용이었다.

 

만약 아주 많은 셔츠들이 사이즈별로 정렬되어있다면 이진탐색 방법을 활용해 빠르게 원하는 사이즈를 찾을 수 있다. 이진탐색은 정렬된 데이터를 계속 반으로 쪼개서 비교를 통해 방향을 정하고 원하는 데이터를 찾아나간다. 여기에 n에서 시작해 마지막 하나 남은 자료에 이르기까지 반복적으로 반으로 나누는 횟수를 뜻하는 수학함수 로그의 개념이 적용되어 있다. 마지막 하나가 남으면 비교값 일치여부에 상관없이 탐색이 끝나기 때문에 배열의 최대 이진탐색 횟수는 2를 밑으로 하는 log n = m + 1의 값이 된다. 이 내용 또한 SQL 의 인덱스가 자료를 찾아내는 트리인덱스 방법과 같은 내용이라는 걸 알게되었다. 나는 이제 정렬되어 있는 n개의 자료가 있다면 최대 m+1번만에 원하는 자료를 찾을 수 있다는 걸 미리 예측할 수 있는 능력이 생겼다.

 

이 책을 읽고 로그의 개념부터 이해하고자 칸아카데미의 대수학2 - 로그 강의를 들었고 여기에 수학과 알고리즘에 관한 훌륭한 강의가 많다는 걸 발견했다. 앞으로 매주 주말 오전을 활용해 알고리즘 강의를 하나씩 듣고 알고리즘 카테고리를 만들어서 배운내용을 정리할 계획이다.