탐욕 알고리즘과 다익스트라 알고리즘

탐욕 알고리즘(Greedy Algorithm)

각 단계에서 가장 최적이라고 생각되는 선택을 하는 알고리즘으로, 전체적으로 최적해를 구하는 것을 목표로 합니다.

 

# 거스름돈 문제
def make_change(amount, coins):
    coins.sort(reverse=True)  # 큰 동전부터 사용
    result = []
    
    for coin in coins:
        count = amount // coin
        if count > 0:
            result.extend([coin] * count)
            amount -= coin * count
    
    return result if amount == 0 else None

# 활동 선택 문제
def activity_selection(activities):
    # 종료 시간을 기준으로 정렬
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    last_end_time = activities[0][1]
    
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end_time:
            selected.append(activities[i])
            last_end_time = activities[i][1]
    
    return selected

# 예제
coins = [500, 100, 50, 10, 5, 1]
amount = 1730
print(f"거스름돈 {amount}원: {make_change(amount, coins)}")

# 활동 선택 예제 (시작시간, 종료시간)
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
selected = activity_selection(activities)
print(f"선택된 활동: {selected}")

 

 

다익스트라 알고리즘(Dijkstra's Algorithm)

가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘

 

import heapq

def dijkstra(graph, start):
    # 최단 거리 테이블 초기화
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # 우선순위 큐 초기화
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        # 이미 처리된 노드라면 스킵
        if current_distance > distances[current_node]:
            continue
        
        # 인접 노드들을 확인
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            # 더 짧은 경로를 발견했다면 업데이트
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# 경로 추적이 가능한 다익스트라
def dijkstra_with_path(graph, start, end):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}
    
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_node == end:
            break
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))
    
    # 경로 재구성
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()
    
    return distances[end], path

# 예제 그래프
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2)],
    'E': [('C', 10), ('D', 2)]
}

distances = dijkstra(graph, 'A')
print(f"A에서 모든 노드까지의 최단 거리: {distances}")

distance, path = dijkstra_with_path(graph, 'A', 'E')
print(f"A에서 E까지의 최단 거리: {distance}, 경로: {path}")