2분 안에 알아보는 이진 탐색 (Binary Search)

(제목은 거짓입니다.)

무언가 알고리즘다운 알고리즘을 처음으로 알게 된 것은 이진 탐색부터라고 할 수 있겠다. 

정렬하고 뽑아내는 것도 물론 쉽지 않지만, 애초에 정해진 방법이 있는 알고리즘을 처음 배운것이다.

 

사실상 단어 뜻만 가지고서는 이걸로 뭘 하는건가 싶은데 가끔씩 실생활에서도 사용을 하는.. 그런 방법이었다.

 

원리는 간단하고 사용할 조건도 필요하다. (간단?)

이 알고리즘은 특정 숫자를 찾는 업 - 다운 게임을 생각하면 되겠다. 근데 이걸로 끝이겠냐?

 

사실상 개념은 익숙한 편이고 그리 어렵지 않지만 이것을 배우는 이유는 문제 해결을 위해서다.

수많은 데이터들 중에서 원하는 데이터를 찾을 수 있는 방법.. 중 하나인 것이다.

 

좀더 자세히 알아볼까? (2분 초과)

 

이진 탐색

꺼무위키에서 찾은 수도코드를 살펴보자

function 이진탐색(데이터, 찾는 값)

데이터가 혹시 비어 있는가?
(네) return 찾는 값 없음.

데이터의 가운데 지점을 찾는다.
찾은 지점의 값을 뽑는다.
뽑은 값이 찾는 값인가?

(네) return 뽑은 값.
(아니요)
  뽑은 값과 찾는 값을 비교한다.
  (뽑은 값이 찾는 값보다 큰 값인가?)
    return 이진탐색(데이터 앞쪽 절반, 찾는 값)
  (작은 값인가?)
    return 이진탐색(데이터 뒤쪽 절반, 찾는 값)

 

가장 기본적인 로직은 데이터의 '중간 지점'을 뽑아내 비교하는 것이다. 

 

그렇기에 정렬되어있지 않은 데이터는 의미가 없다. 데이터의 인덱스를 이용하든, 값이 정렬 되어있어야 의미있는 사용을 할 수 있다.

 

수많은 시행횟수를 통해 끊임없이 좌우로 왔다갔다 하다가 결국엔 내가 원하는 답을 찾게된다. 머리로 떠올려보자...

데이터를 모두 조회하는 것보다 복잡도가 낮아서 필요할 때 사용하면 좋을듯 하다.

 

방금 풀어본 (아님) 예제가 마음에 들어 함께 살펴보자. 샤라웃 투 백준

징검다리 : https://www.acmicpc.net/problem/11561

 

????? ??????????????????????

소신발언 : 코딩 문제 제작자들은 문제를 만들 수 있는 지식이 분명히 필요하겠지만, 그것보다 글을 더 명확하고 잘 썼으면 하는데.. 나같은 멍청이도  쉽게 이해할 수 있는 깔끔한 문장으로 작성해주세요. 이상한 말좀 늘어놓지 마세요. 하하하

 

처음 볼때는 4가지 조건이 한번에 명확히 이해가 되지 않았다. 물론 여러번 생각하고 읽으면 문제가 무엇을 원하는지 알 수 있다. 모든 문제가 말이 이상한 것은 아닌데 문장이 이상한 글들을 자주 만나니 피로해지는 것은 어쩔 수 없었다. 

 

어쨌든 불쌍한 승택이는 몇개인지도 모를 징검다리를 뛰어서 건너야하고, 계속해서 멀리멀리 뛰어야한다.

 

조건들을 살펴보자.

 

1. 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
   -> 강변에 서있는 승택이는 첫번째 징검다리는 아무 것이나 밟을 수 있다. 설령 1000만개가 있다고 해도 천만번째를 밟을 수 있는 것이다. 물론 징검다리를 밟는 최대 개수를 구해야하므로 1번 징검다리를 밟는 것이 잠정적으로 확정된다. 헷갈리게 하려는 목적이었나? 그냥 첫번째 징검다리는 아무거나 밟을 수 있다고 했으면 뭐 문제가 더 쉽게 느껴졌을 수도 있겠다. 아니면 시작을 그냥 1번에서 한다던가.. 그래...
2. 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
   아니 이렇게 쓸거였으면 1번 조건을 "첫 번째 점프는 아무 징검다리나 밟을 수 있다." 라고만 해도 되지 않았나 싶음.
   점프력이 대단한 승택이는 점프가 계속 될 때마다 한 칸 씩 더 거리를 늘려가야한다. 1칸 2칸.. 3칸... 4칸....
3. N번 징검다리는 반드시 밟아야 한다.
   그냥 마지막 징검다리라고 하면 안될까?
   
   
4. N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.
   마지막 징검다리에 도착한 승택이는 편하게 강변으로 올라온다. 점프를 하지 않아도 된다. 

쓰다보니 글 자체를 뭐라 하고 있었는데, 조건을 분석해보면 이진 탐색??? 을 떠올리기가 쉽지가 않다. 실제로 나는 떠올리지 못했다. 근데 이게 왜 이진 탐색으로 풀어야 하는 문제일까? 물론 다른 방법도 있을것이다. 다른 방법이 쉽게 떠올랐다면 그대로 푸는게 낫겠다. 하지만 이진 탐색 설명이므로 이 알고리즘으로 접근해보자.

 

나도 헷갈리니 징검다리를 밟는 횟수 = 점프횟수라고 생각하고 점프라는 표현을 쓰겠다

 

문제에선 주어진 N개의 징검다리를 지나 강을 건너기 전에 최대한 많은 점프를 해야 한다. 마지막은 꼭 밟아야 하니까 그것도 고려해두자. 

 

그럼 1칸씩 가면 되잖아요? -> 조건에서 점프를 할때 마다 거리를 이전의 점프에서 1 만큼 늘린다고 했다.

 

결국 5번 점프를 하면 1+2+3+4+5 만큼의 거리를 이동한 것이된다.

강변에서 시작하여 첫번째 점프로 1번 징검다리를 밟고(시작은 아무거나 밟을 수 있으니) 4번 더 점프하고 나서 15번 징검다리에 도착했을 것이다. 그리고 강을 건너게 된다.

 

만약 예시처럼 징검다리가 15개였다면, 최대 점프 횟수는 5회가 될것이다. 이 과정을 잘 기억해두자.

 

1 부터 k 까지의 자연수 합이 징검다리의 개수 N보다 작거나, 같으면

우리가 원하는 최대 점프 횟수 k를 알 수 있다. 

 

N은 문제에서 주어진다. 이진탐색을 통해 이 k를 알 수 있다.

 

그냥 번호를 찾는 업다운과는 약간 다른 형태이다. 등차수열의 합이 등장하였으므로..

간단한 이진 탐색 구현으로 정답을 찾을 수 있었다.

 

def max_steps(n):
    left, right = 1, n
    answer = 0

    while left<=right:
        mid = (left+right)//2
        sum_mid = mid * (mid+1) //2

        if sum_mid <= n:
            answer = mid
            left = mid +1
        else:
            right = mid-1

    return answer

 

1) 탐색을 진행할 데이터를 설정한다. 시작은 1, 끝은 문제에서 주어진 징검다리의 개수 N이다.

2) mid라고 선언한 중간 값은 1과 N의 중간 값이다. 그리고 1부터 mid까지의 자연수 합 sum_mid를 계산한다. 

 

3) 맨 처음 while문으로 left, right의 값에 따라 반복문을 빠져나오는 조건을 설정한다.

4) if 분기에 따라 left, right로 선언된 값을 조절할 것이다. -> sum_mid가 어떤 값이 나오느냐에 따라.

 

 

예시에서 N  = 15일때 이야기를 했으므로 이걸 예시로 간단히 정리해보자

while left<=right:  마지막 반복에서 빠져나올 수 있음

    left: 1, right: 15, mid: 8, sum_mid: 36
    처음 주어진 범위, 중간값 8, 8까지 자연수 합은 36이므로 if문 조건 불일치
    조건과 일치하려면 더 작은수가 필요함. right를 mid-1로 변경 (우측 삭제)

    left: 1, right: 7, mid: 4, sum_mid: 10
    두번째 범위, 중간값 4, 4까지 자연수 합은 10이므로 if문 조건 일치. 우선 answer = 4저장
    조건에 맞는 또다른 중간값이 나올 수 있다. left를 mid+1로 변경 (좌측 삭제)

    left: 5, right: 7, mid: 6, sum_mid: 21
    세번째 범위, 중간값 6, 6까지 자연수의 합은 21이므로 if문 조건 불일치
    조건과 일치하려면 더 작은수가 필요함. right를 mid-1로 변경 (좌측 삭제) 

    left: 5, right: 5, mid: 5, sum_mid: 15
    조건과 일치함. answer를 5로 업데이트함.
    아직 while을 벗어나지 못했음. if 조건이 일치하므로 left를 mid+1로 변경

    left:6, right:5 -> 최상위 while 조건에 어긋나므로 while 이탈.
    
    answer = 5

최대 점프 횟수: 5

 

이런 과정을 거쳐, 어떤 수를 집어넣든 문제에 맞는 답을 찾게 된다. 

 

작은 N이니까 대충 머리로 생각해보면

1번 - 첫번째 징검다리로 1칸 뜀.  (현재 1번째 징검다리)

2번 - 2칸 뜀 (현재 3번째 징검다리)
3번 - 3칸 뜀 (현재 6번째 징검다리
4번 - 4칸 뜀 (현재 10번째 징검다리)
5번 - 5칸 뜀  - 마지막 징검다리 도착   (6번은 뛰려면 규칙을 어겨야함)

 

이런 흐름이 되겠지만, 실질적인 코드 작성에는 큰 도움은 되지 않는다. 이진 탐색의 원리를 이해하고 그것을 구현할 수 있느 능력이 있어야하겠다.

---

 

이진 탐색은 이 글을 작성하며 어느정도 이해가 되었으나, 가장 중요한것은 언제 이진 탐색을 사용하여 답을 찾을 수 있는가를 알아내는 것이다. 이것은 오로지 경험 뿐이다.. 비슷한 문제를 더 풀어보자. 뒷심이 좀 떨어졌지만, 이진 탐색을 좀 더 이해할 수 있었다.

 

앞서 간 사람들이 존경스러운 시간이다. 당신들은 대체 어떤 싸움을......... 하신겁니까..