힙큐

이 문제는 이것이 코딩테스트다 262페이지 문제이다. 최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다. 이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다. 다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다. https://yunzae.tistory.com/94 최단경로(다익스트라,플로이드워셜) 최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립 yunzae.tistory.com 아래는 나의..

https://yunzae.tistory.com/86 힙 정의및장단점 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 yunzae.tistory.com 힙큐는 힙자료구조를 이용한다. 힙 자료구조는 부모 가 자식보다 항상 크다. 하지만 형제노드사이에는 크기순위가 없다. 전체적인 순위를 따지기보다는 최대값, 최솟값이 필요 할 때 힙큐를 자주 쓴다. 파이썬 힙 자료구조 파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다. 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 ..

최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립되어 있다. 예를 들면 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등의 다양한 사례가 존재한다. 상황에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. 대표적으로 사용하는 최단 거리 알고리즘은 3가지인데 다익스트라(데이크스트라), 플로이드 워셜, 벨만 포드 알고리즘 이다. 이중 다익스트라와, 플로이드 워셜은 꼭 알아야 한다. 이 두가지에 대해서 설명을 하고 추후에 벨만 포드 알고리즘에 대해서 포스팅하겠다. 다익스..