4. 다익스트라 알고리즘 파이썬 구현 (우선순위 큐 활용까지 포함) 참고: heapq 라이브러리 활용을 통해 우선순위 큐 사용하기 - 데이터가 리스트 형태일 경우, 0번 인덱스를 우선순위로 인지, 우선순위가 낮은 순서대로 pop 할 수 있음 import heapq queue = [] heapq.heappush(queue, [2, 'A']) heapq.heappush(queue, [5, 'B']) heapq.heappush(queue, [1, 'C']) heapq.heappush(queue, [7, 'D']) print (queue) for index in range(len(queue)): print (heapq.heappop(queue)) 출력 [ [1, ‘C’] , [5, ‘B’], [ 2, ‘A’],..

최단 경로 알고리즘의 이해 1. 최단 경로 문제란? - 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 - 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발 (single-source shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경..

탐욕 알고리즘의 이해 1. 탐욕 알고리즘 이란? - Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 - 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. - 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 coin_list = [1, 100, 50, 500] print (coin_list) coin_list..

너비 우선 탐색 (Breadth-First Search) 1. BFS 와 DFS 란? * 대표적인 그래프 **탐색** 알고리즘 - 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 - 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 - BFS 방식: A - B - C - D - G - H - I - E - F - J - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 - DFS 방식: A - B - D - E - F - C - G - H - I - J - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 ..

너비 우선 탐색 (Breadth-First Search) 1. BFS 와 DFS 란? * 대표적인 그래프 **탐색** 알고리즘 - 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 - 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 - BFS 방식: A - B - C - D - G - H - I - E - F - J - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 - DFS 방식: A - B - D - E - F - C - G - H - I - J - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 ..

그래프 이해 1. 그래프 (Graph) 란? * 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용 예제 집에서 회사로 가는 경로를 그래프로 표현한 예 2. 그래프 (Graph) 관련 용어 - 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함 - 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) - 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) - 참고 용어 - 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선..