20260424 오늘의 학습: 이진 탐색

Yesol Lee·2026년 4월 24일
COS Propython학습일지

COS Python

목록 보기
23/30

지난 학습 요약

4/23 21차 세션에서는 20차 자기 진단에서 나온 두 약점(초기값 세팅 누락 / 인덱스+값 병렬 처리 미숙)을 겨냥해 enumerate → zip → 튜플 정렬 세 빈칸을 가볍게 풀었다. zip 문제에서 top_score = scores[0], top_name = names[0] 초기값 세팅을 힌트 없이 스스로 써서 개선 신호를 확인했고, 부호 뒤집기 트릭의 경계 질문에서 stable sort 기반 2단계 정렬까지 확장했다. 세션 마지막에는 이미 풀어본 프린터 우선순위 문제를 매개로 그리디 알고리즘 개념을 명시적으로 정립했다.

오늘 수업 계획

오늘은 이진 탐색(Binary Search) 을 처음부터 배운다. 개념 설명 → 기본 템플릿 빈칸 → lower bound 변형 빈칸 → 디버깅 → 함수 작성(개수 세기 응용) 순서로 진행한다. COS Pro 1급에 빈출되는 유형이자 아직 안 배운 영역이라 기초를 탄탄히 쌓는 데 집중한다. 마지막에 학습자가 제기한 "시험에서 bisect 써도 되나?" 질문에서 완성형/부분형별 활용 전략까지 정리한다.

학습 내용 정리

1) 이진 탐색 — 언제, 왜 쓰는가?

전제 조건: 리스트가 정렬되어 있어야 한다. 정렬되지 않은 데이터에는 못 쓴다.

속도 비교:

탐색 방법시간복잡도크기 100만 리스트에서 최악 비교 횟수
선형 탐색O(n)약 1,000,000번
이진 탐색O(log n)약 20번 (2²⁰ ≈ 100만)

절반씩 버려가며 탐색하기 때문에, 데이터가 커질수록 격차가 기하급수적으로 벌어진다.

동작 원리: [1, 3, 5, 7, 9, 11, 13] 에서 11 찾기

  1. 가운데(인덱스 3) 값은 7. 찾는 값 11보다 작으니 왼쪽 반 전부 버림 → left = mid + 1
  2. 남은 [9, 11, 13] 의 가운데(인덱스 5) 값은 11. 찾음, 반환 5

핵심 3줄로 요약하면:

mid = (left + right) // 2
if arr[mid] == target: 찾음
elif arr[mid] < target: left = mid + 1   # target은 오른쪽에 있음
else: right = mid - 1                     # target은 왼쪽에 있음

2) 기본 이진 탐색 템플릿 (빈칸 1)

문제: 정렬된 arr 에서 target 의 인덱스를 반환, 없으면 -1. ㉠, ㉡ 을 채우시오.

def solution(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target: # 7 < 11
            left = mid + 1      # ㉠
        else:
            right = mid - 1     # ㉡
    return -1

왜 +1, -1 을 붙이나?

arr[mid] 는 이미 target이 아닌 걸 확인했으니 mid 자체는 다시 볼 필요가 없다. 그래서 ±1 로 mid를 제외하고 범위를 줄여야 한다.

만약 left = mid 로 쓰면? [1, 3] 에서 3 찾을 때 left=0, right=1 → mid=0 → arr[0]=1 < 3 → left=0 그대로 → 무한 루프 💥

while 조건 <= 에 등호가 꼭 필요한 이유: 원소가 한 개 남았을 때(left == right) 그 한 개도 검사해야 하기 때문. 등호를 빼면 마지막 남은 원소를 놓친다.

3) lower bound 패턴 — "target 이상 첫 위치" (빈칸 2)

기본 이진 탐색만으로는 부족한 경우가 많다. 예: "6 이상의 값이 처음 나오는 위치" 같은 경계값 찾기. COS Pro에서도 종종 이 변형으로 출제된다.

# 정렬된 arr에서 target 이상인 값이 처음 등장하는 위치를 반환
# 모든 값이 target보다 작으면 len(arr) 반환
def solution(arr, target):
    left, right = 0, len(arr)     # ← right가 len-1이 아닌 len
    while left < right:            # ← 등호 없음
        mid = (left + right) // 2
        if arr[mid] >= target:
            right = mid            # ← mid도 답 후보이므로 제외하지 않음
        else:
            left = mid + 1
    return left

# 테스트
print(solution([1,3,5,7,9], 6))   # 3  (6 이상 첫 값은 7, 인덱스 3)
print(solution([1,3,5,7,9], 10))  # 5  (없음 → len 반환)

기본 이진 탐색과 3가지 차이점:

항목기본 이진 탐색lower bound
초기 rightlen(arr) - 1len(arr)
while 조건left <= rightleft < right
범위 좁히기right = mid - 1right = mid

왜 right = mid 이고 mid - 1 이 아닌가?

  • 기본 버전: arr[mid] == target 이면 바로 반환이라 mid는 이후 볼 필요 없음 → 제외 가능 → mid ± 1
  • lower bound: arr[mid] >= target 이면 mid도 답 후보 로 남겨야 함 → 제외 금지 → right = mid

왜 < 로 등호를 뺐나?

  • 만약 <= 이면 left == right == mid 에서 right = mid 로 범위가 그대로 → 무한 루프
  • < 면 left == right 에서 루프 종료하고 그 값이 답

풀이 중에는 print(f"left={left} right={right} mid={mid} arr[mid]={arr[mid]}") 로 실행을 직접 추적하며 ㉠에 right = mid, ㉡에 left = mid + 1 을 채웠다. 이진 탐색처럼 조건이 헷갈릴 때는 한 번 찍어보고 가는 게 확실하다.

4) 디버깅 — / vs // 함정

문제: 한 줄만 고쳐라.

def solution(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) / 2    # ← 버그!
        if arr[mid] == target:
            return mid
        ...

답: mid = (left + right) // 2 (정수 나눗셈으로 교체)

이유:

  • Python의 / 는 항상 실수(float) 를 반환한다. (0 + 6) / 2 는 3.0 이다.
  • arr[3.0] 은 TypeError: list indices must be integers 에러가 난다. 리스트 인덱스는 반드시 정수여야 한다.
  • 따라서 정수 나눗셈 // 를 써야 한다.

Java와 비교:

언어(0 + 6) / 2 결과
Java (int / int)3 (자동으로 정수 나눗셈)
Python3.0 (항상 실수)
Python 정수 나눗셈(0 + 6) // 2 → 3

Java 경험이 있으면 오히려 이 함정에 걸리기 쉽다. / 가 Java에서처럼 자동으로 정수로 떨어질 거라 기대하기 때문. 이진 탐색 디버깅 단골 함정이므로 반드시 기억해두자.

5) 함수 작성 — target 등장 횟수 (lower + upper bound 조합)

문제: 정렬된 리스트 arr 에서 target 이 몇 번 등장하는지 반환. 중복 가능.

아이디어: 두 번의 이진 탐색으로 경계를 찾아 뺀다.

  • target 이상 첫 위치 = left_idx
  • target + 1 이상 첫 위치 = right_idx (= target 초과 첫 위치)
  • 개수 = right_idx - left_idx

예: [1, 2, 2, 2, 3], target=2

  • 2 이상 첫 위치 = 1
  • 3 이상 첫 위치 = 4
  • 개수 = 4 − 1 = 3 ✓

풀이:

def solution(arr, target):
    # right_idx 찾기 (target+1 이상 첫 위치)
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= target + 1:
            right = mid
        else:
            left = mid + 1
    right_idx = left

    # left_idx 찾기 (target 이상 첫 위치)
    left, right = 0, right_idx  # 위에서 이미 찾은 범위만 뒤지면 충분
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= target:
            right = mid
        else:
            left = mid + 1
    left_idx = left

    return right_idx - left_idx

테스트 [1,2,2,2,3,4,5] target=2 → 3, [1,1,1,1,1] target=1 → 5, 빈 리스트 [] → 0 (while 루프 자체에 진입 안 해서 자연스럽게 0 반환) 까지 전부 통과.

빈 리스트 대응을 위해 별도 방어 코드를 쓰지 않아도 left=0, right=0 이면 while left < right 가 바로 거짓이 되어 빠져나간다. 이진 탐색 템플릿의 숨겨진 장점 중 하나.

더 간결한 방법 (학습자 질문)

수업 중 질문 (풀이 직후): "이진 탐색 로직을 두 번 썼는데 더 간결한 방법도 있을까?"

크게 두 가지 대안이 있다.

방법 1: bisect 표준 라이브러리 활용

from bisect import bisect_left, bisect_right

def solution(arr, target):
    return bisect_right(arr, target) - bisect_left(arr, target)
  • bisect_left(arr, x) = x 이상 첫 위치 (= left_idx)
  • bisect_right(arr, x) = x 초과 첫 위치 (= right_idx)
  • 위에서 손으로 짠 두 이진 탐색을 한 줄로 대체

방법 2: 헬퍼 함수로 중복 제거

def solution(arr, target):
    def lower_bound(x):
        left, right = 0, len(arr)
        while left < right:
            mid = (left + right) // 2
            if arr[mid] >= x:
                right = mid
            else:
                left = mid + 1
        return left
    return lower_bound(target + 1) - lower_bound(target)

이진 탐색 로직이 한 곳에만 있어 중복이 제거된다. 바깥 변수 arr 는 클로저로 자연스럽게 참조된다.

결론: 중복처럼 보여도 if 조건이 다르기 때문에 직접 두 번 쓰는 것도 완전히 정답. 리팩터링은 취향.

6) 시험 전략 — bisect 를 시험에서 그대로 써도 되나?

수업 중 질문: "시험에서 bisect를 그대로 써도 되는거야?"

좋은 질문이다. 정답은 "쓸 수 있다, 하지만 뉘앙스 주의".

COS Pro 1급에서 허용되는 표준 라이브러리:

import bisect                          # 이진 탐색
from collections import Counter, deque  # 빈도 / 큐
from itertools import combinations      # 조합
import heapq                            # 우선순위 큐
import math                             # gcd, sqrt

하지만 유형별로 활용 가능 범위가 다르다:

유형bisect 사용 가능?실전 팁
완성형 (함수 작성, 3문제)O, 자유롭게bisect 쓰면 코드가 훨씬 짧아져 시간 절약
빈칸 채우기출제자가 정해둔 코드를 따라야 함직접 구현 코드가 제시되면 그 흐름대로 빈칸 채움
디버깅출제자 코드 구조 그대로bisect가 이미 쓰여있으면 그 안에서 버그 찾기

왜 빈칸에선 직접 구현이 더 많이 나오나?
출제자 입장에서 bisect_left(arr, target) 한 줄을 빈칸으로 내면 시험이 너무 쉬워진다. 그래서 이진 탐색 로직을 풀어쓴 코드에서 left = mid + 1 같은 부분을 빈칸으로 내는 게 일반적이다.

결론적인 학습 전략:
1. 직접 구현 원리를 확실히 이해 — 빈칸/디버깅 대비 (부분형 7문제 = 700점, 훨씬 큰 비중)
2. bisect 사용법도 알아두기 — 완성형에서 시간 단축 무기
3. 완성형에서 남은 시간이 빠듯하면 bisect 한 줄로 처리하고 다음 문제로 넘어가는 판단도 가능

오늘 세션에서 빈칸 2개 + 디버깅 1개 + 함수 작성 1개 모두 직접 구현으로 풀었으니, 부분형 대비의 기초는 탄탄히 깔린 셈이다.

오늘의 결과

  • 푼 문제 4문제 (빈칸 2 + 디버깅 1 + 함수 작성 1), 1차 정답률 100% (4/4)
  • 이진 탐색 기본 / lower bound 변형 / 개수 세기 응용까지 한 세션에 체화
  • 다음 학습: 수학 (소수 판별 / GCD / LCM) 진입 예정
profile
Yesol Lee
문서화를 좋아하는 개발자
이전 포스트

20260423 오늘의 학습: 인덱스+값 병렬 패턴과 그리디 개념

다음 포스트

20260427 오늘의 학습: 수학 기초 (소수 판별, 약수, GCD, LCM)

0개의 댓글