재호의 공부방

설계 1. 배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 2. 배낭문제는 짐을 쪼갤 수 있는 경우의 분할가능 배낭문제(Fractional Knapsack Problem)와 짐을 쪼갤 수 없는 경우의0-1 배낭문제(0-1 Knapsack Problem) 두 가지로 나눌 수 있는데, 이번 게시글은 0-1 배낭문제(0-1 Knapsack Problem)을 다뤄보았다. 코드 def knapsack(values, weights, capacity): n = len(v..

다익스트라(Dijkstra) 알고리즘 1. 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 2. 각 꼭짓점을 최대 한 번씩만 방문가능하며 방문하지 않은 점 중 최단거리인 점을 찾아 방문하여 최단 거리를 정하고 이를 반복한다. 코드 import heapq def dijkstra(graph, start): # 그래프에서 모든 노드까지의 최단거리를 저장할 딕셔너리 초기화 distance = {node: float('inf') for node in graph} distance[start] = 0 # 시작 노드부터의 최단거리를 저장할 우선순위 큐 초기화 priority_queue = [(0, start)] while priority_queue:..