코딩 테스트 개요 및 문제 풀이를 위한 자바스크립트 문법 06

이 글은 네이버 블로그에 2024년 2월 4일에 올렸던 것을 그대로 옮겨온 것입니다.

1. 다익스트라 알고리즘

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치를 갖는 간선이 없을 때 사용할 수 있습니다.

작동 원리:

1. 출발 노드를 설정하고, 출발 노드로부터 각 노드까지의 거리를 저장하는 배열을 무한대로 초기화합니다. 출발 노드의 거리는 0으로 설정합니다.
2. 아직 방문하지 않은 노드 중에서 가장 가까운 노드를 선택합니다.
3. 선택한 노드를 통해 다른 노드로 가는 거리를 계산하고, 기존에 저장된 거리보다 작으면 업데이트합니다.
4. 모든 노드를 방문할 때까지 2와 3의 과정을 반복합니다.

2. 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 모든 쌍의 노드 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 가중치가 음수일 때도 사용할 수 있지만, 음의 순환(cycle)이 없어야 합니다.

작동 원리:

1. 모든 노드 쌍에 대한 최단 거리를 저장할 2차원 배열을 초기화합니다. 자기 자신으로 가는 거리는 0으로, 나머지는 무한대로 설정합니다.
2. 모든 간선에 대해, 두 노드 사이의 거리를 간선의 가중치로 설정합니다.
3. 각 노드를 거쳐가는 경우를 고려하여 모든 노드 쌍의 최단 거리를 업데이트합니다. 이때, dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 공식을 사용합니다.
4. 모든 노드 쌍에 대해 3의 과정을 반복합니다.

3. 벨만 포드 알고리즘

벨만 포드 알고리즘은 다익스트라 알고리즘과 유사하게 한 노드에서 다른 모든 노드까지의 최단 경로를 찾지만, 음의 가중치를 가진 간선이 있을 때도 사용할 수 있습니다. 또한, 음의 순환을 감지할 수 있습니다.

작동 원리:

1. 출발 노드로부터 각 노드까지의 거리를 저장하는 배열을 무한대로 초기화하고, 출발 노드의 거리는 0으로 설정합니다.
2. 모든 간선에 대해, 만약 해당 간선을 거치는 것이 더 짧은 경로를 제공한다면, 해당 노드까지의 거리를 업데이트합니다.
3. 2의 과정을 노드의 수 - 1번 반복합니다. 이는 최악의 경우 모든 노드를 거쳐가는 경우를 고려줍니다. 4. 음의 순환을 감지하기 위해, 모든 간선에 대해 한 번 더 거리 업데이트 시도를 합니다. 이 때 거리가 업데이트되면 그래프에 음의 순환(cycle)이 존재하는 것입니다.

1. 다익스트라 알고리즘 예시

문제: 도시 A에서 도시 F까지 가는 최단 경로를 찾으려고 합니다. 각 도시 간의 거리는 다음과 같습니다.

• A → B: 4
• A → C: 2
• B → C: 5
• B → D: 10
• C → E: 3
• D → F: 11
• E → D: 4

해결:

1. 출발점 A에서 출발하여, A에서 각 도시까지의 초기 거리를 무한대로 설정합니다(단, A의 거리는 0).
2. A에서 직접 연결된 도시 B와 C의 거리를 갱신합니다(A → B: 4, A → C: 2).
3. 가장 가까운 도시 C를 선택하고, C를 통해 다른 도시로 가는 거리를 계산하여 필요한 경우 거리를 갱신합니다(C → E: 2 + 3 = 5).
4. 다음으로 B와 E를 거쳐 나머지 도시들의 거리를 갱신합니다.
5. 이 과정을 반복하며, 각 단계에서 최단 거리를 갖는 도시를 선택하고 거리를 갱신합니다.
6. 최종적으로 A에서 F까지의 최단 거리를 찾습니다.

2. 플로이드 워셜 알고리즘 예시

문제: 세 개의 도시 A, B, C가 있고, 각 도시 간의 거리는 다음과 같습니다.

• A → B: 5
• B → C: 3
• C → A: 2

해결:

1. 모든 도시 쌍(A, B, C)에 대해 최단 거리를 초기화합니다. 직접 연결되지 않은 도시의 거리는 무한대로 설정합니다.
2. 각 도시를 거쳐 가는 경로를 고려하여 거리를 업데이트합니다. 예를 들어, A → B → C의 경로를 확인하고, A → C보다 짧은 경우 거리를 업데이트합니다.
3. 모든 도시를 거쳐 가는 모든 가능한 경로를 고려하여 최종 거리를 계산합니다.

3. 벨만 포드 알고리즘 예시

문제: 도시 A에서 출발하여 다른 도시로 가는 최단 경로를 찾으려고 합니다. 도시 간의 거리는 다음과 같으며, 일부는 음의 가중치를 갖습니다.

• A → B: 4
• A → C: 5
• B → C: -7
• C → B: 2

해결:

1. A에서 각 도시까지의 거리를 무한대로 초기화하고, A의 거리는 0으로 설정합니다.
2. 각 간선에 대해 거리를 업데이트합니다. 예를 들어, A → B는 4, A → C는 5로 설정합니다.
3. 모든 간선을 다시 검사하며, B → C를 거쳐 A → C로 가는 경로가 더 짧은지 확인합니다. 이 경우, A → B → C 경로가 A → C 직접 경로보다 2만큼 더 짧게 됩니다.
4. 모든 간선에 대해 이 과정을 반복하며, 음의 순환을 감지할 수 있습니다. 이 예에서는 음의 순환(B → C → B)이 발생합니다.