기록

팩토리얼, 지수시간에 비해 빠르지만 입력 크기가 커질수록 처리 시간이 급격히 증가하는 알고리즘 범주에 속한다.

이 복잡도는 이중 반복문이 포함된 구조에서 자주 나타나며, 작은 입력에선 문제없지만, 큰 입력에서는 비효율적인 성능을 보인다.

대표적으로 정렬 알고리즘 중 버블 정렬, 삽입 정렬, 선택 정렬이 이에 해당하며, 브루트포스 방식의 문제 해결에서도 볼 수 있다.

버블 정렬

오름차순 기준

배열의 인접한 두 원소를 검사하고 정렬한다.

길이가 n인 배열이 있다.

전체 루프 i는 첫 번째부터 마지막 요소 앞 n-1까지 진행한다.

내부 루프 j는 인접한 두 요소를 비교하고 더 큰 수인 경우 교환을 진행하여 n - 1 - i까지 진행한다.

루프마다 가장 큰 요소가 순서대로 끝에 배치된다.

def bubble_sort(arr):
    n = len(arr)

    # 총 n-1회 반복
    for i in range(n - 1):
        # 정렬된 요소를 제외한 범위에서 반복
        for j in range(n - 1 - i):
            # 인접한 요소 비교 후 순서가 잘못되면 교환
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

data = [5, 2, 4, 3, 1]
print("정렬 전:", data)
bubble_sort(data)
print("정렬 후:", data)

"""
정렬 전: [5, 2, 4, 3, 1]
정렬 후: [1, 2, 3, 4, 5]
"""

모든 요소를 반복적으로 비교 및 교환한다. 어떤 경우든 i 반복은 무조건 n-1번을 수행하게 되며 이미 정렬된 배열인 경우에도 불필요한 반복이 진행되게 된다. 이러한 점을 개선해 스왑 발생 여부를 확인하여 정렬이 된 상태인 경우 조기 종료를 시킬 수 있다.

def bubble_sort_optimized(arr):
    n = len(arr)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # 스왑이 한 번도 없으면 이미 정렬된 상태
        if not swapped:
            break

data = [1, 2, 3, 4, 5]
print("정렬 전:", data)
bubble_sort(data)
print("정렬 후:", data)

최악이나 평균의 경우에는 모든 요소를 끝까지 비교하고 교환해야 하므로 시간 복잡도는 O(n^2)이다. 그러나 이미 정렬된 배열인 최선의 경우에는 비교만 수행되고 스왑이 한 번도 발생하지 않기 때문에 조기에 종료되어, 최적화된 구현에서는 O(n)의 시간 복잡도를 가질 수 있다.

선택정렬

매 반복마다 가장 작은 값을 찾아 맨 앞과 교환하는 방식이다. 정렬된 부분과 미정렬 부분을 구분하고, 매 단계마다 최솟값을 선택한다. 교환 횟수는 최대 n-1회이지만 비교는 항상 일정하게 많이 발생하기 때문에 최선/최악 구분 없이 O(n^2)이다.

비교 방식이 데이터 정렬 여부와 무관하다.

def selection_sort(arr):
    """
    선택 정렬 함수
    현재 위치 이후의 요소 중 최솟값을 찾아 현재 위치와 교환
    """
    n = len(arr)

    for i in range(n - 1):
        min_index = i  # 현재 위치를 최솟값 인덱스로 가정

        # i 이후 요소들 중에서 최솟값 인덱스 탐색
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # 현재 위치와 최솟값 위치를 교환
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

data = [5, 2, 4, 3, 1]
print("정렬 전:", data)
selection_sort(data)
print("정렬 후:", data)

"""
정렬 전: [5, 2, 4, 3, 1]
정렬 후: [1, 2, 3, 4, 5]
"""

구조가 단순하고, 교환 횟수가 적기 때문에 메모리 이동 비용이 큰 환경에 적합하지만 비교 횟수가 많고 입력이 정렬되어 있어도 시간 복잡도가 항상 O(n^2)인 단점이 있어 대규모 데이터에는 부적합하다.

삽입 정렬

삽입 정렬은 배열의 두 번째 요소부터 시작하여, 현재 요소를 그 앞에 있는 요소들과 비교하면서 적절한 위치를 찾아 삽입하는 방식이다. 비교 과정에서는, 앞의 요소가 현재 요소보다 크면 한 칸씩 뒤로 이동시키고, 더 작은 값을 만나거나 배열의 처음까지 도달하면 그 자리에 현재 요소를 삽입한다. 이 과정을 반복하며 배열의 왼쪽 부분부터 정렬된 상태가 된다.

def insertion_sort(arr):
    """
    삽입 정렬 함수
    배열의 각 요소를 순차적으로 '정렬된 부분'에 삽입하여 정렬하는 알고리즘.
    """
    n = len(arr)
    
    # 두 번째 요소부터 시작: 첫 번째 요소는 이미 '정렬된 부분'으로 가정
    for i in range(1, n):
        key = arr[i]        # 현재 정렬할 값
        j = i - 1           # key 앞의 마지막 인덱스

        # key가 정렬된 부분의 값보다 작으면, 한 칸씩 오른쪽으로 이동시켜 자리 비움
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # 최종적으로 key를 알맞은 위치에 배치
        arr[j + 1] = key

data = [5, 2, 4, 3, 1]
print("정렬 전:", data)
insertion_sort(data)
print("정렬 후:", data)

"""
정렬 전: [5, 2, 4, 3, 1]
정렬 후: [1, 2, 3, 4, 5]
"""

정렬된 배열일 경우 비교만 하고 이동이 거의 없어 O(n)에 가까운 성능을 보인다.

구현이 간단하며, 안정 정렬이기 때문에 동일한 값을 가진 요소들의 상대적 순서가 유지된다. 추가적인 배열 없이 입력 배열 내부에서만 정렬 수행을 하기 때문에 메모리에 효율적이지만 전체가 정렬되지 않은 경우 비교, 이동이 많아져 시간 복잡도는 O(n^2)가 된다.

O(2^n) - 지수 시간

O(n!) 시간 복잡도처럼, 지수 시간 복잡도 또한 입력 크기가 조금만 커져도 실행 시간이 급격히 증가하는 대표적인 비효율적인 복잡도이다. 특히, 모든 가능한 경우의 수를 탐색해야 하는 문제에서 자주 나타난다.

부분 집합 생성

집합 [1, 2, 3]이 있을 때, 모든 부분 집합의 개수는 2^3 = 8개이다.

def subsets(arr):
    if not arr:
        return [[]]

    first = arr[0]
    rest_subsets = subsets(arr[1:])

    # 기존 부분집합들 + first를 포함한 새로운 부분집합들
    return rest_subsets + [[first] + subset for subset in rest_subsets]

print(subsets([1,2,3]))

"""
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
"""

1. 재귀를 사용해서 주어진 리스트의 모든 가능한 부분 집합을 생성한다.

재귀 호출의 종료 조건은 입력 리스트가 비어있어 더 이상 처리할 요소가 없으면 빈 리스트를 반환하여 공집합이 모든 집합의 부분집합이 되는 규칙을 반영한다.

2. 현재 리스트에서 첫 번째 요소를 분리하고, 나머지 요소를 처리하는 하위 문제로 분할한다.

첫 번째 요소를 제외한 나머지 리스트의 모든 부분집합을 재귀적으로 구한다.

3. 재귀적으로 얻은 나머지 요소들의 부분집합을 기반으로 최종 부분집합들을 조합한다.

first를 포함하지 않는 부분집합과 포함하는 부분집합 두 그룹을 반환한다.

subsets([1, 2, 3])

├── first = 1

├── rest_subsets = subsets([2, 3])

│          ├── first = 2

│          ├── rest_subsets = subsets([3])

│           │       ├── first = 3

│           │       ├── rest_subsets = subsets([]) → [[]]

│           │       └── return [[], [3]]

│           └── return [[], [3], [2], [2, 3]]

└── return [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

- n개 원소의 부분집합 개수 2^n개

- 각 원소마다 포함 또는 비포함 2가지 선택

- 재귀 호출 2^n번 발생

부분집합을 구하는 방식은 비트마스킹을 사용하여 재귀 없이 반복문과 비트 연산으로 더 효율적으로 생성할 수 있다.

def subsets_bitmask(arr):
    n = len(arr)
    result = []
    
    for i in range(2**n):  # 0부터 2^n-1까지
        subset = []
        for j in range(n):
            if i & (1 << j):  # j번째 비트가 1이면
                subset.append(arr[j])
        result.append(subset)
    
    return result
# 시간복잡도: O(2^n * n) — 모든 부분집합을 순회하며 최대 n개의 요소를 확인
print(subsets_bitmask([1, 2, 3]))

"""
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
"""

피보나치수열(비효율적 재귀)

 피보나치수열은 첫째 및 둘째 항은 1로 고정되고 그 뒤의 모든 항은 바로 앞 두 항의 합으로 이루어진 수열이다.

입력을 받아서 해당 순서에 들어오는 수를 출력하는 코드를 만들어 본다.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# 호출 예시
print(fibonacci(5)) 

"""
5
"""

시간 복잡도는 O(2^n)이며 재귀호출로 인한 중복 호출이 많이 발생하게 된다.

n = 5일 때, 

finbonacci(3) : 2번

finbonacci(2) : 3번

finbonacci(1) : 5번

finbonacci(0) : 3번

이러한 중복을 대처하기 위해 효율적인 대안으로 동적 계획법이나 메모이제이션으로 O(n)으로 개선이 가능하다.

조합 탐색 (DFS/백트래킹 기반)

n개의 원소 중에서 순서에 상관없이 R개를 뽑는 모든 조합을 탐색한다.

- DFS : 깊이 우선 탐색

- 백트래킹 : 모든 경우의 수를 탐색하면서 가능성이 없는 분기는 중단하고 되돌아가는 기법

def dfs(arr, path, start, r):
    if len(path) == r:
        print(path)
        return
    for i in range(start, len(arr)):
        dfs(arr, path + [arr[i]], i + 1, r)

dfs([1, 2, 3, 4], [], 0, 2)

"""
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
"""

주어진 배열(arr)에서 r개의 원소를 선택하는 모든 조합을 찾는다.

선택한 원소보다 뒤에 있는 원소들만 탐색하여 중복 선택을 방지하고 순서를 고려하지 않는 조합의 특성을 구한다.

조합의 수는 C(n, r)로 최대 O(2^n)이 된다. 백트래킹의 경우 조건에 따라 일부 경로는 생략 가능해서 효율은 개선되지만 최악의 경우는 여전히 O(2^n)이다.

동적 계획법

Top-Down

큰 문제를 작은 하위 문제로 쪼개면서 재귀적으로 호출한다.

이미 계산한 하위 문제의 결과는 메모이제이션을 통해 저장하여 중복 호출을 방지한다.

재귀 호출 중에 처음 계산되는 하위 문제만 실제 계산되고, 이후에는 저장된 값을 재사용한다.

def fibonacci_memo_top_down(n, memo=None):
    # memo는 계산된 값을 저장하기 위한 딕셔너리 (기본값은 None으로 시작)
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]  # 이미 계산된 값이 있으면 바로 반환 (중복 계산 방지)

    if n <= 1:
        return n  # 기저 사례: 피보나치(0) = 0, 피보나치(1) = 1

    # 아직 계산되지 않은 경우 재귀적으로 계산
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]  # 계산된 값을 반환
    
print(fibonacci_memo_top_down(10))
# 55

시간 복잡도 O(n), 코드가 간결하지만 메모리 사용량이 많을 수 있으며 재귀 한도가 있어 너무 큰 입력에는 스택 오버플로우 위험이 있다.

Bottom-Up

가장 작은 하위 문제부터 차례대로 해결하면서 결과를 쌓아 올린다.

반복문을 이용해 누적적으로 해결하여 스택 사용 없이 처리한다.

def fibonacci_dp_bottom_up(n):
    # 피보나치 수열의 n번째 수를 구하기 위한 동적 계획법 (Bottom-Up 방식) 구현

    if n <= 1:
        return n  # n이 0 또는 1일 경우, 그대로 반환 (기저 사례)

    dp = [0] * (n + 1)  # 0부터 n까지의 값을 저장할 DP 테이블 생성 (n+1 크기)
    dp[1] = 1  # 초기 조건 설정: 피보나치(0) = 0, 피보나치(1) = 1

    # 점화식에 따라 2부터 n까지 순차적으로 계산
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 이전 두 항을 더한 값을 현재 위치에 저장

    return dp[n]  # 최종적으로 n번째 피보나치 수를 반환
    
 print(fibonacci_dp_bottom_up(10))

테이블을 통해 모든 값을 저장한다. 시간 복잡도 O(n)을 가지며 재귀 호출이 없어 스택 오버플로우 걱정이 없으며 공간복잡도를 O(n)에서 O(1)로 개선 가능하여 메모리 최적화가 가능하다. 하지만 DP 테이블을 모두 만들어야 하기 때문에 필요 없는 값도 계산하게 되기도 한다.

공간 복잡도 개선

def fibonacci_optimized(n):
    # 피보나치(0) = 0, 피보나치(1) = 1 처리
    if n <= 1:
        return n

    # 이전 두 항만 저장 (dp 테이블 전체 필요 없음)
    prev2 = 0  # 피보나치(n-2)
    prev1 = 1  # 피보나치(n-1)

    for i in range(2, n + 1):
        curr = prev1 + prev2  # 현재 피보나치 수
        prev2 = prev1         # 피보나치(n-2) ← 피보나치(n-1)
        prev1 = curr          # 피보나치(n-1) ← 현재 피보나치 수

    return prev1  # n번째 피보나치 수

일반적인 bottom-up 방식은 dp = [0] * (n+1)로 전체 수열을 저장하므로 공간복잡도는 O(n)이다. 하지만 피보나치수열의 다른 특징은 항을 계산할 때 오직 이전 두 항만 사용하기 때문에 dp 배열 없이 prev1, prev2 두 변수만 사용해도 충분하다. 불필요한 dp 배열을 제거하게 되면 공간 복잡도는 O(1)로 줄어들게 된다.

외판원 문제(TSP)

NP는 정답을 빠르게 검증할 수 있는 문제 집합이다. 즉, 어떤 해답이 주어졌을 때, 그것이 맞는지 다항 시간 내에 확인 가능한 문제들을 말한다. 

NP-complete는 NP 문제 중 가장 어려운 문제들로, NP에 속하면서 모든 NP 문제로부터 다항 시간 내에 환원이 가능한 문제이다. 

NP-hard는 모든 NP-complete 이상의 난이도를 포함하는 상위 개념이다. 이 집합은 NP를 포함하지 않을 수도 있으며, 검증조차 다항 시간 내에 불가능할 수 있는 문제까지 포함한다.

P ⊆ NP  
NP-complete ⊆ NP  
NP-complete ⊆ NP-hard  

TSP는 하나의 경로가 주어졌을 때, 그 경로가 총얼마의 비용을 갖는지 계산하는 데는 O(n)으로 정답을 빠르게 검증하는 게 가능하기 때문에 NP 문제에 속한다.

최적 경로를 찾기 위한 모든 경우를 탐색하면 (n-1)!개의 경로가 생기고, 이는 O(n!) 시간 복잡도로, 도시 수가 조금만 늘어나도 계산이 불가능한 수준으로 커지게 된다. 현재까지는 다항 시간 내에 최적해를 찾는 알고리즘은 발견되지 않았기 때문에 TSP의 최적화 문제(정답을 찾는 문제)는 NP-hard이다.

TSP의 최단 경로를 묻는 최적화가 문제가 아닌 "총 경로 비용이 K 이하인 경로가 존재하는가?"처럼 결정 문제로 형태를 바꾸면 예/아니오로 답할 수 있고, 다항 시간 검증/환원이 가능한 NP-complete 문제가 된다.

즉, 본질적으로는 NP-hard 한 최적화 문제지만, 이를 결정 문제로 변환하면 NP-complete 문제로 볼 수 있다. 실제 적용에서는 정확한 해 대신, 근사 알고리즘이나 동적 계획법을 활용해 현실적인 해를 구하는 방향으로 발전하였다.

Held-Karp 알고리즘

작은 규모의 문제에 대해 최적해를 찾는 효율적인 방법을 제공하는 TSP를 해결하기 위한 동적 계획법 기반의 알고리즘이다. 알고리즘의 핵심은 문제를 더 작은 하위 문제로 분할하고, 이 하위 문제들의 해를 저장하여 중복 계산을 피하는 것으로 이때 비트 마스킹을 사용하여 효율적으로 표현한다.

문제 풀이의 구조

하위 문제 정의

C(S, j) : 시작 도시(0)에서 출발해 집합 S(0 포함, j 포함)에 속한 도시를 한 번씩 방문, 마지막 도시가 j일 때의 최소 비용 

- S: 방문한 도시 집합 (도시 0은 항상 포함)

- j ∈ S, j ≠ 0

비트마스킹으로 상태 표현

방문한 도시의 집합 S를 정수로 표현한다

예) s =  0b1011 (0, 1, 3번 도시를 방문한 상태)

알고리즘 구성

기저 사례 (Base Case)

더 이상 쪼갤 수 없는 최소 단위 하위 문제이다.

두 도시만 방문한 경우(0에서 j로 바로 가는 비용) : C({0, j}, j) = cost(0, j) 

점화식 (Recurrence)

작은 하위 문제를 통해 큰 문제를 푸는 공식이다.

C(S, j) = min { C(S - {j}, i) + cost(i, j) } (단, i ∈ S - {j})

도시 j에 도착하기 직전 도시 i를 고려해, i까지 최소 비용 + i -> j 비용을 더한 값을 구한다.

계산 순서

S의 크기를 2 → n까지 증가시키며 모든 C(S, j) 계산한다.

각 상태는 비트마스킹으로 구현한다.

최종 결과

모든 도시(V) 방문 후 0으로 돌아오는 최소 경로를 구한다.

min { C(V, j) + cost(j, 0) } (단, j ≠ 0)

def tsp_dp(dist):
    n = len(dist)
    
    # dp[visited][curr]:
    # 시작 도시 0에서 출발, visited(비트마스킹) 상태의 도시 방문 && 현재 위치 curr일 때 최소 비용
    # 2^n * n -> O(n * 2^n)
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0 # Base Case : 시작 도시(0) 방문 상태

    for visited in range(1 << n): # 총 2^n개의 visited 상태
        for curr in range(n):     # 현재 위치한 도시 (j)
            if not (visited & (1 << curr)):
                continue
            for next in range(n):
                if visited & (1 << next):
                    continue
                next_visited = visited | (1 << next)
                
               	# C(S ∪ {next}, next) = min(C(S, curr) + cost(curr, next))
                dp[next_visited][next] = min(
                    dp[next_visited][next],
                    dp[visited][curr] + dist[curr][next]
                ) # O(n^2 * 2^n)
    
    # 모든 도시 방문 후, 다시 0으로 돌아오는 비용 중 최솟값
    # min(C(V, j) + cost(j, 0))  (j != 0)
    return min(dp[(1 << n) - 1][i] + dist[i][0] for i in range(1, n))

dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

result = tsp_dp(dist)
print(f"최소 이동 비용: {result}")

"""
최소 이동 비용: 80
"""

시간 복잡도는 개선되어 O(m^2 * 2^n)이 되지만 여전히 도시 수가 증가했을 때 지수적으로 증가하므로 큰 입력엔 부적합하다.

근사 알고리즘

도시 수가 증가하면 계산량이 급격히 증가하는 문제를 해결하기 위한 방법으로, 정확한 최적해는 아니지만 계산 가능한 시간 내에 효율적인 경로를 찾는 방법이다.

최소 신장 트리 (Minimum Spanning Tree, MST) 알고리즘

MST는 가중치가 있는 무방향 그래프에서 모든 정점을 연결하면서, 간선 가중치의 총합이 최소가 되는 트리를 말한다.

TSP는 출발점에서 모든 정점을 한 번씩 방문하고, 다시 출발점으로 돌아오는 사이클(순환 경로)을 찾는 문제이지만, MST는 사이클이 없는 트리이다. 하지만 이 MST를 활용하여 다음과 같은 방식으로 TSP 근사 경로를 만들 수 있다.

1. 완전 그래프 구성

풀고자 하는 TSP 문제의 원래 그래프가 주어지면, 모든 도시 간의 최단 거리를 간선 가중치로 하는 완전 그래프를 구성한다.

이는 특히 삼각 부등식을 만족하는 Metric TSP에서 유용하다.

*  Metric TSP?

- 모든 정점 쌍이 연결되어 있으며, 거리 함수가 삼각 부등식을 만족하는 TSP를 의미한다.

- distance(A, C) ≤ distance(A, B) + distance(B, C)

- 이러한 조건을 만족할 경우, 근사 알고리즘의 성능 보장이 가능하다.

2. MST 구성

완전 그래프에 대해 MST를 구성한다. 보통 프림(Prim) 알고리즘이 사용되며, 전체 간선 가중치의 합이 최소가 되도록 트리를 구성한다.

3. MST 전위 순회 (Preorder Traversal)

MST를 DFS 방식으로 전위 순회하여 방문 순서를 얻는다. 이 순서는 중복 방문이 가능하며, 이후 중복된 정점을 생략하고 한 번씩만 방문하는 경로로 정제한다. 이를 통해 해밀턴 순환 경로에 근사한 경로를 얻는다.

* 해밀턴 순환 경로

- 해밀턴 경로 : 그래프 내의 모든 정점을 정확히 한 번씩만 방문하는 경로, 시작점과 도착점이 다를 수 있다.(비순환)

- 해밀턴 순환 경로는 해밀턴 경로의 조건에서 시작점으로 다시 돌아오는 순환 경로를 추가한다.

4. 쇼트컷 적용 및 최종 경로 구성

방문 순서 중 이미 방문한 정점은 건너뛰고 다음 미방문 정점으로 이동하는 쇼트컷(shortcut)을 적용한다. 이를 통해 중복 없이 정점을 한 번씩만 방문하는 해밀턴 순환 경로가 완성되며, 마지막에 시작 도시로 돌아와 TSP의 근사해를 얻는다.

프림 (Prim) 알고리즘

최소 신장 트리를 찾을 때는 대표적으로 프림 알고리즘을 사용한다. 이 알고리즘은 그래프의 한 정점에서 시작해서, MST 바깥에 있는 정점 중 현재 MST에 있는 정점과 가장 가중치가 낮은 간선으로 연결된 정점을 하나씩 추가하면서 MST를 만들어 나가는 방식이다. 모든 정점을 연결하는 트리를 사이클 없이 만들고, 총 간선 가중치의 합이 최소가 되도록 구성한다.

1. 정점 중 하나를 시작 정점으로 선택하고 MST에 포함시킨다.

2. 현재 MST에 포함된 정점들과 연결된 간선들 중에서, MST 바깥에 있는 정점으로 연결되며 가중치가 가장 낮은 간선을 선택한다.

3. 선택한 간선의 반대쪽 정점을 MST에 새롭게 추가하고, 해당 간선도 MST에 포함시킨다.

4. 모든 정점이 MST에 포함될 때까지 반복한다.

import heapq

# 1. Prim 알고리즘으로 MST 구성
def prim_mst(graph):
    n = len(graph)
    visited = [False] * n
    mst = [[] for _ in range(n)]  # MST를 인접 리스트로 표현
    min_heap = [(0, 0)]  # (가중치, 정점)
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        for v in range(n):
            if not visited[v] and u != v:
                heapq.heappush(min_heap, (graph[u][v], v))
                mst[u].append(v)
                mst[v].append(u)  # 무방향 MST
    return mst

# 2. DFS로 MST 순회하여 TSP 경로 획득
def dfs_path(tree, node, visited, path):
    visited[node] = True
    path.append(node)
    for neighbor in tree[node]:
        if not visited[neighbor]:
            dfs_path(tree, neighbor, visited, path)

# 3. 근사 TSP 실행
def tsp_mst_approx(graph):
    mst = prim_mst(graph)  # MST 생성
    path = []
    visited = [False] * len(graph)
    dfs_path(mst, 0, visited, path)  # DFS로 순회 경로 생성
    path.append(0)  # 출발 도시로 복귀
    total_cost = sum(graph[path[i]][path[i+1]] for i in range(len(path)-1))
    return total_cost, path

# 테스트용 그래프 (대칭 행렬, 삼각 부등식 만족)
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

cost, path = tsp_mst_approx(graph)
print(f"근사 비용: {cost}")
print(f"근사 경로: {path}")

"""
근사 비용: 95
근사 경로: [0, 1, 2, 3, 0]
"""

이 알고리즘은 Metric TSP (삼각 부등식 만족) 조건에서만 유효하며, 항상 최적해의 2배 이내의 근사 결과를 보장하는 2-근사 알고리즘(2-approximation)이다.

최근접 이웃 (Nearest Neighbor) 알고리즘

출발점에서 시작해서 가장 가까운 도시부터 방문해 나가는 방식이다. 정점을 한 번씩만 방문하고, 모든 도시를 돌고 나면 다시 출발점으로 돌아간다. 

1. 시작 정점을 임의로 선택

2. 현재 정점에서 가장 가까운 미방문 정점으로 이동

3. 모든 정점을 한 번씩 방문할 때까지 반복

4. 마지막 정점에서 시작 정점으로 돌아와 순환 경로 완성

def tsp_nearest_neighbor(graph, start=0):
    n = len(graph)
    visited = [False] * n
    path = [start]
    total_cost = 0
    current = start
    visited[current] = True

    for _ in range(n - 1):
        nearest = None
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and graph[current][i] < min_dist:
                nearest = i
                min_dist = graph[current][i]
        visited[nearest] = True
        path.append(nearest)
        total_cost += min_dist
        current = nearest

    # 돌아오는 거리 추가
    total_cost += graph[current][start]
    path.append(start)
    return total_cost, path

# 테스트용 대칭 거리 행렬
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

cost, path = tsp_nearest_neighbor(graph)
print(f"근사 비용: {cost}")
print(f"근사 경로: {path}")

"""
근사 비용: 80
근사 경로: [0, 1, 3, 2, 0]
"""

(한 번의 탐색마다 O(n) 거리 계산) * (n개 도시) = O(n^2)의 시간복잡도를 가진다.

구현이 간단하고 빠르고 직관적이지만, 초기 시작점에 따라 결과가 달라지며 지역 최적 해에 빠지기 쉽다. 최악의 경우 낮은 수준의 근사율을 가질 수 있어 최적해보다 빠른 근사해가 필요한 시스템에 활용되거나 대규모 TSP문제 등에 활용하거나 최적해를 개선하기 위한 방식들로 개선한다.

1. Multi-Start Nearest Neighbor

- n개의 정점을 모두 출발점으로 시도, 최적 경로 선택

- 시간복잡도 O(n^3)까지 증가하지만 품질이 향상된다.

2. 2-opt / 3-opt 알고리즘

- 최근접 이웃으로 얻은 경로에서 두 정점 간 경로를 교환하여 더 짧은 경로 탐색

- 지역 최적해 탈출 가능

3. 다른 휴리스틱과 결합

- MST 기반 알고리즘, Christofiedes 알고리즘 등과 비교 및 결합 가능