알고리즘_PS/Algorithm

[Algo] 다익스트라 (dijkstra) 알고리즘

1. 서론 다익스트라 알고리즘이란, 그래프 상에서 한 정점에서 다른 (모든) 정점으로의 최단경로를 구하기 위해 사용되는 알고리즘이다. 인접 리스트와 우선순위 큐를 이용해 손쉽게 구현할 수 있다는 장점이 있어 많은 사람들이 사용한다. 2. 설명 먼저, 다음과 같은 그래프가 있다고 가정하자. 다익스트라 알고리즘은 먼저 시작점 자신의 거리를 0으로 두고 다른 갈 수 있는 모든 점들의 최단거리값 (dist[])를 업데이트한다. 업데이트시 만약 [현재 노드의 cost + 현재 가리키는 노드로 가는 edge의 cost] 값이 가리키는 노드의 dist값보다 작다면, dist를 업데이트한다. 그 다음, 방문하지 않은 다른 모든 점들중 가장 dist값이 작은 노드를 시작점으로 잡고, 다시 dist를 업데이트한다. 이를 ..

[Algo] Insertion Sort - 삽입 정렬

참고한 블로그 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html [알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 알고리즘을 풀다 내가 삽입 정렬도 구현하지 못하는 것을 발견했고, 잊지 않고자 기록한다... 먼저 삽입 정렬이란 다음과 같다. (오름차순 정렬이라고 가정) https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC 삽입 정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 삽입 정렬(揷入整列..

[Algorithm] 위상 정렬 - C

https://m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ... blog.naver.com https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-sort [알고리즘] 그림으로 알아보는 위상 정렬(Topology sort) 위상정렬은 순서가 정해져 있는 노드..