NEMOSTAR5

'모든 정점에서 '모든정점'으로의 최단 경로르 구하고 싶다면 플로이드 와샬 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 '거져가는 정점'을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 0 5 무한 8 7 0 9 무한 2 무한 0 4 무한 무한 3 0 위 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. X에서 Y로 가는 최소 비용 VS X에서 1로 가는 비용 + 1에서 Y로 가는 비용 노드 1을 거쳐가는 경우 0 5 무한 8 7 0 9 15 2 7 0 4 무한 무한 3 0 노드 2를 거치는 경우 0 5 14 8 7 0 9 15 2 7 0 4 무한 무한 3 0 위와 같이 노드 3과 노드 4에 반복해주면 된다..

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선을 포함할 수 없다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 '최단 거리는 여러개의 최단 거리로 이루어져있기 때문이다' 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다시 말해 다익스트라 알고리즘은 '현재까지 알고 있던 최단 경로를 계속해서 갱신'합니다. 1. 출발 노드를 설정합니다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다. 3. ..

다이나믹 프로그래밍은 줄여서 DP라고도 하고, 동적 계획법이라고도 불린다. 다이나믹 프로그래밍이란 '하나의 문제는 단 한번만 풀도록 하는 알고리즘'이다. 일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. (다만 분할 정복 기법은 '정렬'과 같은 몇몇 요소에 대해서는 동일한 문제를 다시 풀게 되는 단점이 없습니다. 그 예시로 퀵 정렬이나 병합 정렬은 매우 빠릅니다.) 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열의 점화식: D[i] = D[i - 1] + D[i - 2] 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다. 1번 가정. 큰 문제를 작은 문제를 나눌 수 있다. 2번 가정. 작은 문제에서 구한 ..

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘. 예를 들어, 여러개의 도시가 있을 경우 가장 적은 가중치를 가지는 도시를 먼저 연결한다. 이걸 계속 반복해 나아가며 결국에는 모든 노드를 연결해 그래프를 완성해 나가는 것이다. 최종적으로 완성되는 그래프의 간선 숫자는 노드 숫자 == 노드 숫자 - 1 "간선을 거리가 짧은 순서대로 그래프에 포함시킨다." 1. 노드들의 가중치를 오름차순으로 정렬을 수행한다. 2. 정렬된 순서에 맞게 그래프에 포함시킨다. 3. 하지만, 사이클이 형성되는지 확인하고 발생하지 않는 경우에만 간선에 포함시킨다. (사이클 테이블) 사이클이란? 코드 추가 예정.