[코테 스터디] Week4 이진 탐색 개념 정리

* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다.

https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5

이진 탐색 알고리즘

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

→ 가장 기본적인 형태의 데이터 탐색 알고리즘

ex. 선택 정렬에서 매 단계마다 가장 작은 데이터를 찾는 과정

⇒ 리스트에서 특정 데이터가 존재하는지 검색할 때 별다른 말이 없으면 기본적으로 순차 탐색을 이용하는 것

 

이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 시간 복잡도: O(logN)
• 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

💡 이진 탐색 동작 예시 (찾으려는 수: 4)

0 2 4 6 8 10 12 14 16 18

[Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)

0 2 4 6 8 10 12 14 16 18 (시작 숫자: 0, 끝 숫자: 18, 중간 숫자: 8)

→ 중간 숫자를 포함하여 위 쪽은 찾으려는 수보다 크므로 탐색 범위에서 제외

[Step 2] 시작점: 0, 끝점: 3, 중간점: 1 (소수점 이하 제거)

0 2 4 6 (시작 숫자: 0, 끝 숫자: 6, 중간 숫자: 2)

→ 중간 숫자를 포함하여 아래 쪽은 찾으려는 수보다 작으므로 탐색 범위에서 제외

[Step 3] 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거)

4 6 (시작 숫자: 4, 끝 숫자: 6, 중간 숫자: 4)

탐색 종료

이진 탐색의 시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일하므로, 연산 횟수: log2N 에 비례

ex. 초기 데이터의 개수: 32개, 이상적으로 1단계만 거치면 16개 가량의 데이터만 남음

• 2단계: 8개
• 3단계: 4개

⇒ 탐색 범위를 절반씩 줄이며, 시간 복잡도: O(logN)

# 이진 탐색 소스코드 구현 (재귀 함수)

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(찾고자 하는 값)을 입력 받기
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) # 몇 번째 원소인지 출력하기 위해 +1 (인덱스+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(찾고자 하는 값)을 입력 받기
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) # 몇 번째 원소인지 출력하기 위해 +1 (인덱스+1)

파이썬 이진 탐색 라이브러리

• bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 4

 

파라메트릭 서치 (Parametric Search)

파라메트릭 서치: 최적화 문제를 결정 문제 (’예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법

ex. 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능

예제 1) 떡볶이 떡 만들기

적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복 조정

• ‘현재 이 높이로 자르면 조건을 만족할 수 있는가?’를 확인한 뒤, 조건의 만족 여부 (’예’ 혹은 ‘아니오’)에 따라서 탐색 범위를 좁혀서 해결 가능
• 절단기의 높이는 0부트 10억까지의 정수 중 하나

⇒ 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 함

+ 중간점의 값은 시간이 지날수록 ‘최적화된 값’이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 중간점을 기록하면 됨

import sys

N, M = map(int, sys.stdin.readline().split())
h_list = list(map(int, sys.stdin.readline().split()))

start = 0
end = max(h_list)

result = 0
while(start <= end):
    total = 0
    mid = (start+end) // 2
    for x in h_list:
        # 잘랐을 때의 떡의 양 계산
        if x > mid: # 현재 떡의 길이가 높이보다 클 때만 떡을 얻을 수 있음
            total += x - mid # 떡이 잘렸을 때 길이가 0 이상이면 total 값에 더해짐
    # 떡의 양이 부족한 경우 더 많이 자르기 = 왼쪽 부분 탐색
    if total > M:
        end = mid - 1
    # 떡의 양이 충분한 경우 덜 자르기 = 오른쪽 부분 탐색
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로 여기에서 result 기록
        start = mid + 1

print(result)

예제 2) 정렬된 배열에서 특정 수의 개수 구하기

• 시간 복잡도 O(logN)으로 동작하는 알고리즘 = 이진 탐색 수행 (데이터 정렬되어있으므로)
  • 일반적인 선형 탐색으로는 시간 초과 판정
• 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산하면 해결 가능

import sys
from bisect import bisect_left, bisect_right

n, x = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))

dif = bisect_right(array, x) - bisect_left(array, x)
if dif == 0:
    print(-1)
else:
    print(dif)