이것 저것 뚝딱거리는 사람 이것 저것 뚝딱거리는 사람

플로이드-워셜(Floyd-Warshall) 알고리즘 그래프의 모든 노드 간 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 $O(n^3)$이므로 모든 최단 경로가 필요하지만 노드의 수가 적을 때 사용할 수 있다. 아이디어 한 노드(k)가 다른 두 노드(a, b)의 중간지점이라 생각한다면, a에서 b로 가는 경로는 $a-k-b$ 이다. (k가 a혹은 b라면 경로는 a-b가 된다.) $a-k-b$를 모두 조사한다면 a-b간 최단 경로를 알 수 있다. 아래와 같은 그래프를 가정하면 2를 중간 노드로 둘 경우, 2-2-3, 2-2-5, 3-2-5의 세 가지 경로의 값을 알 수 있다. 이 값들 중에서 3-2-5의 경우 3-5로 가는 경로보다 값이 작으므로 업데이트 해준다. 코드 for k in range(1, n..

이진 탐색 (이분 탐색, Binary Search) 이진 탐색 트리와 같이 정렬된 리스트에서 탐색 범위를 두 부분으로 나누어 특정 값을 찾는 방식 앞이나 뒤에서부터 순서대로 원하는 값을 찾는 순차 탐색보다 훨씬 빠르다. 순차 탐색은 $O(N)$의 시간 복잡도를 가지나, 이진 탐색은 $O(logN)$의 속도를 가진다. 빠르기 때문에 효율성을 따져서 무언가를 찾는 문제에서 생각해 볼법하다. 알고리즘 우선 정렬된 리스트에서 최소값의 인덱스를 left, 최대값의 인덱스를 right로 둔다. left와 right를 통해 mid를 만들어준다. mid와 찾는 값$x$ 비교 mid가 더 큰 경우 left = mid+1, mid가 더 작은 경우 right = mid-1 2, 3, 4번을 left>right가 될 때까지 ..