본 포스팅은 (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 공부하고 정리한 글임을 밝힙니다.

---

이진 탐색 알고리즘

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

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

  • 시작점, 끝점, 중간점을 이용하여 탐색 범위 설정

이지 탐색 동작 예시

✅ 찾고자하는 값보다 중간점의 값이 더 크다면, 중간점에서부터 끝점까지 전부 확인할 필요가 없는 것 (중간점보다 모두 큰 값이기 때문)✅ 이후 끝점을 중간점의 왼쪽으로 다시 할당 ➡️ 탐색 범위가 더 줄어듬
✅ 4개의 범위에서 다시 중간점을 셋팅한 후, 마찬가지로 우리가 찾고자하는 값 4를 찾지 못했음
✅ 다만, 이번에는 중간점 값보다 찾고자하는 값이 더 크기때문에 중간점부터 시작점까지 왼쪽 부분은 볼 필요가 없음
✅ 따라서 이번에는 시작점의 위치를 중간점의 오른쪽으로 다시 할당✅ 이번에는 중간점이 우리가 찾고자하는 값과 동일하므로 탐색을 종료 ➡️ 인덱스 2에 위치함을 알게됨

이진 탐색의 시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일 ➡️ 연산 횟수는 $log_2N$에 비례
• ex) 초기 데이터 개수가 32개 일때, 이상적으로 1 단계를 거치면 16개 가량의 데이터만 남음
  • 2 단계 ➡️ 8개 가량의 데이터
  • 3 단계 ➡️ 4개 가량의 데이터
• 즉, 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 $\bold {O(logN)}$을 보장

이진 탐색 소스코드(1): 재귀적 구현

# 이진 탐색 소스코드 구현 (재귀함수)
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)

이진 탐색 소스코드(2): 반복문 구현

# 이진 탐색 소스코드 구현 (재귀함수)
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)

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

• 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))
print(bisect_right(a, x))

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

# 배열 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))

# 값이 [-1, 3] 범위에 속하는 데이터 개수 출력
print(count_by_range(a, -1, 3))

파라메트릭 서치(Parametric Search)

• 실제로 이진 탐색을 활용해야하는 문제가 출제될 경우, 파라메트릭 서치 유형으로 출제되는 경우 많음
• 파라메트릭 서치: 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법
  • ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 코테에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능

<문제 1> 떡볶이 떡 만들기

문제 설명

문제 해결 아이디어

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

• '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부(예/아니오)에 따라서 탐색 범위를 좁혀서 해결 가능

  • 높이가 커지게 되면 잘린 떡의 길이가 작아지고, 반대로 높이를 줄이면 잘린 떡의 길이가 커짐
  • 매 높이마다 조건 여부 확인하여 높이 조절

• 절단기의 높이는 0부터 10억까지의 정수 중 하나

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

✅ 여기서 중간점은 우리가 자르고자 하는 높이 H가 됨
✅ 중간점=9일 때, 필요한 M만큼의 떡을 가질 수 있으므로 결과 저장
✅ 높이를 더 높였을 때도 길이 M을 만족할 수 있는지 확인✅ 마찬가지로 길이 M보다 크기때문에 결과 저장하고, 다시 높이를 증가시켜봄✅ 이때 잘린 떡의 길이가 M을 만족하지 못하므로 결과를 저장하지 않고, 이번엔 중간점(높이)를 더 줄여서 또 확인✅ 잘린 떡의 길이가 M과 완전히 동일하므로 이때의 결과를 저장하고 결과 반환

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

답안 예시

# 떡의 개수(N)와 요청한 떡의 길이(M) 입력
n, m = list(map(int, input().split()))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행 (반복적)
result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in array:
        # 잘랐을 때의 떡의 양 계산
        if x > mid:
            total += x - mid
    # 떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡의 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result 기록
        start = mid + 1

# 정답 출력
print(result)

<문제 2> 정렬된 배열에서 특정 수의 개수 구하기

문제 설명

문제 해결 아이디어

• 시간 복잡도 $O(logN)$으로 동작하는 알고리즘 요구

  • 일반적인 선형 탐색(Linear Search)로는 시간 초과 판정
  • but, 데이터가 정렬되어 있기 때문에 이진 탐색을 수행

• 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제 해결

  답안 예시

• bisect_left와 bisect_right 이용한 문제 풀이

  from bisect import bisect_left, bisect_right

값이 [left_value, right_value]인 데이터의 개수 반환 함수

def count_by_range(array, left_value, right_value):
left_index = bisect_left(array, left_value)
right_index = bisect_right(array, right_value)
return right_index - left_index

데이터 개수 N, 찾고자 하는 값 x 입력 받기

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

값이 [x, x] 범위에 있는 데이터 개수 계산

count = count_by_range(array, x, x)

값이 x인 원소가 존재하지 않는다면

if count == 0:
print(-1)

값이 x인 원소가 존재한다면

else:
print(count)