🦕 공룡이 되자!

힙 라이브러리 사용 # 최소 힙 import heapq # 오름차순 힙 정렬(Heap Sort) def heapsort(iterable): h=[] result=[] # 모든 원소를 차례대로 힘에 삽입 for value in iterable: heapq.heappush(h, value) # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i in range(len(h)): result.append(heapq.heappop(h)) return result result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) print(result) 실행결과 >>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # 최대 힙 import heapq # 내림차순 힙 정렬(Hea..

다익스트라 알고리즘 특정 노드에서 다른 노드까지의 최단 경로 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류(DP로도 분류가 되기도 함) 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 전체적인 흐름 출발 노드 설정 출발 노드를 기준으로 각 노드의 최소 비용 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 위 과정 3~4를 반복 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음 처리 과정에서 더 짧은 경로를 찾으면 ‘이제..