이진탐색 백준 문제 추천

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

정의

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

[출처:wiki]

역시 정의는 어렵다. 진짜 쉽게 말해서 소주 병뚜껑 숫자 맞추기 할 때 1~100 이면 다들 50 먼저 얘기하고 up/down 듣고 

up 이면 75 down이면 25 ... 이런식으로 중간값을 이야기하는데 그 원리라고 보면 될 것 같다.

(1부터 100까지 계~~~~~~~속 이야기하는건 제한 횟수 내에 맞출수도 없고 비효율적이다. 이것을 부르트포스 방법이라고 한다.)

코드로 살펴보기

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(logN) 시간으로 빠르게 탐색할 수 있습니다.

• 단점

• 정렬이 되어 있지 않다면 정렬를 하는데 시간이 걸립니다.

백준 문제 추천

수찾기 1920번 https://www.acmicpc.net/problem/1920

숫자카드2 10816번 https://www.acmicpc.net/problem/10816

랜선자르기 1654번 https://www.acmicpc.net/problem/1654

나무자르기 2805번 https://www.acmicpc.net/problem/2805

다른 중요한 문제 추천 

DP 문제 추천

https://won-percent.tistory.com/3

그리디 알고리즘 문제 추천

https://won-percent.tistory.com/27