오늘은 시니어 2주차 주제인 이분탐색, binary search에 대해 설명하려 합니다.
이분탐색은 가장 많이 활용되는 탐색법들 중 하나로, 가장 보편적이고 효율적인 알고리즘입니다.
씨앗은 알고리즘 소모임으로,
주 마다 하나의 주제를 선정하고 강의를 진행합니다.
강의 후엔 주제에 맞는 예제를 풀어보고 연구하는 시간을 갖습니다.
Binary Search
이분탐색은 정렬되어 있는 자료들을 탐색범위를 절반씩 좁혀가며 원하는 자료를
탐색하는 방법을 말합니다. Up Down 게임을 상상해보면 쉽습니다.
1 ~ 100까지의 숫자중 63을 찾는 방법은?
1. 완전탐색 brute force
1,2,3...63 순으로 차례대로 63번의 비교를 거쳐 찾아봐야 합니다.
찾는 숫자가 100이였다면, 100번의 비교를 해야합니다.
2. 이분탐색 binary search
1 ~ 100 : 50 up
51~ 100 : 75 down
51 ~ 74 : 62 up
62 ~ 74 : 68 down
62 ~ 68 : 65 down
62 ~ 65 : 63 탐색완료
63번의 비교 연산을 해야하는 완전탐색에 비해 훨씬 적은 횟수로 63을 찾은 것을 볼 수 있습니다.
자료의 크기가 커지면 커질수록 이분탐색의 시간효율성은 더욱 부각되게 됩니다.
만약 10억개의 자료 중 하나를 찾아야 한다면,
완전탐색의 경우, 최악의 경우 : 10억 의 연산횟수를 가집니다.
이분탐색의 경우, 최악의 경우 : 약 30회 (2의 30제곱 = 약10억)
이분탐색은 범위를 절반씩 좁혀가며 탐색을 이어가기 때문에 아무리 탐색이 오래걸려도
log N 을 넘어가지 않습니다.(여기서 log의 밑은 2입니다.)
이제 이분탐색을 구현하는 방법을 알아보겠습니다.
이분탐색의 구현
위에서 나온 UP & DOWN게임을 코드로 옮긴다고 생각하면 쉽습니다.
가능한 숫자의 범위가 0 부터 N이고 (N은 양의 정수)
찾아야하는 숫자가 S라고 하면
1. left(한쪽 끝)를 0으로, right(반대쪽 끝)을 N으로 지정합니다.
2. mid (left와 right의 평균) 와 S를 비교합니다.
3 - 1. 만약 S가 mid보다 크다면, left부터 mid사이엔 S가 없기 때문에
left를 mid + 1로 수정합니다.
3 - 2. 만약 S가 mid보다 작다면 mid부터 right사이엔 S가 없기 때문에
right를 mid - 1로 수정합니다.
4. 과정 2, 3을 S와 mid가 같을 때 or left와 right가 역전될 때까지 반복한다.
코드로 살펴볼까요?
#arr안에 num을 찾는 이분탐색 함수
def biSearch_isNum(num, arr):
left = 0 #작은 쪽의 끝
right = len(list) - 1 #큰 쪽의 끝
#left가 right보다 작을 동안 반복
while left <= right:
#mid는 양 끝의 평균
mid = (left + right) // 2
#num이 mid번째 수 보다 큰 경우
if arr[mid] < num:
left = mid + 1
#num이 mid번째 수 보다 작은 경우
elif arr[mid] > num:
right = mid - 1
#num == arr[mid]
else :
#탐색성공
return True
#탐색실패 => 리스트안에 num없음
return False위 코드는 제가 생각하는 이분탐색을 활용한 가장 기본적인 알고리즘입니다.
이분탐색을 활용한 알고리즘은 매우 다양한데,
right를 찾는 경우, left를 찾는 경우, 그리고 매개변수 탐색 등등..
정말 다양하게 활용할 수 있습니다.
한마디로 이분탐색의 활용방법을 정리하자면,
완전탐색으로 제한시간내에 연산을 끝내지 못하는 경우에
이분탐색을 적용한다 입니다.
지금까지 배웠던 DP와 그리디에서도 비슷한 말을 했었는데
그 둘과는 정말 큰 차이점이 있습니다.
바로, 코드의 형태가 어느정도 정해져있다는 점입니다.
DP와 그리디는 정해진 형태가 딱히 없습니다.
설계단계에서 아이디어를 얻는 것이 끝이기 때문입니다.
하지만, 이분탐색은 찾으려는 값과 mid를 비교, left와 right 갱신
이라는 뚜렷한 패턴이 존재하기 때문에 한번 익혀놓으면
이분탐색을 활용하는 문제들은 거의 구현할 수 있게 됩니다.
이분탐색을 사용하는 문제유형으로는 다음과 같은 것들이 있습니다.
- S가 입력된 자료안에 존재하는 지?
- S가 입력된 자료안에 몇 개 존재하는 지?
- 어떤 조건을 만족하는 가장 큰(가장 작은) 수는 무엇인지? => 매개변수 탐색
- 자료의 어떤 부분수열(연속할 수도, 안할수도) 의 합
- LIS(가장 긴 증가하는 부분수열)을 구하는 문제
- 기타등등..
제 경험상, 이분탐색은 학습 효과가 정말 빠르게 나타납니다.
처음엔 마냥 어렵다가, 몇 문제 찾아보다보면 조금씩 풀이법이 보이기 시작하고
몇 시간 후엔 문제 해결 속도가 정말 빨라졌다는 것을 느낄 수 있었습니다.
그러니 처음엔 어렵더라도 조금씩 해보시면 좋을 것 같습니다.
오늘 준비한 문제들은 유형 1 ~ 4 중 하나로 선정했습니다.
(LIS는 제 개취라서 언젠가 따로 강의를 할 예정입니다.)
예제
Basic
Advanced
Hard
