자료구조·알고리즘 복잡도 정리

없는 값을 이진 탐색하면 어디에서 멈출까?

오름차순 배열에서 20을 찾습니다. 인덱스는 0부터 시작하고 low와 high를 모두 포함하는 구간을 사용합니다. 중앙값 비교 횟수와 최종 반환값을 구하세요.

Python 3

def find(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        print(low, high, mid, values[mid])
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(find([3, 8, 12, 17, 23, 29, 34], 20))

넓은 표는 좌우로 밀어 나머지 열을 볼 수 있습니다.

풀이 순서

1. 17보다 큰 쪽만 남긴 뒤 29보다 작은 쪽을 남기면 인덱스 4 하나만 남습니다. 그 원소 23도 20이 아니므로 마지막 후보를 제외합니다.
2. 중앙 원소를 세 번 확인한 후 low > high가 되어 -1을 반환합니다. -1은 배열 원소가 아니라 이 함수가 정한 실패 표시입니다. 20을 정렬 순서대로 삽입할 위치 4와도 다릅니다.
3. 검색값만 23으로 바꾸면 같은 세 중앙 원소를 거쳐 인덱스 4를 반환합니다. 마지막 단일 원소 구간도 검사해야 하므로 이 코드에서 while low < high로 바꾸면 23을 놓칩니다.

확인 결과

0 6 3 17
4 6 5 29
4 4 4 23
-1

틀리기 쉬운 지점: 정렬 여부, 끝 인덱스 포함 여부, 반환값이 위치인지 원소 값인지 먼저 구별하세요. 로그 복잡도라는 말만으로 특정 입력의 정확한 비교 횟수가 정해지지는 않습니다.

BFS의 방문 순서와 최단 경로는 같은 목록이 아니다

무방향·무가중치 그래프에서 A부터 탐색합니다. 인접 정점은 알파벳 순서로 확인하며 큐에 넣을 때 방문 처리합니다. F까지 최소 간선 수와 경로를 구하세요.

Python 3

from collections import deque

graph = {
    'A': ['B', 'C'], 'B': ['A', 'D'],
    'C': ['A', 'E'], 'D': ['B', 'E'],
    'E': ['C', 'D', 'F'], 'F': ['E']
}
queue = deque(['A'])
parent = {'A': None}
order = []
while queue:
    current = queue.popleft()
    order.append(current)
    for neighbor in graph[current]:
        if neighbor not in parent:
            parent[neighbor] = current
            queue.append(neighbor)
path = []
current = 'F'
while current is not None:
    path.append(current)
    current = parent[current]
print(' '.join(order))
print(' -> '.join(reversed(path)))
print(len(path) - 1)

넓은 표는 좌우로 밀어 나머지 열을 볼 수 있습니다.

풀이 순서

1. 방문 순서는 A B C D E F이지만 B와 C 사이에는 간선이 없습니다. 방문 목록을 그대로 이어 붙여 경로라고 할 수 없습니다.
2. F의 부모 E, E의 부모 C, C의 부모 A를 거꾸로 따라가면 A → C → E → F입니다. 정점 4개를 잇는 간선은 3개입니다.
3. BFS는 거리가 같은 층을 먼저 처리합니다. 이웃 순서를 바꾸면 같은 길이의 경로 선택은 달라질 수 있지만 최소 간선 수는 같습니다. 간선 비용이 제각각이면 최소 간선 경로와 최소 비용 경로는 다를 수 있습니다.

확인 결과

A B C D E F
A -> C -> E -> F
3

틀리기 쉬운 지점: 큐에서 꺼낼 때까지 방문 표시를 미루면 한 정점이 여러 번 큐에 들어갈 수 있습니다. 이 예제는 삽입 시 부모를 기록하여 중복 삽입을 막습니다.

검증 방법과 참고 문서

게시한 Python 코드를 실제 실행하고, 별도 탐색으로 구간·큐·부모와 경로 길이를 대조합니다. 비어 있는 배열, 끝 원소, 단일 원소 구간도 검사합니다.

예제·데이터·풀이표: 정처LAB 자체 설계 · AI 보조 작성 및 로컬 검증 · 예제 수정일 2026-09-27

• Princeton Algorithms: BFS와 최소 간선 경로
• Python: 정렬 배열의 탐색과 삽입 위치 구분