어쩌면 알고리즘 문제는 시간 복잡도와의 싸움일 수 있겠다 싶을정도로 많은 제약이 있다.
그냥 사고의 흐름대로 for문을 중첩으로 사용하여 문제를 해결하면 참 좋겠지만...
많은 문제들이 입력 data를 10만개에 육박하게 주는 경우가 많다.
이럴 경우 우리는 어떤 방법을 통해 문제를 해결해야할까?
그 답중에 하나가 이진탐색이 될 수 있다.
사실 우리는 Up & Down 게임을 통해서 이미 이진탐색을 경험했고 아주 잘 사용하고 있다.
실생활 예를 들어보면, 1 부터 10까지의 숫자 중에 하나를 골라 본인만 알고 있자.
그랬을 때 10번 만에 그 숫자를 맞춰 보려한다면, 우리는 본능적으로 첫 정답을 5이라고 말할 것이다.
(여기서, 정답을 알고 있는 사람이 Up 또는 Down을 알려주면 범위는 2배정도 줄어들기 때문이다.)
만약 Up이라고 했으면 우리는 그 다음 정답을 7라고 말하며 또다시 범위를 줄여나갈 것이다.
지금까지 설명한게 바로 이진탐색이다.
(한자로 명명하여 어렵게 느껴진다.. 이름을 up & Down 탐색이라고 하면 좋았듯하다..)
위와 같은 배열이 있다고 가정했을 때 0번방 부터 10번방까지 돌아다니며 원하는 값을 찾을 수 있겠지만
배열의 크기가 100만이라하면 매우 불편해진다. 예시는 10개짜리 배열을 들었지만 100만개 짜리 배열이라고 생각하자.
그럼 이제부터 어떻게 컴퓨터에게 값을 찾게 할 것인가?
실생활 예를 다시 가지고 다시 생각해보자.
1. 1 부터 10까지의 숫자 중에 하나를 골라 --> 찾고자 하는 값
2. 첫 정답을 5이라고 말할 것 --> 중앙 값
3. Up이라고 했으면 --> 시작 위치 변경
4. 그 다음 정답을 7라고 말하며 --> 변경 된 중앙 값
이렇게 나눠볼 수 있다. 그러면 이제 변수를 지정해보자.
1. 찾고자 하는 값 == d
2. 중앙 값 == m
3. 시작위치 == s
4. 끝 위치 == e
이미지를 그려보면 위와 같을 것이다. 그렇 다면 그 다음은 어떻게 하면 될까?
찾고자하는 값이 중앙 값보다 Down이면 e인덱스를 중앙 값 바로 앞으로 이동시킨다.
그 상태에서 다시 중앙값을 찾고, Up인지 Down인지 확인한다.
이렇게 s, e의 변수를 중앙값 기준으로 앞 또는 뒤로 이동시켜 범위를 좁혀나가면서 원하는 값을 찾는 것이다.
위의 상태로 값을 찾아보면 다음과 같다.
1. d가 m보다 작으니, e를 m바로 앞으로 (idx 3번)으로 이동시킨다.
2. 중앙값을 1로 변경 후 보면 Up
3. s를 idx 2번으로 이동시키고, m도 idx 2번으로 이동하면 d == m이 같아지면서 원하는 값을 찾을 수 있다.
이렇게 획기적으로 횟수를 줄일 수 있다.
오늘은 이진탐색이 무었인지 알아보았고 다음 포스팅에서는 이진탐색의 활용방법에 대해서 알아보겠다.