14 / 14강

탐색과 해싱, 상황에 맞게 고르기

회원 번호로 한 사람을 찾는 일과 번호가 100번부터 200번인 사람을 모두 찾는 일은 다릅니다. 정확히 특정 키를 찾는지, 순서나 범위까지 필요한지가 선택 기준입니다.

정렬된 배열에서 절반씩 줄이기

이진 탐색은 가운데 값과 비교해 탐색 범위의 절반을 버립니다. 배열이 미리 정렬되어 있어야 합니다.

def binary_search(values, target):
    left, right = 0, len(values) - 1
    while left <= right:
        mid = (left + right) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(binary_search([4, 9, 15, 22, 31], 22))
print(binary_search([4, 9, 15, 22, 31], 10))

출력은 인덱스 3, 찾지 못했다는 뜻의 -1입니다. 빈 배열도 반복문에 들어가지 않고 -1을 반환합니다. 탐색은 O(log n)이지만, 정렬되지 않은 자료라면 정렬 비용이 먼저 듭니다.

키로 저장 위치를 계산하는 해싱

해시 함수는 키를 해시 값으로 바꾸고, 해시 테이블은 이를 이용해 저장할 칸을 정합니다. 예를 들어 키 % 4를 쓰면 3과 7은 모두 3번 칸으로 갑니다. 서로 다른 키가 같은 칸에 도착하는 일을 충돌이라고 합니다.

• 체이닝: 같은 칸에 속한 항목을 별도 목록으로 연결합니다.
• 개방 주소법: 테이블 안의 다른 빈 칸을 정해진 규칙으로 찾습니다.
• 찾을 때는 해시 값뿐 아니라 실제 키도 비교해야 합니다.

Python의 dict와 set은 해시 테이블을 사용합니다. 적절한 해시 분포를 가정하면 조회는 평균 O(1)이지만, 충돌이 몰리면 최악에 O(n)이 될 수 있습니다. 이 비용 설명은 키의 해시 계산과 비교 비용을 일정하다고 놓은 것입니다.

마지막 연습: 작은 서비스 설계

음악 앱을 만든다고 합시다. 다음 기능에는 어떤 구조를 쓰겠습니까?

1. 곡 번호로 제목 찾기
2. 재생 대기 중인 곡을 등록 순서대로 꺼내기
3. 최근 편집을 하나씩 취소하기
4. 곧 시작할 예약 작업부터 실행하기
5. 사용자 사이의 친구 관계 표현하기

문제를 푸는 전략을 더 배우려면 알고리즘 강좌로 이어 가세요.