d라이브러리

견우가 이제 제가 없는데도 차츰 알고리듬으로 문제를 해결하려고 하네요! 비록 문제를 맞힌 건 최강이지만 이 정도면 아주 성공적이에요. 그럼 최강이 말한 ‘탐색 알고리듬’이 뭔지 상세히 설명해 줄게요.

우리 디지털 세계에는 세상의 모든 책을 모아 놓은 커다란 도서관이 있어요. 여러분이 원하는 어떤
책이든 읽을 수 있죠. 그런데 책이 많아도 너무 많아 찾기가 어렵다는 문제가 있어요. 검색대 조차
없다면 어떤 방법을 쓰면 될까요?

이럴 때 사용하는 방법이 검색대에 쓰이는 알고리듬인 ‘탐색 알고리듬’이에요. 현대 사회에서는 수
많은 정보 중 원하는 정보를 얼마나 빨리 정확하게 찾아내느냐가 중요한 기술이죠. 예를 들어 어
떤 사이트에 로그인할 때 내가 입력한 아이디를 데이터베이스에서 탐색하고 일치해야 들어갈 수 있는데요. 몇백만 명이 이용하는 사이트에서 내 정보를 찾는 일이 굉장히 오래 걸린다면 아무도 그 사이트를 이용하지 않을 거예요. 다시 도서관으로돌아가 보죠. 만약 수학동아를 찾고 싶은데 책이
가나다순으로 정리돼 있다면 굳이 첫 칸부터 볼 필요 없이 ‘ㅅ’으로 시작하는 책장으로 바로 가면 돼요. 책이 정리돼 있지 않고 무작위로 꽂혀 있다면 차례대로 책장을 확인하는 것이 나을 거고요.
이렇게 정보가 어떻게 배열돼 있는지에 따라 탐색하는 방법도 여러 가지예요. 앞에서부터 차례대로 데이터를 찾는 방법은 ‘선형 탐색’, 정렬된 데이터를 반씩 나눠 비교하는 방법은 ‘이진 탐색’이라고하죠. 이진 탐색은 단순히 순서를 따라 데이터를 찾는 선형 탐색에 비해 무척 효율적이에요. 100개의 데이터가 있을 때 앞에서부터 순서대로 찾으면 최대 100번을 확인해야 하지만 이진 탐색을 쓰면 최대 7번 만에 원하는 정보를 찾을 수 있거든요.

이진 탐색을 쓰면 n개의 원소로 이뤄진 배열에서는 최대 log₂n만에 답을 찾을 수 있어요. 이것이
이진 탐색 알고리듬의 ‘실행 시간’이고, 실행 시간은 알고리듬의 효율성을 따지는 데 아주 중요한 요소예요. 오늘은 이진 탐색의 기본 원리를 먼저 익혀보고 다음 시간에 알고리듬의 실행 시간에 대해 더 자세히 알려드릴게요!

참고자료

박우창 ‘검색(search)’, 이시다 모리테루, 미야자키 쇼이치 ‘알고리즘 도감’, 아디트야 바르가바 ‘Hello
Coding 그림으로 개념을 이해하는 알고리즘’