알고리즘은 문제의 입력을 올바른 출력으로 바꾸는 계산 절차다. 이 문서는 탐색·정렬·완전 탐색·탐욕법·동적 계획법·그래프를 실제 예제로 설명하고, 정확성의 근거와 시간·공간 비용, 전제 위반과 검증 방법을 함께 다룬다.
알고리즘은 무엇을 정하는가
알고리즘은 주어진 문제를 해결하기 위해 수행하는 명확한 절차다. 프로그램이 특정 언어와 실행 환경에서 동작하는 구현이라면, 알고리즘은 그 구현이 따라야 하는 계산의 방법에 초점을 둔다. 같은 탐색 절차를 Python, Java, C++로 구현할 수 있지만 자료 표현과 언어별 연산 비용 때문에 실제 성능은 달라질 수 있다.
예를 들어 고객 목록에서 ID가 같은 고객을 찾는 문제에는 처음부터 하나씩 비교하는 방법, ID 순서로 정렬한 뒤 범위를 절반씩 줄이는 방법, ID를 키로 하는 사전을 미리 만드는 방법이 있다. 어느 방법이 좋은지는 목록의 크기뿐 아니라 조회 횟수, 갱신 빈도, 준비 비용과 메모리 제한에 따라 달라진다. 문제를 풀 수 있다는 사실과 상황에 적합하다는 판단을 구분해야 한다.
알고리즘 설명에는 입력과 출력, 허용 조건, 절차, 올바름의 근거, 필요한 자원이 함께 있어야 한다. 이름과 복잡도만 외우면 적용할 수 없는 입력에 잘못 사용하는 일이 생긴다. 이 문서는 작은 예제를 실행해 결과를 관찰하고, 왜 맞는지와 언제 다른 방법이 필요한지를 연결해서 설명한다. Python 예제는 각각 독립적으로 실행하며 외부 패키지와 네트워크를 사용하지 않는다.
문제를 먼저 명세하기
“가장 좋은 경로를 찾는다”는 문장만으로는 구현을 정할 수 없다. 간선 수가 가장 적은 경로인지, 거리나 요금의 합이 최소인 경로인지, 경유지 제한이 있는지에 따라 문제가 달라진다. 출발지와 도착지가 같거나 도착할 수 없을 때 무엇을 반환하는지도 정해야 한다.
검색 문제에서도 값의 존재 여부, 아무 위치 하나, 첫 위치, 모든 위치는 다른 출력 계약이다. 중복 값이 있을 때 어느 것을 고르는지 정하지 않으면 두 구현이 서로 다른 결과를 내도 둘 다 맞는지 판단하기 어렵다. 입력이 정렬되어 있다는 조건이 있다면 함수 설명과 호출 경계에 드러내야 한다.
정렬의 경우 출력이 오름차순인 것만으로 충분하지 않다. 입력에 있던 원소와 개수가 보존되어야 한다. [1, 2, 3]을 어떤 입력에도 반환하는 프로그램은 정렬된 결과를 내지만 정렬 알고리즘은 아니다. 원본을 변경해도 되는지, 같은 키의 순서를 보존해야 하는지, 비교 기준이 일관적인지도 명세에 포함한다.
명세를 구체적으로 쓰면 테스트도 자연스럽게 정해진다. 빈 입력, 하나의 원소, 중복, 찾는 값이 없음, 최대 크기와 경계값을 어떻게 처리할지 먼저 적는다. 코드가 나온 뒤 현재 동작에 맞춰 요구사항을 붙이는 것보다 설계의 오류를 일찍 발견할 수 있다.
첫 예제: 선형 탐색과 반환 계약
선형 탐색은 앞에서부터 원소를 하나씩 확인한다. 아래 함수는 첫 번째 일치 위치를 반환하고 없으면 None을 반환한다. [8, 3, 8, 5]에서 8의 결과는 0이고 7의 결과는 None이다. 중복 중 첫 위치라는 계약이 반복 방향과 즉시 반환으로 구현되어 있다.
이미 확인한 위치에는 찾는 값이 없다는 사실을 유지하면서 다음 원소로 진행한다. 일치하면 그보다 앞에는 일치가 없으므로 반환 위치가 첫 위치다. 끝까지 일치하지 않으면 모든 원소를 확인했으므로 없다는 결론을 낼 수 있다. 작은 함수에서도 이런 논리를 말할 수 있으면 경계 조건을 이해하기 쉽다.
최악의 경우 n개 원소를 비교하므로 비교 횟수는 O(n)이다. 첫 원소에서 찾으면 한 번만 비교한다. 이처럼 최선과 최악의 경우는 다르다. 평균을 말하려면 찾는 위치나 실패 확률에 대한 가정이 필요하다. “평균은 대략 절반”이라는 말도 모든 데이터 분포에서 자동으로 성립하지 않는다.
예제 코드
def first_index(values, target):
for index, value in enumerate(values):
if value == target:
return index
return None
print(first_index([8, 3, 8, 5], 8))
print(first_index([8, 3, 8, 5], 7))
print(first_index([], 7))실행 결과
0
None
None정확성: 반복 불변식과 종료
반복 불변식은 반복을 시작할 때마다 유지되는 성질이다. 최대값을 찾는 루프라면 “현재 best는 지금까지 확인한 원소의 최대값”이라는 설명을 사용할 수 있다. 첫 원소로 초기화하면 성질이 성립하고, 다음 원소와 비교해 더 큰 것을 저장하면 유지된다. 모든 원소를 확인했을 때 전체 최대값이라는 결론을 얻는다.
초기화·유지·종료 후 결론을 나눠 보면 코드가 왜 맞는지 구조적으로 설명할 수 있다. 최대값의 초기값을 무조건 0으로 두면 모든 수가 음수일 때 틀린다. 루프 본문이 아니라 초기 조건이 불변식을 깨뜨린 사례다. 빈 입력에 대해서는 최대값이 없으므로 예외, None, 별도 기본값 중 계약을 정한다.
정확한 결과를 내는 것과 반드시 끝나는 것도 구분한다. 이진 탐색에서 범위를 줄이는 대입을 잘못하면 특정 입력에서 같은 구간을 반복할 수 있다. 남은 구간 길이처럼 매 단계 감소하는 음이 아닌 양을 찾으면 종료 근거를 설명하기 쉽다.
테스트는 선택한 입력에서 동작을 확인하지만 모든 가능한 입력의 증명을 대신하지는 않는다. 반대로 수학적 증명이 있다고 실제 코드의 오타나 자료형 범위 문제까지 사라지는 것도 아니다. 절차의 논리와 구현 검증을 함께 사용한다.
예제 코드
def maximum(values):
if not values:
raise ValueError('empty input')
best = values[0]
for value in values[1:]:
if value > best:
best = value
return best
print(maximum([-9, -2, -7]))
try:
maximum([])
except ValueError as error:
print(error)실행 결과
-2
empty input시간과 공간을 세는 기준
시간 복잡도는 입력 크기에 따라 필요한 연산이 어떻게 증가하는지 분석하는 방법이다. 모든 명령을 실제 초 단위로 예측하는 공식은 아니다. n이 원소 수인지 문자열 길이인지 정점 수인지 먼저 정하고, 비교나 덧셈 같은 기본 연산을 어떤 비용으로 보는지 명시한다.
O(n), O(n log n), O(n²)는 증가율을 비교할 때 유용하지만 실제 실행 시간의 순위를 모든 크기에서 고정하지는 않는다. 상수 비용, 메모리 접근, 구현 언어와 캐시가 영향을 준다. 작은 입력에서 간단한 이중 반복이 복잡한 자료 구조보다 빠를 수도 있으나 입력이 커지면 증가율 차이가 더 중요해질 수 있다.
공간은 입력 저장 공간과 추가 작업 공간, 출력 공간을 나눠 설명하면 좋다. 앞 절의 maximum 예제는 values[1:]라는 슬라이스를 만들기 때문에 Python에서는 추가 원소 참조 배열이 생긴다. 추상적인 최대값 탐색은 상수 추가 공간으로 가능하지만 그 구현은 그렇지 않다. 실제 코드를 보고 분석해야 하는 이유다.
정수가 커지면 덧셈·곱셈 자체의 비용도 커질 수 있다. 무한 정밀도 정수를 사용하는 언어에서 값의 비트 수를 무시하고 모든 연산을 상수 시간으로 보는 것은 분석 모델의 단순화다. 암호나 큰 수 계산에서는 비트 길이를 입력 크기로 다루는 것이 특히 중요하다.
자료 구조와 전처리 비용
같은 검색 문제라도 자료 구조에 따라 비용을 분배하는 방식이 달라진다. 목록을 매번 순회하면 준비 비용은 작지만 조회마다 많은 비교가 필요하다. 사전을 만들면 구축과 메모리 비용을 들이는 대신 반복 조회를 빠르게 할 수 있다. 한 번만 조회하는 작은 목록과 수백만 번 조회하는 고정 자료는 다른 선택이 합리적이다.
아래는 ID를 키로 고객 이름을 저장한다. 조회 결과는 Ada와 missing이다. 이 예제의 ID는 유일하다고 가정한다. 중복 ID가 있으면 사전 생성 과정에서 뒤 값이 앞 값을 덮어쓸 수 있으므로, 중복을 오류로 볼지 여러 항목을 묶을지 별도로 정해야 한다.
해시 기반 조회를 상수 시간이라고 설명할 때는 해시 계산과 충돌, 적재율 등에 관한 가정이 있다. 긴 문자열 키를 처음 해시하는 비용이나 악의적인 입력까지 항상 같은 비용이라고 단정하면 안 된다. 또한 검색이 빠른 자료 구조가 범위 조회나 정렬된 순회에도 가장 적합한 것은 아니다.
예제 코드
customers = [(17, 'Ada'), (23, 'Lin'), (41, 'Sam')]
by_id = dict(customers)
print(by_id.get(17, 'missing'))
print(by_id.get(99, 'missing'))실행 결과
Ada
missing이진 탐색: 찾을 범위를 절반으로 줄이기
이진 탐색은 정렬처럼 비교 결과를 이용해 한쪽 구간을 버릴 수 있는 구조를 사용한다. 아래 lower_bound는 target 이상인 첫 원소의 위치를 반환한다. 모든 원소가 작으면 배열 길이를 반환한다. 같은 값이 여러 번 있어도 가장 왼쪽 경계를 찾는 계약이다.
[2, 4, 4, 9]에서 4의 경계는 1이고 5의 경계는 3이다. 10의 경계는 4로 실제 원소 인덱스 범위를 벗어나지만 삽입 위치로는 유효하다. 경계 위치를 얻었다고 값을 찾았다는 뜻은 아니다. 위치가 길이보다 작은지와 해당 값이 target인지 확인해야 존재 여부를 알 수 있다.
루프는 [lo, hi)라는 반열린 구간을 사용한다. mid 값이 target보다 작으면 mid까지는 후보가 아니므로 lo를 mid+1로 옮긴다. 그렇지 않으면 mid가 답일 수도 있으므로 hi를 mid로 옮긴다. 각 단계에서 구간이 줄어들고 lo==hi일 때 경계가 정해진다.
비교 횟수는 O(log n)이지만 임의 위치 접근이 빠르다는 전제가 있다. 연결 리스트에서 중간 노드까지 매번 걸어가면 같은 비용이 되지 않는다. 검색 전에 매번 정렬한다면 정렬 비용까지 포함해 선형 탐색과 비교해야 한다.
예제 코드
def lower_bound(values, target):
lo, hi = 0, len(values)
while lo < hi:
mid = lo + (hi - lo) // 2
if values[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
values = [2, 4, 4, 9]
for target in [4, 5, 10]:
print(lower_bound(values, target))실행 결과
1
3
4전제 위반과 경계 오류를 재현하기
정렬되지 않은 배열에 이진 탐색을 적용하면 답이 보장되지 않는다. [9, 1, 5]에서 1을 찾는 과정을 생각하면 중간 값이 1이라는 사실만으로 왼쪽의 9와 오른쪽의 5를 정렬된 구간처럼 해석할 수 없다. 비교 결과로 버리는 쪽에 답이 없다는 논리가 성립하지 않는다.
또 다른 흔한 오류는 lo=mid로 갱신하는 것이다. 길이 1인 구간에서는 mid가 lo와 같을 수 있어 범위가 줄지 않는다. 아래 예제는 실제 무한 반복 대신 한 단계만 계산해 lo와 hi가 그대로 0,1임을 보여준다. 수정은 반열린 구간의 계약에 맞게 lo=mid+1로 옮기는 것이다.
경계 테스트에는 빈 배열, 길이 1, 모든 값보다 작은 target, 모든 값보다 큰 target, 중복 값과 모든 값이 같은 입력을 포함한다. 함수 내부에서 정렬 여부를 매번 선형 검사하면 전체 비용이 달라지므로, 전제 검증을 어디에서 한 번 수행하고 이후 어떻게 유지할지도 설계한다.
예제 코드
values = [2]
lo, hi = 0, len(values)
mid = (lo + hi) // 2
if values[mid] < 3:
lo = mid # 잘못된 갱신: 구간이 줄지 않는다.
print(lo, hi)
lo = mid + 1 # 이 경우의 올바른 갱신
print(lo, hi)실행 결과
0 1
1 1정렬: 순서·안정성·원본 변경
정렬은 이후의 탐색이나 묶음 처리에 사용할 구조를 만든다. 비교 기준이 무엇인지, 같은 키의 순서를 유지해야 하는지, 원본을 바꿔도 되는지 먼저 정한다. 이름을 사전순으로 정렬하는 것과 사람의 언어 규칙에 맞춰 정렬하는 것도 같지 않을 수 있다.
아래는 점수가 높은 순서로 정렬한다. Ada와 Sam의 점수가 같으므로 안정적인 정렬에서는 입력에서의 상대 순서가 유지된다. Python의 sorted는 새 목록을 반환하므로 원본의 첫 원소 Lin은 그대로다. 정렬된 결과와 원본 보존을 각각 확인한다.
비교 기반 정렬의 일반적인 하한은 입력 원소 사이의 비교만으로 순서를 알아내는 모델에 관한 것이다. 작은 범위 정수를 세는 계수 정렬처럼 다른 정보를 사용하는 방법에 같은 하한을 무조건 적용하면 안 된다. 반대로 특수한 정수 정렬의 효율을 임의의 객체나 문자열 비교에 그대로 기대해서도 안 된다.
실무에서는 학습용 정렬을 직접 구현하기보다 검증된 표준 라이브러리를 우선 검토한다. 직접 구현은 원리와 제약을 배우거나 특수한 요구를 해결할 때 의미가 있다. 라이브러리를 사용해도 비교 키 계산 비용, 메모리 사용과 안정성 계약은 이해해야 한다.
예제 코드
rows = [('Lin', 80), ('Ada', 90), ('Sam', 90)]
ranked = sorted(rows, key=lambda row: -row[1])
print([name for name, score in ranked])
print(rows[0][0])실행 결과
['Ada', 'Sam', 'Lin']
Lin분할 정복: 병합 정렬의 계산 흐름
분할 정복은 문제를 작은 부분 문제로 나누고 각각 해결한 결과를 결합한다. 병합 정렬은 배열을 둘로 나눠 정렬한 뒤 두 정렬된 목록을 합친다. 부분 결과가 이미 정렬되어 있다는 성질 덕분에 두 목록의 맨 앞 후보만 비교하면서 다음 원소를 고를 수 있다.
아래 [7, 2, 5, 2]는 [7, 2]와 [5, 2]로 나뉘고, 각 부분이 [2, 7]과 [2, 5]가 된 뒤 [2, 2, 5, 7]로 합쳐진다. 결과에 같은 값 2가 두 번 남아야 한다. 집합으로 바꿔 중복을 없애면 정렬이 아니라 다른 문제를 푼 것이다.
각 단계에서 합치는 총 원소 수는 n에 비례하고 분할 깊이는 log n에 비례하므로 비교와 이동 비용을 상수로 보는 모델에서 O(n log n)이다. 이 Python 구현은 슬라이스와 새 목록을 사용하므로 제자리 정렬이 아니다. 동시에 살아 있는 추가 저장 공간과 전체 실행 중 생성한 누적 자료량도 구분한다.
재귀의 기저 조건은 길이 0 또는 1이다. 분할할 때 항상 더 작은 문제로 내려가야 종료한다. 같은 값을 만났을 때 왼쪽을 먼저 고르는 규칙은 안정성을 유지하는 병합의 핵심이지만, 일반 레코드로 확장할 때는 비교 키와 원본 항목의 관계를 명시해야 한다.
예제 코드
def merge_sort(values):
if len(values) <= 1:
return list(values)
mid = len(values) // 2
left = merge_sort(values[:mid])
right = merge_sort(values[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([7, 2, 5, 2]))
print(merge_sort([]))실행 결과
[2, 2, 5, 7]
[]완전 탐색: 작은 문제의 기준 해법
완전 탐색은 가능한 후보를 빠짐없이 살펴 조건을 만족하는 답을 찾는 방법이다. 후보 수가 작으면 가장 명확하고 검증하기 쉬운 해법이 될 수 있다. 빠른 알고리즘을 만들기 전 작은 입력에 대한 정답 판정기로 사용하기도 한다.
아래는 합이 10인 두 원소의 인덱스를 모두 찾는다. i보다 큰 j만 검사하므로 같은 원소를 두 번 쓰거나 (i,j)와 (j,i)를 중복 출력하지 않는다. [2, 7, 3, 8]에서 결과는 (0,3)과 (1,2)다. 값이 같더라도 인덱스가 다른 두 항목을 허용할지 계약에 따라 처리한다.
후보 쌍 수는 n(n-1)/2이므로 O(n²)이다. 존재 여부나 한 쌍만 필요하다면 사전 기반 방법으로 바꿀 수 있지만 모든 쌍을 출력해야 하는 경우 결과 자체가 많을 수 있다. 출력 크기의 비용을 빼고 “항상 선형 시간”이라고 주장하면 잘못된 비교가 된다.
예제 코드
def pairs_with_sum(values, target):
result = []
for i in range(len(values)):
for j in range(i + 1, len(values)):
if values[i] + values[j] == target:
result.append((i, j))
return result
print(pairs_with_sum([2, 7, 3, 8], 10))실행 결과
[(0, 3), (1, 2)]탐욕법: 당장의 선택을 정당화해야 한다
탐욕법은 각 단계에서 정한 기준에 따라 가장 좋아 보이는 선택을 하고 진행한다. 코드가 간단할 수 있지만 지역적인 선택이 전체 최적해를 보장한다는 근거가 필요하다. 문제의 구조에 맞는 교환 논증이나 불변식을 제시할 수 있어야 한다.
동전 수를 최소화하는 문제에서 큰 동전부터 고르는 전략은 모든 화폐 체계에 맞지 않는다. 단위가 1,3,4이고 금액이 6이면 탐욕법은 4+1+1로 세 개를 고르지만 3+3은 두 개다. 아래 코드는 바로 이 반례를 출력한다. 익숙한 통화에서 잘 동작했다는 경험을 임의 단위에 일반화한 오류다.
반례 하나는 특정 전략이 항상 맞다는 주장을 반박하지만, 많은 성공 사례는 항상 맞음을 증명하지 않는다. 탐욕법을 채택할 때는 입력 제한과 최적성 근거를 함께 적고, 그 제한이 바뀌면 다시 검토한다. 최적해가 필요 없는 휴리스틱이라면 보장하지 않는 범위도 분명히 표시한다.
예제 코드
amount = 6
picked = []
for coin in [4, 3, 1]:
while amount >= coin:
amount -= coin
picked.append(coin)
print(picked)
print([3, 3])실행 결과
[4, 1, 1]
[3, 3]동적 계획법: 부분 문제의 답을 재사용하기
동적 계획법은 작은 상태의 답을 저장하고 더 큰 상태를 계산하는 데 재사용한다. 핵심은 표를 만드는 문법이 아니라 상태가 무엇을 의미하고 어떤 이전 상태로 답을 구성할 수 있는지 정하는 일이다. 동전 문제에서는 best[x]를 금액 x를 만드는 최소 동전 수로 정할 수 있다.
마지막에 사용하는 동전이 c라면 앞부분은 x-c를 만드는 문제다. 따라서 사용 가능한 c마다 best[x-c]+1을 비교하고 최소를 고른다. best[0]=0은 동전을 사용하지 않아도 금액 0을 만들 수 있다는 기저 상태다. 도달할 수 없는 금액은 별도 큰 값으로 표시한다.
아래 결과는 [1,3,4]로 6을 만들 때 2, [2,4]로 3을 만들 때 None이다. 탐욕법 반례를 올바르게 처리하면서 불가능한 경우도 구별한다. 이 구현은 동전 단위와 금액이 정수라는 전제에서 동작한다. 예제의 값 검사는 음수 금액과 양수가 아닌 단위를 막지만 모든 Python 자료형을 검증하는 범용 입력 계층은 아니다.
금액 A와 동전 종류 k에 대해 O(Ak)개의 전이를 검토하고 O(A) 공간을 사용한다. A가 이진수로 표현된 입력의 값이라는 점에 주의한다. A 자체에 비례하는 비용은 입력 비트 수에 대한 다항 시간과 같은 뜻이 아니며, 이를 의사다항 시간이라고 부르는 맥락이 있다.
예제 코드
def minimum_coins(coins, amount):
if amount < 0 or any(c <= 0 for c in coins):
raise ValueError('positive coins and nonnegative amount required')
unreachable = amount + 1
best = [0] + [unreachable] * amount
for value in range(1, amount + 1):
for coin in coins:
if coin <= value:
best[value] = min(best[value], best[value - coin] + 1)
return None if best[amount] == unreachable else best[amount]
print(minimum_coins([1, 3, 4], 6))
print(minimum_coins([2, 4], 3))실행 결과
2
None메모이제이션과 표 채우기
재귀 함수가 같은 부분 문제를 여러 번 계산한다면 결과를 저장하는 메모이제이션이 도움이 된다. 피보나치 수의 단순 재귀는 F(n-1)과 F(n-2)를 계산하는 과정에서 같은 값들을 반복해서 구한다. 캐시를 사용하면 각 n의 결과를 재사용할 수 있다.
아래 fib(10)은 55를 반환한다. 하지만 캐시는 결과 저장 공간을 사용하며 재귀 깊이도 남는다. n이 매우 크면 반복문으로 상태 두 개만 유지하는 방식이 더 적합할 수 있다. 여기서 필요한 결과가 마지막 수 하나인지 중간 수 모두인지에 따라 저장 전략도 달라진다.
메모이제이션은 필요한 상태에서 재귀적으로 시작하고, 바닥부터 표를 채우는 방식은 의존 순서에 따라 상태를 계산한다. 어느 쪽이든 상태 의존성에 순환이 있는지, 기저 상태가 충분한지, 캐시 키가 결과를 결정하는 모든 입력을 포함하는지 확인한다. 외부 상태가 변하는 함수에 이전 결과를 무조건 재사용하면 잘못된 값을 얻을 수 있다.
피보나치 계산을 O(n)번 덧셈이라고 세는 것과 비트 연산 비용을 포함하는 분석은 다르다. 결과의 자릿수가 증가하므로 큰 정수 덧셈을 항상 한 단위로 볼 수는 없다. 알고리즘 설명에서 어떤 비용 모델을 사용했는지 표시해야 한다.
예제 코드
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 0:
raise ValueError('nonnegative n required')
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10))
print(fib(0))실행 결과
55
0그래프로 모델링하기
그래프는 정점과 정점 사이의 관계인 간선으로 문제를 나타낸다. 웹 문서와 링크, 작업과 선행 조건, 장소와 이동 가능성처럼 여러 관계를 모델링할 수 있다. 관계에 방향이 있는지, 가중치가 있는지, 같은 두 정점 사이에 간선이 여러 개 있을 수 있는지 먼저 결정한다.
무방향 길을 인접 목록으로 저장할 때는 보통 양쪽 정점에 연결을 넣어야 한다. 한쪽만 넣으면 알고리즘이 아니라 입력 표현이 다른 그래프를 만들게 된다. 간선이 없는 정점도 그래프에 존재할 수 있으므로 간선에서 등장한 이름만 모으면 고립 정점을 빠뜨릴 수 있다.
인접 목록은 실제 간선을 중심으로 저장하고 인접 행렬은 모든 정점 쌍의 관계를 표로 저장한다. 간선이 적은 그래프에서 행렬을 사용하면 O(V²) 공간이 부담될 수 있지만 임의 두 정점의 연결 여부를 빠르게 확인하는 데는 단순하다. 필요한 연산과 밀도를 보고 선택한다.
같은 그래프 알고리즘도 표현에 따라 비용이 달라진다. 인접 목록에서 이웃만 순회하는 것과 행렬에서 매번 모든 정점을 확인하는 것은 다른 작업량이다. V와 E를 따로 표시하면 정점 수와 간선 수의 영향을 구분할 수 있다.
너비 우선 탐색: 간선 수가 가장 적은 경로
너비 우선 탐색(BFS)은 시작점에서 한 간선으로 갈 수 있는 정점, 두 간선으로 갈 수 있는 정점처럼 거리를 층별로 확장한다. 모든 간선 비용이 같은 그래프에서 처음 발견한 경로의 간선 수가 최소라는 성질을 이용한다. 가중치가 서로 다른 비용 최소 문제에 그대로 적용하지 않는다.
아래 그래프에서 A에서 D까지의 경로는 A-B-D다. A-C-D도 같은 길이지만 인접 목록 순서에 따라 B를 먼저 발견한다. 최단 경로가 여러 개일 때 어떤 하나를 반환한다는 계약이며 사전순 최소 경로를 별도로 보장하는 구현은 아니다. 고립 정점 X까지는 None이다.
parent는 방문 여부와 경로 복원 정보를 함께 저장한다. 큐에 넣는 순간 표시하므로 같은 정점이 여러 부모에게 반복해서 들어가는 일을 막는다. 목표를 찾으면 부모를 거슬러 올라가 뒤집어서 출발지부터의 경로를 만든다.
인접 목록과 적절한 큐를 쓰면 탐색 시간은 O(V+E), 추가 방문 정보는 O(V)다. Python 목록의 맨 앞 pop을 반복하면 원소 이동 비용이 추가되므로 deque.popleft를 사용했다. 정점 이름과 사전 연산의 비용을 일정하게 보는 분석이며 이 구현은 모든 이웃이 그래프 키로 등록되어 있다고 가정한다.
예제 코드
from collections import deque
def shortest_path(graph, start, goal):
if start not in graph or goal not in graph:
raise ValueError('unknown vertex')
parent = {start: None}
queue = deque([start])
while queue:
current = queue.popleft()
if current == goal:
path = []
while current is not None:
path.append(current)
current = parent[current]
return path[::-1]
for neighbor in graph[current]:
if neighbor not in parent:
parent[neighbor] = current
queue.append(neighbor)
return None
graph = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C'], 'X': []}
print(shortest_path(graph, 'A', 'D'))
print(shortest_path(graph, 'A', 'X'))실행 결과
['A', 'B', 'D']
None깊이 우선 탐색과 재귀의 수명
깊이 우선 탐색(DFS)은 한 갈래를 따라 가능한 곳까지 진행한 뒤 돌아와 다른 갈래를 탐색한다. 연결 여부, 순환 탐지, 위상 정렬 같은 문제의 기반이 된다. BFS와 달리 처음 발견한 경로가 간선 수 최소라는 보장은 없다.
재귀 구현은 호출 스택이 돌아갈 위치를 저장하므로 간결하지만 깊은 그래프에서 실행 환경의 재귀 제한을 만날 수 있다. 명시적 스택을 사용하면 호출 깊이 문제를 줄일 수 있으나 방문 시점과 이웃을 넣는 순서에 따라 탐색 순서가 달라질 수 있다. 순서 자체가 요구사항인지 단순한 관찰 결과인지 구분한다.
방향 그래프의 순환 탐지는 단순한 방문 집합만으로 충분하지 않은 경우가 있다. 현재 재귀 경로에 있는 정점과 탐색을 끝낸 정점을 구별해야 한다. 이미 방문한 정점으로 향하는 모든 간선을 순환이라고 판단하면 서로 다른 경로가 같은 정점에 합류하는 경우를 잘못 처리한다.
재귀를 반복문으로 바꿀 때는 “어떤 정점을 방문할 것인가”뿐 아니라 “자식 처리가 끝난 뒤 어떤 작업을 할 것인가”도 보존해야 한다. 후위 순회나 종료 시각이 필요한 알고리즘은 스택에 실행 단계를 함께 저장하는 방식이 필요할 수 있다.
가중치 최단 경로와 다익스트라의 전제
가중치가 있으면 간선 수가 적은 경로가 비용도 작다고 할 수 없다. A에서 D로 바로 가는 비용이 10이고 A-B-D의 비용이 각각 2와 3이라면 두 간선을 거치는 경로가 더 싸다. BFS의 거리와 가중치 합을 혼동하면 다른 문제를 풀게 된다.
다익스트라 알고리즘은 음수가 아닌 간선 가중치에서 현재 알려진 거리가 가장 작은 후보를 선택해 확장한다. 이미 확정한 거리가 나중에 더 작아지지 않는다는 논리에 비음수 조건이 중요하다. 음수 간선이 존재하는 문제에는 적용 조건을 다시 확인하고 벨만-포드 같은 다른 방법을 검토한다.
우선순위 큐에 개선된 거리를 새로 넣는 구현은 이전의 오래된 후보가 큐에 남을 수 있다. 꺼낸 거리와 현재 최선 거리를 비교해 오래된 항목을 건너뛰어야 불필요한 확장을 줄인다. 목적지까지 거리만 필요한지 실제 경로까지 필요한지에 따라 부모 정보도 저장한다.
가중치의 자료형과 범위도 알고리즘의 일부다. 매우 큰 정수의 합, 부동소수점 비교 오차, 도달 불가능을 나타내는 무한대 표기와 실제 유효한 값의 충돌을 검토한다. 길찾기 제품의 시간대별 통행 조건이나 동적으로 바뀌는 비용은 단일 고정 그래프 예제보다 더 복잡한 모델을 요구한다.
위상 정렬: 작업 순서와 순환 검출
위상 정렬은 방향 비순환 그래프에서 모든 선행 조건이 먼저 오도록 정점을 나열한다. 예를 들어 자료 읽기 후 변환, 변환 후 보고서 생성이라는 의존성이 있다면 그 순서를 지켜야 한다. 의존 관계가 없는 두 작업의 상대 순서는 여러 답이 가능하다.
진입 차수가 0인 작업부터 꺼내고, 그 작업에서 나가는 간선을 제거하면서 새로 진입 차수가 0이 된 작업을 후보에 넣는 방법을 사용할 수 있다. 모든 정점을 꺼냈다면 하나의 유효한 순서를 얻는다. 일부가 남았고 더 이상 후보가 없다면 순환 의존성을 의심할 수 있다.
선행 작업이 완료됐다는 의미와 단순히 순서 목록에 먼저 나열됐다는 의미는 다르다. 실제 병렬 실행 시스템에서는 실패·재시도·중복 실행과 자원 제한을 별도로 처리해야 한다. 위상 정렬은 실행 가능한 순서의 구조를 제공하지만 운영 스케줄러 전체를 대신하지 않는다.
결과 검증은 미리 정한 한 배열과 정확히 같아야 한다고 검사하기보다, 모든 정점이 한 번씩 포함되고 각 간선의 출발점이 도착점보다 앞에 있는지 확인하는 방식이 더 적절할 수 있다. 답이 여러 개인 문제에서 유효성 조건을 검사하는 사례다.
누적 합: 반복 질의를 위한 요약
고정된 숫자 목록에서 여러 구간의 합을 반복해서 묻는다면 매번 구간을 순회하는 대신 누적 합을 만들 수 있다. prefix[i]를 처음 i개 원소의 합으로 정의하면 반열린 구간 [left,right)의 합은 prefix[right]-prefix[left]다. 맨 앞에 0을 두면 left가 0인 경우도 같은 식으로 처리된다.
아래 [3,1,4,2]의 누적 합은 [0,3,4,8,10]이고 인덱스 1 이상 3 미만의 합은 5다. 원소 1과 4를 더한 결과다. 구간의 오른쪽 끝을 포함하는지 제외하는지를 코드와 설명에서 일관되게 유지해야 한다.
구축 비용은 O(n), 각 질의는 O(1)이지만 원본 값이 바뀌면 뒤쪽 누적 값에 영향을 준다. 갱신이 빈번하면 펜윅 트리나 세그먼트 트리 같은 다른 구조를 비교할 수 있다. 전처리로 얻는 빠른 질의에는 갱신 비용과 저장 공간의 대가가 있다.
예제 코드
values = [3, 1, 4, 2]
prefix = [0]
for value in values:
prefix.append(prefix[-1] + value)
left, right = 1, 3
print(prefix)
print(prefix[right] - prefix[left])실행 결과
[0, 3, 4, 8, 10]
5상위 k개와 전체 정렬의 차이
가장 큰 몇 개만 필요하다면 모든 원소를 완전히 정렬하는 것이 불필요할 수 있다. k개 후보를 유지하는 힙을 사용하면 일반적으로 O(n log k) 형태의 비용으로 처리할 수 있다. 단 k와 n의 관계, 정렬된 결과가 필요한지, 입력이 스트림인지에 따라 유리한 방법이 달라진다.
아래 heapq.nlargest는 점수 세 개를 큰 순서로 반환하여 [11,9,8]을 얻는다. 이 라이브러리 호출의 내부 전략은 조건에 따라 달라질 수 있으므로 모든 k에 대해 하나의 단순 구현을 실행한다고 단정하지 않는다. 핵심은 문제의 출력 요구를 전체 정렬보다 작게 정의할 수 있다는 점이다.
같은 점수의 항목을 어느 순서로 고를지, 중복 점수를 별도 항목으로 셀지, 여러 필드로 순위를 정할지도 필요하다. 실시간 순위에서 입력이 계속 바뀌면 삭제와 갱신을 지원하는 방법이 추가로 필요하다. 정적인 숫자 목록 예제를 운영 랭킹 시스템 전체로 확대하지 않는다.
예제 코드
import heapq
scores = [4, 11, 2, 9, 8, 3]
print(heapq.nlargest(3, scores))실행 결과
[11, 9, 8]정확한 해·근사·휴리스틱을 구분하기
모든 문제에서 큰 입력의 정확한 최적해를 빠르게 구하는 방법을 알고 있는 것은 아니다. 제한된 시간에 좋은 해를 찾는 휴리스틱이나 특정 성능 보장을 가진 근사 알고리즘을 선택할 수 있다. 이때 “대체로 잘 된다”와 “최적해 대비 특정 비율을 보장한다”는 다른 주장이다.
예를 들어 방문할 장소가 많을 때 가까운 곳부터 이동하는 경로는 쉽게 만들 수 있지만 전체 최단 순회가 된다는 보장은 없다. 업무가 요구하는 것은 최적성의 증명인지, 정해진 시간 안의 충분히 좋은 경로인지 먼저 정한다. 목적 함수와 제약이 바뀌면 기존 휴리스틱의 품질도 달라질 수 있다.
무작위 알고리즘은 난수를 사용하는 방식에 따라 실행 시간이나 오류 확률을 분석할 수 있다. 난수를 사용한다는 이유만으로 틀린 답을 내는 것도, 항상 빠른 것도 아니다. 테스트에서는 재현 가능한 시드와 입력을 기록하되 한 시드의 성공을 확률적 보장의 증명으로 취급하지 않는다.
NP-완전 같은 복잡도 분류는 특정 형식의 문제와 환원에 관한 개념이다. “현실의 모든 작은 사례가 풀리지 않는다”거나 “근사해도 구할 수 없다”는 뜻으로 쓰면 안 된다. 입력 제한, 매개변수, 요구 정확도를 바꿔 실용적인 해법을 찾을 수 있는지 검토한다.
테스트: 단순한 정답 구현과 대조하기
빠른 알고리즘의 결과를 작은 입력에서 단순한 기준 구현과 비교하면 경계 오류를 찾는 데 도움이 된다. 아래 검사는 앞의 lower_bound와 merge_sort 정의 뒤에 붙여 실행한다. 길이 0부터 5까지 값 0,1,2로 만들 수 있는 모든 배열을 생성해 정렬 결과를 표준 sorted와 비교한다.
이진 탐색은 정렬된 배열에서 target 이상인 첫 위치를 선형 순회로 찾은 결과와 대조한다. target은 -1부터 3까지 검사하므로 모든 값보다 작은 경우와 큰 경우도 포함된다. 검사 건수는 정렬 364개와 경계 탐색 1820개다. 무작위 몇 개보다 작은 영역을 빠짐없이 확인하는 방식이다.
이 검사는 선택한 작은 영역에 대한 강한 확인이지만 모든 크기의 증명은 아니다. 큰 입력의 재귀 제한과 메모리 사용, 사용자 정의 비교 연산의 특성도 별도 검토해야 한다. 구현의 논리를 설명하는 불변식과 이런 실행 검증을 함께 사용하면 근거가 더 명확해진다.
예제 코드
from itertools import product
sort_checks = search_checks = 0
for length in range(6):
for values in product(range(3), repeat=length):
ordered = sorted(values)
assert merge_sort(values) == ordered
sort_checks += 1
for target in range(-1, 4):
expected = next((i for i, value in enumerate(ordered) if value >= target), len(ordered))
assert lower_bound(ordered, target) == expected
search_checks += 1
print(sort_checks, search_checks)실행 결과
364 1820실험과 벤치마크에서 놓치기 쉬운 비용
실행 시간은 입력 생성, 파일 읽기, 전처리, 본 계산과 결과 출력 중 무엇을 포함했는지에 따라 달라진다. 정렬된 자료를 준비한 뒤 이진 탐색 시간만 재고 정렬까지 포함한 선형 탐색과 비교하면 서로 다른 작업을 비교한 셈이다. 실제 서비스에서 반복 사용되는 비용 구조를 재현해야 한다.
측정에는 작은 입력과 큰 입력, 이미 정렬된 입력, 역순과 중복이 많은 입력처럼 대표적인 분포를 포함한다. 최악의 경우를 보장하는 알고리즘과 평균적으로 좋은 알고리즘을 비교할 때는 사용자에게 중요한 지연의 형태도 고려한다. 평균만 낮아도 일부 요청이 매우 느리면 요구사항을 만족하지 못할 수 있다.
출력을 루프마다 찍으면 계산보다 출력 비용이 측정을 지배할 수 있다. 준비 단계와 측정 단계를 나누고 반복 횟수, 실행 환경과 버전을 기록한다. timeit 같은 도구는 작은 코드 측정에 도움을 주지만 데이터베이스와 네트워크를 포함한 시스템 성능을 자동으로 대표하지는 않는다.
측정 결과가 분석과 다르면 둘 중 하나를 무조건 버리지 않는다. 입력 크기가 아직 작거나, 숨겨진 복사·할당·해시·비교 비용이 있거나, 비용 모델이 실제 병목과 다를 수 있다. 연산 수 분석과 프로파일링을 함께 사용해 차이를 설명한다.
알고리즘을 선택하고 설명하는 순서
먼저 입력과 출력, 실패 조건을 명확히 적는다. 작은 예제를 손으로 풀고 가장 단순한 기준 해법을 만든다. 그다음 입력 크기와 반복 질의, 갱신 비율, 메모리 제한을 보고 병목을 찾는다. 정렬·사전·힙·그래프 모델 같은 이미 알려진 도구로 문제를 바꿀 수 있는지 검토한다.
방법을 바꾸면 정확성이 유지되는 근거를 설명한다. 탐욕 선택을 정당화할 수 있는지, 동적 계획법의 상태가 필요한 정보를 모두 담는지, 그래프의 가중치 조건이 알고리즘의 전제와 맞는지 확인한다. 구현에서는 범위와 빈 입력, 중복과 자료형 경계를 검사한다.
최종 설명은 이름 하나와 복잡도 한 줄로 끝내지 않는다. 전제, 핵심 아이디어, 실제 예제, 결과 해석, 정확성 근거, 시간·공간 비용과 한계를 이어서 제시한다. 다른 방법과의 비교는 “더 좋다”보다 어떤 연산과 입력에서 어떤 비용을 줄이고 무엇을 더 쓰는지로 표현한다.
학습에서는 탐색과 정렬에서 시작해 자료 구조, 그래프, 동적 계획법으로 연결하면 같은 원리가 반복해서 등장하는 것을 볼 수 있다. 실무에서는 검증된 라이브러리를 활용하되 그 계약과 실패 조건을 이해한다. 알고리즘 지식의 목적은 어려운 이름을 많이 아는 것이 아니라 문제의 구조에 맞는 계산과 근거를 선택하는 데 있다.