Baekjoon

·Algorithms
🌟 다익스트라 알고리즘이란?하나의 시작 정점에서 다르정점까지의 최단 경로를 계산하는 것이다. 최단 경로 알고리즘이라고도 불린다!  ⚒️ Dijkstra의 최단 경로 알고리즘다음과 같은 그림에서 최단경로를 계산하려고 한다. 각 단계에서 S안에 있지 않은 정점 중에서 가장 distance값이 작은 정점을 S에 추가한다.정점 W를 거쳐서 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정해보자! 그러면 정점 v에서 정점 u까지의 거리는 v->w->u (경로2 + 경로3) 거리가 된다.그러나 경로 2는 경로 1보다 항상 길 수 밖에 없다. 현재 distance 값이 가장 작은 정점은 u이기 때문이다. => 거리1  이 알고리즘을 해결하기 위해선 3가지를 고려해야한다. directionvisitedqueued..
·Algorithms
🌟 위상정렬이란?어떤 일을 하기 위해 일련의 작업을 차례때로 수행해야 하는 알고리즘이다.즉, B를 하기 위해선 A를 해야하고, C를 하기 위해선 B를 해야하는 상황에서 A-> B-> C 순서로 할 수 있다.예를 들어, 대학교에서 선수 과목을 들어야 해당 과목을 들을 수 있듯이 순서가 정해져 있는 알고리즘이다.N(노드의 개수) = 5, M(간선의 개수) = 5 인 다음과 같은 그래프에서 위상정렬을 수행해보자.이 알고리즘을 해결하기 위해서는 3가지를 고려해야 한다.indegreequeuegraph✔️indegree각 노드에서 진입 차수 개수를 저장 ✔️graph노드의 인접 리스트로 그래프 구현 ✔️queue1. popleft()해서 나온 노드의 영향이 있는 graph으로2. 나온 노드를 indegree-=..
galong
'Baekjoon' 태그의 글 목록