성덕이의 개발공간

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 전형적인 최단 거리 문제이므로 최단 거리 알고리즘을 이용해 해결한다. N의 크기가 최대 100이므로 플로이드 워셜 알고리즘을 이용해도 효율적으로 해결할 수 있다. 플로이드 워셜 알고리즘을 수행한 뒤에 (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리)를 계산하여 출력한다. 4. 답안 예시 INF = int(1e9) #무한을 의미 #노드, 간선의 개수를 입력받기 n, m = map(int, input().split()) #2차원 리스트(그래프 표현)을 만들고 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in ..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 한 도시에서 다른 도시까지의 최단 거리 문제이다. N과 M의 범위가 충분히 크기 때문에 우선순위 큐를 활용한 다익스트라 알고리즘을 활용 4. 답안 예시 import heapq INF = int(1e9) #무한을 의미 def dijkstra(start): q = [] #시작 노드로 가기 위한 최단 거리는 0으로 설정하여, 큐에 삽입 heapq.heappush(q, (0,start)) distance[start] = 0 while q: #큐가 비어있지 않다면 #가장 최단 거리가 짧은 노드에 대한 정보 꺼내기 dist, now = heapq.heappop(q) #현재 노드가 이미 처리된 적이 있는 노드라면 무시 if distance[now] < dist..

1. 개요 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로디으 워셜(Floyd-Warshall)알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하진 않다. 2차원 테이블에 최단 거리 정보를 저장한다. for문을 3번 사용하므로 많은 노드에서는 비효율 적이다. 다이나믹 프로그래밍 유형에 속한다. 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a - b의 최단 거리보다 a - k - b가 더 짧은지 검사 점화식 2. 동작 과정 살펴보기 [초기 상태] 그래프를 준비하고 최단 거리 테이블을 초기화한다. 행은 출발노드, 열은 도착노드 1번노드에서 2번..

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 표준 라이브러리 형태로 지원 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나 최소 힙(Min Heap), 최대 힙(Max Heap) 존재 Min Heap = 값이 낮은 값부터 추출 Max Heap = 값이 높은 값부터 추출 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용 리스트는 삽입에 굉장히 빠른 시간이 소요되지만 삭제에는 전체 데이터를 돌아야한다. 힙의 이진트리 형태를 이용한다. 사용예제 1. 최소 힙 import heapq #오름차순 힙 정렬(Heap Sort) def heapsort(iterable): h = [] result = [] #모든 원소를 차례대로 힙에 삽입 for value in iterable: hea..

최단 경로 알고리즘이란 가장 짧은 경로를 찾는 알고리즘 1. 한 지점에서 다른 한 지점까지의 최단 경로 2. 한 지점에서 다른 모든 지점까지의 최단 경로 3. 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 1. 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 작용 그리디 알고리즘으로 분류 매 상황에서 가장 비용이 적은 노드를 선택하는 과정을 반복 1.1 다익스트라 최단 경로 알고리즘 출발 노드를 설정 최단 거리 테이블을 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리..