플로이드-워셜 알고리즘 - 그래프에서 최단 거리를 구하는 알고리즘으로, 모든 노드 간에 최단 경로를 탐색한다. 특징 - 음수 가중치 에지가 있어도 수행이 가능하다. - 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간복잡도 - O(V^3) - 모든 노드 간의 최단 거리를 확인하기 때문에 시간 복잡도가 빠르지 않다. 따라서 이 알고리즘으로 문제를 풀어야 하는 경우 다른 그래프에 비해 노드의 개수 범위가 적게 나타난다. 핵심 원리 - 노드 A부터 노드 B까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 노드 K가 존재한다면, 그것을 이루는 부분 경로 역시 최단 경로이다. - 예를 들어 1 -> 5까지의 최단 경로가 1 -> 3 -> 4 -> 2 -> 5 라면, 1 -> 4, 4 -> 5 역시 최단..

- Graph 현상이나 사물을 정점 vertex과 간선 edge으로 표현한 것. : Graph G = (V, E) 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. - 그래프와 트리의 차이 트리는 사이클을 허용하지 않는 그래프 - 그래프의 표현 1. N x N 행렬로 표현 2. N개의 연결 리스트로 표현 - 그래프 탐색 대표적 두 가지 방법 1. DFS 너비우선탐색 2. BFS 깊이우선탐색 - DFS 스택 자료구조를 이용한다. - 과정 0. 모든 노드를 not visited로 표시한다. 1. 탐색 시작 노드를 스택에 삽입하고, visited로 표시한다. 2. 스택의 최상단 노드에 not visited인 인접 노드가 있으면 스택에 넣고 visited로 표시한다. not visited인 인접 노드가 없으..