🌟 우선순위 큐란?우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐는 2가지로 구분된다.최소 우선순위 큐 : 가장 우선순위가 **낮은** 요소부터 삭제최대 우선순위큐 : 가장 우선순위가 **높은** 요소부터 삭제우선순위 큐 구현 방법배열을 이용한 우선순위 큐연결리스트를 이용한 우선순위 큐힙(heap)을 이용한 우선순위 큐여기에선 힙을 이용한 우선순위 큐를 설명한다.힙을 이용한 우선순위 큐 시간 복잡도는 O(logn)이다. 🌟 힙(heap) 이란?key(부모노드) >= key(자식노드) 또는 key(부모노드) 힙 종류최대 힙 : key(부모노드) >= key(자식노드) 완전 이진트리최소 힙 : key(부모노드) ✔️ Heapqpyt..
🌟 다익스트라 알고리즘이란?하나의 시작 정점에서 다르정점까지의 최단 경로를 계산하는 것이다. 최단 경로 알고리즘이라고도 불린다! ⚒️ Dijkstra의 최단 경로 알고리즘다음과 같은 그림에서 최단경로를 계산하려고 한다. 각 단계에서 S안에 있지 않은 정점 중에서 가장 distance값이 작은 정점을 S에 추가한다.정점 W를 거쳐서 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정해보자! 그러면 정점 v에서 정점 u까지의 거리는 v->w->u (경로2 + 경로3) 거리가 된다.그러나 경로 2는 경로 1보다 항상 길 수 밖에 없다. 현재 distance 값이 가장 작은 정점은 u이기 때문이다. => 거리1 이 알고리즘을 해결하기 위해선 3가지를 고려해야한다. directionvisitedqueued..
🌟 위상정렬이란?어떤 일을 하기 위해 일련의 작업을 차례때로 수행해야 하는 알고리즘이다.즉, B를 하기 위해선 A를 해야하고, C를 하기 위해선 B를 해야하는 상황에서 A-> B-> C 순서로 할 수 있다.예를 들어, 대학교에서 선수 과목을 들어야 해당 과목을 들을 수 있듯이 순서가 정해져 있는 알고리즘이다.N(노드의 개수) = 5, M(간선의 개수) = 5 인 다음과 같은 그래프에서 위상정렬을 수행해보자.이 알고리즘을 해결하기 위해서는 3가지를 고려해야 한다.indegreequeuegraph✔️indegree각 노드에서 진입 차수 개수를 저장 ✔️graph노드의 인접 리스트로 그래프 구현 ✔️queue1. popleft()해서 나온 노드의 영향이 있는 graph으로2. 나온 노드를 indegree-=..
