봉황대 in CS

백준 2224번을 풀며 플로이드-와샬 알고리즘을 사용할 때 주의해야 할 점을 깨닫게 되었고, 이를 잊지 않기 위해서 이렇게 글로 남긴다. 플로이드-와샬 알고리즘 이 알고리즘이 무엇인지에 대해서는 이전에 작성한 글을 참고하길 바란다. [알고리즘] 플로이드-와샬(Floyd-Warshall) 알고리즘 플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모 eunajung01.tistory.com 문제 2224번: 명제 증명 첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전..

플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 ) 즉, (1) 정점 a에서 정점 b로 가는 최소 비용과 (2) 정점 a에서 정점 k로 가는 비용 + 정점 k에서 정점 b로 가는 비용을 비교하여 더 적은 비용을 가지는 쪽을 취하는 것이다. N개의 노드가 있을 때, N번만큼의 단계를 반복하여 점화식에 따라 2차원 리스트를 갱신하기 때문에 동적 계획법(Dynamic Programming) 알고리즘에 속한다. ( ↔︎ 다익스트라 : 탐욕(그리디) 알고리즘 ) * 동적 계획법(Dynamic Programming, D..