이진탐색이란? 백준 문제추천

이진탐색이란? 백준 문제추천

도입

  연초가되어 카카오에서 고생한 직원 100명을 뽑아서 카카오해변으로 휴가를 보내주었습니다. 1년 동안 힘들게 일한 라이언은 신이나서 해변에 멋찐 작품을 만들고 밥을 먹고 돌아왔습니다. 돌아오니 아니 웬걸, 라이언이 공들여 만든 작품은 망가져있고 모래사장에 발자국이 하나 찍혀 있었습니다. 해변에는 100명의 사람들이 있습니다. 발자국 길이를 잰 라이언은 어떻게 하면 빠르게 범인을 찾을 수 있을까요?

  범인을 찾는 두 가지 방법이 있습니다.

• [방법 1] 해변에 찍힌 발자국의 길이와 같은 사람이 나올때까지 만나는 사람마다 발 크기를 재는 방법
  • [방법 2] 사람드에게 신발 크기가 작은 순서부터 큰 순서로 서 있게 한 다음에 중간에 서 있는 사람의 발 크기부터 비교합니다.

[방법 1] 은 전통적인 부르트포스 방법이고, [방법 2] 는 이번에 알아볼 이진탐색입니다.

코드로 살펴보기

def binarySearch(array, value, low, high):
    if low > high:
        return False
    mid = (low+high) / 2
    if array[mid] > value:
        return binarySearch(array, value, low, mid-1)
    elif array[mid] < value:
        return binarySearch(array, value, mid+1, high)
    else:
        return mid

(Source : Wiki)

이진탐색의 장점, 단점

• 장점
  • 정렬이 되어 있어야 이진탐색을 할 수 있습니다.
  • O(lgN) 으로 빠르게 탐색할 수 있습니다.
• 단점
  • 정렬이 되어 있지 않다면 정렬를 하는데 시간이 걸립니다.

🎁 백준 문제 추천

난이도는 주관적인 기준입니다 : )

No.	난이도	백준 링크	문제 풀이
1	🌕🌑🌑🌑🌑	수 찾기	풀이 준비중
2	🌕🌗🌑🌑🌑	숫자 카드 2	풀이 준비중
3	🌕🌗🌑🌑🌑	랜선 자르기	풀이 준비중
4	🌕🌗🌑🌑🌑	나무 자르기	풀이 준비중

---

참고자료

• Wiki. 이진 검색 알고리즘
• Blog. 이진탐색(binary search)

이미지

• pixabay. 발자국 이미지