[코딩테스트] 이진 탐색 알고리즘

이진 탐색

순차 탐색 : 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인

 

이진 탐색 : 탐색 범위를 절반씩 좁혀가며 탐색

정렬되어 있는 리스트에서만 탐색 가능함

시작점, 끝점, 중간점 등을 이용해 탐색해야 함

-> 시작점과 끝점이 같아질 때까지 반복함!

 

중간점을 기준으로 하여 찾고자 하는 값이 어디에 있는지 확인

중간점과 찾고자 하는 값이 동일하면 종료

 

- 이진 탐색 재귀로 구현

def binary_search(array, target, start, end):
    if start > end: # 탐색할 데이터가 없다면
        return None

    mid = (start + end) // 2 # 중간점 명시

    if array[mid] == target: # 중간점 == 찾고자 하는 값이면
        return mid # 결과를 찾은 것

    elif array[mid] > target: # 중간점 값보다 찾고자 하는 값이 작은 경우
        return binary_search(array, target, start, mid - 1) # 왼쪽을 다시 탐색
    else:
        return binary_search(array, target, mid + 1, end) # 오른쪽을 다시 탐색

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소 없음")
else:
    print(result + 1)

 

- 이진 탐색 반복문으로 구현

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:  # 중간 값 == 찾고자 하는 값
            return mid  # 중간 값 반환
        elif array[mid] == target:  # 왼쪽에 찾고자 하는 값이 존재
            end = mid - 1
        else:  # 오른쪽에 찾고자 하는 값이 존재
            start = mid + 1
    return None


n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소 없음")
else:
    print(result + 1)

 

 

트리 자료구조

트리 : 노드와 노드의 연결로 표현

노드 : 어떠한 정보를 가지고 있는 개체(단위)

 

 

이진 탐색 트리

부모 노드보다 왼쪽 자식 노드의 값이 작다

부모 노드보다 오른쪽 자식 노드의 값이 크다

 

 

예제) 떡볶이 떡 문제

여러 떡(N)을 가지고 있으며 떡의 길이는 각각 다름

떡은 절단기의 높이(H)에 맞춰 잘리고 남은 부분을 손님에게 판매

손님이 원하는 크기(M)를 맞춰서 잘라주는 최대의 길이(H) 찾기

 

높이가 0~10억까지 경우의 수를 선택할 수 있음 -> 큰 탐색 범위 -> 무조건 이진 탐색을 생각해야 함

 

중간 점의 값은 시간이 지날수록 최적화된 값이 도출됨

-> 떡 길이의 합이 크거나 같은 때마다 중간 값을 기록하면 됨 (마지막 else 부분)

n, m = map(int, input().split()) # 떡 개수 / 가져갈 길이

cake_list = list(map(int, input().split()))

start = 0
end = max(cake_list)
output = 0 # 결과

while start <= end:
    total_long = 0 # 잘랐을 때 떡의 길이
    mid = (start + end) // 2

    for i in cake_list:
        if i > mid:
            total_long += i - mid # 잘리는 부분의 값만 더함

    if total_long < m: # 잘린 양이 주문량보다 작은 경우
        end = mid - 1
    else: # 잘린 양이 주문량보다 크거나 같은 경우
        output = mid # 결과 값 저장
        start = mid + 1

print(output)

 

 

예제) 정렬된 배열에서 특정 숫자가 몇 번 나오는지 반환하는 함수를 작성하라.

정렬된 데이터에서 특정 값을 찾는 문제 == 무조건 이진 탐색

 

 

 

 

※ 해당 포스트는 이것이 "코딩 테스트다 with 파이썬(나동빈 저)"를 통해 학습한 내용을 정리한 것입니다.