20260604 분기한정과 힙소트 구현

이번 커밋은 알고리즘 스터디의 12주차 과제로, 외판원 문제(Traveling Salesperson Problem)의 변형인 travel2 함수와 힙 정렬 알고리즘인 heapsort 함수를 구현했습니다.

요약

• 주요 변경사항: travel2 함수와 heapsort 함수를 구현했습니다.
• 작업 날짜: 2026년 6월 4일
• 전체 맥락: 알고리즘 스터디의 12주차 과제 제출을 위한 구현입니다.

배경 및 목적

외판원 문제는 최단 경로를 찾는 NP-hard 문제입니다. travel2 함수는 이를 근사적으로 해결하기 위한 분기 한정법(Branch and Bound)을 사용하여 최적의 경로를 찾는 알고리즘입니다. 힙 정렬은 시간 복잡도 O(N log N)을 보장하는 효율적인 정렬 알고리즘입니다. 이 과제는 이 두 알고리즘을 직접 구현하며 이해도를 높이는 것을 목적으로 합니다.

구현 내용

이번 커밋에서는 두 개의 주요 파이썬 파일을 수정했습니다.

변경된 파일 목록

• Week12_problem/6.3.travel2_problem.py
• Week12_problem/7.5.heapsort_problem.py
• python-3.12.7-amd64.exe (이 파일은 실행 파일로, 코드 변경과는 직접적인 관련이 없습니다.)

추가/삭제 라인 수

• 추가 라인: 295
• 삭제 라인: 0

Week12_problem/6.3.travel2_problem.py 상세

이 파일은 분기 한정법을 이용한 외판원 문제 해결 함수 travel2를 구현합니다.

• Node 클래스는 탐색 과정에서 각 노드의 상태(깊이, 경로, 하한값)를 저장합니다.
• pathlength 함수는 주어진 경로의 총 거리를 계산합니다.
• hasOutgoing, hasIncoming 함수는 경로에서 특정 노드가 이미 사용되었는지 확인합니다.
• boundof 함수는 현재 노드의 하한값(현재까지의 경로 거리 + 앞으로 방문할 노드들의 최소 연결 거리)을 계산합니다.
• travel2 함수는 우선순위 큐를 사용하여 하한값이 가장 낮은 노드부터 탐색을 확장하며 최적의 경로를 찾습니다.
• 테스트 함수 test_travel2를 통해 다양한 입력에 대한 함수 동작을 검증합니다.

# Node 클래스 정의 (일부)
class Node:
    def __init__(self, level, path):
        self.level = level
        self.path = path[:]
        self.bound = 0

# travel2 함수 (일부)
def travel2(n, W):
    global INF
    heap = []  # 우선순위 큐
    
    v = Node(0, [1])
    v.bound = boundof(v, n, W)
    minlength = INF
    opttour = []
    
    counter = 0
    heappush(heap, (v.bound, counter, v))
    counter += 1
    
    while len(heap) != 0:
        v = heappop(heap)[2]

        if v.bound < minlength:
            u_level = v.level + 1
            for i in range(2, n + 1):
                if i in v.path:
                    continue
                u = Node(u_level, v.path + [i])
                u.bound = boundof(u, n, W)

                if u.level == n - 1:
                    tour_len = pathlength(u.path, W) + W[u.path[-1]][1]
                    if tour_len < minlength:
                        minlength = tour_len
                        opttour = u.path[:] + [1]
                else:
                    if u.bound < minlength:
                        heappush(heap, (u.bound, counter, u))
                        counter += 1
    
    return minlength, opttour

Week12_problem/7.5.heapsort_problem.py 상세

이 파일은 힙 정렬 알고리즘 heapsort를 구현합니다.

• Heap 클래스는 힙의 배열(S)과 현재 힙 크기(heapsize)를 관리합니다.
• siftdown 함수는 힙의 특정 노드부터 힙 성질을 유지하도록 조정합니다.
• root 함수는 힙의 최댓값(루트)을 제거하고 힙을 재구성합니다.
• removekeys 함수는 힙에서 모든 요소를 순차적으로 제거하여 정렬된 배열을 만듭니다.
• makeheap 함수는 주어진 배열을 최대 힙으로 변환합니다.
• heapsort 함수는 makeheap과 removekeys를 호출하여 전체 힙 정렬을 수행합니다.
• 테스트 함수 test_heapsort를 통해 정렬 결과를 검증합니다.

# Heap 클래스 및 관련 함수 (일부)
class Heap:
    def __init__(self, n, S):
        self.S = S[:]
        self.heapsize = n

def siftdown(H, i):
    parent = i
    siftkey = H.S[parent]
    while True:
        left = 2 * parent + 1
        if left >= H.heapsize:
            break
        right = left + 1
        if right < H.heapsize and H.S[left] < H.S[right]:
            largerchild = right
        else:
            largerchild = left
        if siftkey < H.S[largerchild]:
            H.S[parent] = H.S[largerchild]
            parent = largerchild
        else:
            break
    H.S[parent] = siftkey

def heapsort(n, H, S):
    makeheap(n, H)
    removekeys(n, H, S)

기술적 의사결정

이 커밋에서는 특별한 기술적 의사결정 사항이 없으며, 수업자료의 구현을 따랐습니다.

배운 점 및 개선점

• 배운 점:
  • 분기 한정법의 기본 원리와 우선순위 큐를 활용한 탐색 전략을 이해했습니다.
  • 힙 정렬의 두 단계(힙 구성, 힙에서 제거)와 각 단계에서의 배열 조작 방식을 익혔습니다.
  • 재귀적 또는 반복적 방식으로 알고리즘을 구현하는 방법을 연습했습니다.
• 개선점:
  • travel2 함수의 boundof 함수 로직이 복잡하여 이해하는 데 시간이 걸렸습니다. 좀 더 간결한 표현이나 주석이 추가되면 좋을 것 같습니다.
  • 힙 정렬에서 siftdown 함수의 인덱스 계산(2 * parent + 1, left + 1)을 정확히 이해하는 것이 중요했습니다.
• 다음 단계 계획:
  • 구현한 travel2 함수의 성능을 다양한 크기의 입력으로 측정하고 분석합니다.
  • 힙 정렬의 다른 구현 방식(예: 최소 힙을 이용한 내림차순 정렬)을 탐색합니다.

참고 자료

• CSE304 2026-1 Algorithms 수업 자료 (이론 및 의사코드)