[Algorithm] 이진 검색과 대 선형 검색

---

알고리즘을 조금씩 알아가게 되면서 깨닫게 된 것은 우리는 일상에서도 알고리즘을 사용하고 있다는 것이다. 특히 알리 알모사위의 "알고리즘 라이프"를 읽으면서 프로그래머스의 알고리즘 문제를 풀 때보다 알고리즘이 쉽게 다가왔다. 나는 1달 전까지만 해도 알고리즘은 본 적도 없었다. 수학, 통계와 관련된 수업에서 항상 낙제점을 받아서 그런지 더욱 기피하게 되었다. 하지만 책을 읽으면서 알게된 알고리즘은 우리가 겪는 문제를 해결하기 위한 가장 빠른 길을 알려주는 기술이라고 느껴진다. 마치 미리 같은 문제들로 고생한 선배들이 남긴 족보와 같다고 느껴진다. 이번 글에서는 내가 이해한 알고리즘이 중요한 이유를 가볍게 설명해보려고 한다.

---

일상에서 문제를 해결하는 방법

우리는 살아가면서 다양한 문제를 마주하게 된다. 특히 살아오면서 '정리'라는 문제를 자주 마주하게 된다. 옷장 정리, 서랍 정리, 서류 정리, 문서 정리, 물건 정리... 등등 다양한 정리를 하면서 우리는 살아간다. 처음으로 '정리'라는 문제를 마주한다면 사람은 생각하게 된다. 어떻게 하면 이 문제를 해결할 수 있을까?

일반적으로 사람들은 '순서'라는 기준으로 문제를 정리한다. 정렬을 통해서 문제를 해결하기 위한 준비를 하는 것이다. 이렇게 정렬이 된 문제들을 보고 하나 씩 검색하는 것을 선형 검색이라고 한다. 그런데 정렬된 문제들을 해결하는 방법 중이는 선형 검색보다 훨씬 빠른 이진 검색이 있다.

---

이진 검색과 선형 검색

하나 씩 확인해야 했던 선형 검색과 다르게 이진 검색은 조건을 통해 검색하게 된다. 문제들이 정렬되어 있다는 가정하에서, 어떠한 값을 찾고 싶다면 처음부터 찾는 것이 아니라, 가운데 값을 통해서 찾게 되는 것이다. 우리가 흔히 하는 UP&DOWN게임 혹은 스무고개와 같은 개념이다. 이렇게 중간 지점을 찾게 되면 우리는 하나씩 확인하는 선형검색의 과정보다 훨씬 빠르게 정답에 도달 할 수 있다.

이를 좀더 정리해서 이야기하자면 선형 검색은 100개의 문제가 있다면 원하는 정답을 찾기 위해 100개의 단계를 거쳐야 한다. 그 말인 즉슨 원소의 수만큼의 단계가 필요하단 말이다. 만약 그 수가 억개를 넘는다면? 엄청난 과정의 연산을 지나야 하는 것이다.

하지만 이진 검색은 문제들의 개수를 두배로 늘릴 때마다 단계 수가 하나씩 증가한다. 계산해 보자면 10,000개인 배열에서 선형 검색은 최대 10,000단계를 지나야 하지만 이진 검색은 최대 13번의 단계로 해결이 가능하다. 크기가 1,000,000개인 배열에서 선형검색은 1,000,000번의 단계가 필요하지만 이진 검색은 최대 20단계면 가능 하다는 것이다.

---

결론

이처럼 모든 문제와 상황에 따라 각각의 알고리즘이 필요하다는 것을 알 수 있게 된다. 그렇다면 최선의 방법으로 문제를 해결하기 위해서는 그 문제를 해결하기 위한 가장 빠른 길, 알고리즘을 알아야 한다는 것이다. 매번 사고를 하여 고민을 하면서 시간을 투자하여 문제를 해결하는 것이 아닌, 정리된 가장 빠른 길을 찾아 갈 수 있게 된 것이다.

너무나 많고 다양한 알고리즘들은 어렵고 힘들지만, 그 길을 먼저 갔던 사람들에 비해선 편한 길이란걸 잊지 말자. 화이팅 :)