성공을 즐기자

다익스트라는 그리디와 DP의 유형으로 분류되는 최단경로 알고리즘이다. DP는 계속해서 그래프를 갱신하기 때문이고 그리디는 그 순간 가장 짧은 정점을 선택하기 때문이다. 음의 가중치가 적용될 수 없어 일상생활 문제에서 잘 사용될 수 있다. 특정한 한 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘이다. 원래는 O(V^2)의 시간복잡도를 가진다. ( 리스트 이용, 돌면서 가장 거리가 짧은 노드를 찾는 경우) 이것은 5,000개 까지는 괜찮지만 개수가 10,000개가 되면 시간초과가 될 가능성이 농후하다. (파이썬은 1초에 2천만 연산이라고 생각하면 됨) 시간초과를 막기 위해서 heap을 이용하면 된다. (방문하지 않은 최단거리의 정점을 찾을 때 이용) 파이썬의 minheap은 heappop을 하면..

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 생각해야하는 것 : heapify를 통해 최소힙으로 만들어 준 후 해야한다. 정답 코드[블로그 참조] : import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) # scoville을 최소 힙화 한다 # 처음 주어질 때는 heap 순서가 아니므로 while scoville[..

heap 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조! MAX heap 과 MIN heap이 있다. MAX heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다. MIN heap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 의미한다. 파이썬에서 heap을 구현하려면 ? heapq 모듈을 import 하면 된다. heapq 모듈은 리스트를 최소 힙처럼 사용할 수 있게 도와준다. import heapq heap = [] heapq.heappush(heap,4) heqpq.heappop(heap) heapify를 이용하면 리스트를 힙으로 만들 수 있다. heapq.heapify(heap) 참고 블로그 : https://www..