알고리즘 선택·경계 검사·다음 학습
문제 제약에 맞는 방법을 고르고 작은 입력 비교와 증명 역할을 정리합니다.
한 알고리즘을 외웠다고 다른 문제에 바로 적용할 수는 없습니다. 목표는 입력 구조·출력 요구·성능 조건을 근거로 방법을 고르고 검사 범위를 솔직히 기록하는 것입니다. 핵심 1~11장과 종합 경로 문제를 복습하세요.
개념과 약속
미정렬 목록에서 대상 값의 첫 위치를 찾을 때는 순차 탐색, 이미 정렬된 목록에서는 이진 탐색을 사용합니다. 안정성이 필요하면 이 교재의 병합·삽입 버전을, 최악 정렬 시간 보장이 필요하면 병합·힙을 검토합니다. 비음수 정수 자릿수를 사용할 수 있으면 기수 정렬을 고려합니다. 무가중 최소 간선 수는 BFS, 비음수 최소 비용은 Dijkstra, 모든 쌍의 도달 가능성은 Warshall, 모든 쌍의 최소 비용은 Floyd–Warshall을 문제 크기에 맞춰 검토합니다.
검사는 명세를 사례로 구체화합니다. 빈 입력·하나·중복·정렬/역순·없음·모두 같음·0 비용·음수 거부·도달 불가능·겹치는 문자열·해시 충돌을 필요에 맞게 고릅니다. 작은 입력을 전수 생성해 독립적인 쉬운 방법과 비교하면 특히 경계를 잘 찾습니다. 하지만 제한된 범위의 성공이 모든 입력의 증명은 아닙니다.
분할 정복·탐욕·DP·백트래킹은 접근 방식이고 자료 구조·입력 조건과 함께 선택합니다. 근사·분기 한정·병렬·분산·양자 알고리즘은 서로 다른 정확성·실행 모델을 가진 후속 분야입니다. 이 교재는 그 이름을 분류로 소개하되 구현 학습을 끝냈다고 주장하지 않습니다.
손으로 상태 추적하기
| 문제의 핵심 | 먼저 물을 조건 | 여기의 시작 단원 |
|---|---|---|
| 탐색 | 정렬되어 있는가·첫 위치인가 | 3장 |
| 정렬 | 안정성·자료 크기·자릿수 | 4~6장,12장 |
| 경로 | 간선 수인가·비용인가·음수인가 | 7~8장 |
| 부분 문제 | 상태가 겹치는가·복원이 필요한가 | 9장 |
| 문자열 | 모든 위치·겹침·최악 비용인가 | 10장 |
알고리즘 이름보다 질문의 답이 선택을 결정합니다.
직접 실행하기
아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.
itertools.product([0,1,2], repeat=length)는 지정한 길이의 모든 값 조합을 생성합니다. ordered.index(target)는 있는 값의 첫 위치를 줍니다. 이 쉬운 참조와 직접 구현의 결과를 비교합니다.
def binary_search_first(values, target):
lo, hi = 0, len(values)
while lo < hi:
mid = (lo + hi) // 2
if values[mid] < target:
lo = mid + 1
else:
hi = mid
if lo < len(values) and values[lo] == target:
return lo
return -1
def sift_down(values, root, size):
while 2 * root + 1 < size:
child = 2 * root + 1
if child + 1 < size and values[child + 1] > values[child]:
child += 1
if values[root] >= values[child]:
return
values[root], values[child] = values[child], values[root]
root = child
def build_max_heap(values):
result = list(values)
for root in range(len(result) // 2 - 1, -1, -1):
sift_down(result, root, len(result))
return result
def heap_sort(values):
result = build_max_heap(values)
for end in range(len(result) - 1, 0, -1):
result[0], result[end] = result[end], result[0]
sift_down(result, 0, end)
return result
def prefix_function(pattern):
prefix = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j and pattern[i] != pattern[j]:
j = prefix[j - 1]
if pattern[i] == pattern[j]:
j += 1
prefix[i] = j
return prefix
def kmp_matches(text, pattern):
if not pattern:
return list(range(len(text) + 1))
prefix = prefix_function(pattern)
matches, j = [], 0
for i, character in enumerate(text):
while j and character != pattern[j]:
j = prefix[j - 1]
if character == pattern[j]:
j += 1
if j == len(pattern):
matches.append(i - len(pattern) + 1)
j = prefix[j - 1]
return matches
from itertools import product
count = 0
for length in range(5):
for values in product([0, 1, 2], repeat=length):
values = list(values)
ordered = sorted(values)
assert heap_sort(values) == ordered
for target in [-1, 0, 1, 2, 3]:
expected = ordered.index(target) if target in ordered else -1
assert binary_search_first(ordered, target) == expected
count += 1
assert kmp_matches("AAAA", "AA") == [0, 1, 2]
print("전수 입력", count)
print("범위 내 검사 통과")실행 결과:
전수 입력 121
범위 내 검사 통과왜 맞고 언제 끝나는가
길이 0~4, 값 2의 모든 목록 수는 1+3+9+27+81=121입니다. 정렬은 Python 참조와, 첫 위치는 쉬운 직접 계산과 비교합니다. 검사 자체가 빠뜨린 입력 조건이 없는지도 기록합니다. 보편 정확성은 각 본문의 불변조건·점화식·종료 설명으로 계속 확인해야 합니다.
비용과 적용 범위
이 검사는 입력 생성 수에 비례해 늘며 실제 제품의 알고리즘 비용과 다릅니다. 전수 검사는 작은 범위에서 강하고 큰 범위에는 비용이 급격히 커집니다. 큰 자료는 대표 경계·무작위 시드 고정·성질 검사·실제 환경 측정을 조합합니다.
스스로 풀어 보기
- 음수가 있는 그래프의 최소 비용을 구할 때 'Dijkstra가 빠르다'는 이유만으로 선택할 수 있나요?
- 작은 검사만 통과한 구현을 보고 완료라고 기록하기 전에 적어야 할 세 가지를 쓰세요.
힌트
- 속도보다 적용 조건이 먼저입니다.
- 실제 실행한 범위와 아직 하지 않은 검토를 구분합니다.
해설
- 안 됩니다. 음수 조건을 처리할 수 있는 알고리즘으로 바꾸거나 입력 약속을 정당하게 바꿔야 합니다.
- 검사 입력 범위·비교 기준·미검증 조건을 적습니다. 예컨대 길이 0~4의 정수 목록 121개를 참조와 비교했지만 모든 크기·자료형의 검토는 아니라는 기록입니다.
흔한 오해
PEIM 같은 시험용 요약에서 용어를 확인할 수 있어도 이 교재의 준비·실행·증명을 대신하지 않습니다. 자습의 완료 기준은 이름 기억보다 새 입력을 추적하고 조건을 설명하는 능력입니다.
복습과 다음 연결
다음 학습은 선택 심화 12장 복습, 프로그래밍 언어의 자료구조 구현, 이산수학의 증명·그래프, 운영체제의 스케줄링 등으로 연결할 수 있습니다. 이 교재 안에서 막히면 Python 준비, 정확성, 자료 표현으로 돌아가세요.