이진 탐색 파이썬 코딩테스트 (12) BOJ1920

 

목차

---

서론

탐색은 크게 1.선형 탐색 2. 이분(이진) 탐색 3.해시 탐색 4. DFS/BFS 로 나뉜다. BFS/DFS는 워낙 자주나와서 따로 요일을 할당했고, 선형은...간단하고 기본이라 2,3하면 알아서 딸려올 놈이라 판단했다. 고로 월요일에는 이진탐색과 해시탐색을 다룰 예정이다.

---

이분(이진)탐색이란?

이분탐색은 정렬된 배열에서 특정 데이터를 찾기위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법이다. 마치 업다운을 할때 중간수부터 얘기하고 -> 없이라면 상한값과 해당 중간값의 또 중간값.. 또 중간값..그러면서 결국 수를 찾는 방법이라고 생각하면 되겠다. 선형 탐색이 O(N), 이진 탐색은 Olog(N)이기에 N이 커질수록 그 값(=시간)이 차이가 크다.

---

이분(이진)탐색 알고리즘 

위에 정의에도 있듯 우선 1. 정렬된 배열이여야 한다. 그래야 2로 나눴을때 큰지 작은지 비교해서 더 큰놈 내지 더 작은 그룹을 버릴 수 있기 때문이다. 두번째는 2. 범위의 시작과 끝(start, end) 나타내는 변수가 필요하다. 쉽게 st, en 이렇게 쓰면 될듯. 또한 정의에서 또 알 수 있듯 중간으로 줄여가는 과정이기 때문에 3. 중간 변수를 정해야 한다. 나름 만국 공통인 mid를 사용하도록 하자. mid = (st + en)//2 라고 하면 될듯하다. 나아가 4. 찾고자 하는 값이 없을 수도 있다는 가정(예외의 가능성)을 하자.  st, en, mid 값을 각각 정했으면 이제 줄여나가면 된다. 줄여나가는 과정은 아래 문제(BOJ1920)를 풀어보며 진행하겠다.

---

BOJ1920 수찾기

BOJ1920 문제를 보면 위에서 말한 이분 탐색을 하라고 노골적으로 말하고 있다. 일단 위에서 1번에 해당하도록 sort를 이용해 정렬을 시킨다. 2. st, en, mid를 각각 배정한다.(시작시) 3. x 값과 중간값의 크기를 비교해보자. x는 19, mid는 16이기 때문에 mid 오른쪽에 존재한다. 4. st를 mid+1로변경함으로써 범위를 절반으로 줄인다. 이제 새로워진 범위(st,en)로 5. 또 다시 mid를 계산하고, mid값과 x를 비교한다. A[mid]인 23은 19보다 크기 때문에 이젠 x값이 mid 왼쪽에 위치한다. 이 때에는 6. en를 mid -1로 변경함으로써 또 다시 범위를 절반으로 줄인다. 이렇게하면 A[mid] == x 이기 때문에 19가 있다는것을 확인할 수 있다. 

---

BOJ1920 수찾기 - 예외 상황

만약에 같은 배열이라고 하고, 10과 같이 배열에 없는 값을 찾으면 어떻게 될까? 위에 있는 과정을 계속 진행하다보면 어느순간 st, en, mid가 한곳으로 모이는 순간이 오거나 st가 en 값보다 커지는(같은 말이지만 en이 st보다 작아지는) 상황이 온다. st와 en이 역전된 상황 이라고 하면 될것을 귀찮게 말했다.

---

BOJ1920 수찾기 코드

위에서 설명한대로 코드를 작성하면 다음과 같다. 흐름을 보면 정렬한 뒤, 시작 인덱스를 정하고 (0, len(n)-1), 큰지 작은지 판단하고 같으면 1 둘이 전후 관계가 뒤바뀌면 0 아무것도 아니면 무한 루프를 돌리는 것이다. 아무쪼록 이해했길 바라며 첫 문제인 BOJ1920은 여기서 마치겠다. 다음 포스팅에서는 BOJ10816 좌표압축 문제를 풀어보겠다. 코딩테스트 준비 여정이 궁금한 사람은 여기로.

n =[4, 1, 5, 2, 3]
x = 7
n = sorted(n)
def binarysearch(x):
    st = 0
    en = len(n) - 1
    while(st <= en) :
        mid = (st + en) // 2
        if n[mid] < x :
            st = mid + 1  #중간 값이 타겟 넘버보다 작을 때
        elif n[mid] > x:
            en = mid - 1
        else: 
            return 1  # mid값이 x와 일치했을때 있는거 출력
    return 0  #없을때 예외

print(binarysearch(x))