'Coding Test/Algorithm' 카테고리의 글 목록

Coding Test/Algorithm

JinniePark 2021. 9. 27. 00:00

2021. 9. 27. 00:00

한 정점으로 부터 모든 정점으로의 최단거리를 구하는 알고리즘이다.

다만 음의 간선이 있다면 사용할 수 없다.

동작 순서는 일단 출발지를 정하고, 이어져 있는 거리를 저장한다.

그 다음 부터는 가장 짧은 거리에 있는 정점을 방문하고, 해당 정점을 거쳐가는 거리가 더 짧다면 갱신, 아니면 그대로 둔다.

이런식으로 반복해서 모든 정점을 방문하면 끝나게 된다.

그래프와 인접그래프

다익스트라 알고리즘 시작!

추가적으로,, 최적화에 대해 생각해본다면, 가장 짧은 거리를 탐색할 때, 우선순위 큐를 활용한다면 O(nlogN)으로 탐색이 가능하다.

JinniePark 2021. 9. 19. 02:14

2021. 9. 19. 02:14

플로이드-와샬 알고리즘(이하 플로이드 알고리즘)은 최단 경로를 구하는 알고리즘이다.

이미 잘 알고있는 다익스트라 알고리즘은 한 점점으로 부터 다른 모든 정점으로의 최단 거리를 구할 수 있다.

하지만 플로이드 알고리즘은 모든 정점으로부터 모든 정점으로의 최단 거리를 구하는 알고리즘이다.

기본적으로 그래프를 일단 나타내고, 순차적으로 어떠한 정점을 거쳤을 때, 이동하는 비용이 줄어든다면 값을 고치는것을 반복하는 알고리즘이다.

중요한건 (A에서 B로 가는 거리) > (A에서C를 들렀다가 B로 가는거리)이면 작은 값으로 계속 갱신만 해주면 되는거다.

말로하려니까 어렵다. 아래에 그림을 참고해라.

JinniePark 2021. 9. 15. 15:33

2021. 9. 15. 15:33

MST(최소 신장 트리)를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

오늘은 크루스칼 알고리즘에 대해 더 자세히 살펴보도록 하겠다.

크루스칼 알고리즘은 일단 모든 간선을 오름차순으로 정렬하고

순서대로 이어나가다가 사이클이 발생하면 해당 간선은 건너뛴다. 참으로 간단하다.

크루스칼은 프림에 비해 희소 그래프인 경우, 그러니까 간선이 적은 경우 적합하고,

프림은 크루스칼에 비해 간선이 많이 존재하는 밀집그래프에 더 적합하다.

프림 알고리즘은 아래에서 더 자세하게 다룬다.

[알고리즘 기본]PRIM 알고리즘

PRIM 알고리즘 MST(최소 신장 트리)를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다. 오늘은 프림 알고리즘에 대해 더 자세히 살펴보도록 하겠다. 프림 알고리즘을 시작점을 중

jinniepark.tistory.com

일단을 개념적으로 구하는 방법을 그려보았다.

이때 사이클을 검사하는 알고리즘은 Union-Find 알고리즘이 쓰인다.