Elevation

앞서 4편에서는 하나의 출발점으로부터 각 정점의 최단경로를 구하는 알고리즘들에 대하여 알아보았다. 이번에는 임의의 두 정점 간 최단경로를 구하는 방법에 대해 알아보자. 플로이드-워셜모든 정점 간의 최단 거리가 필요할 때 가장 널리 사용되는 알고리즘이 플로이드-워셜(Floyd-Warshall) 알고리즘이다. 플로이드-워셜 알고리즘의 아이디어는 단순하다. $k$번 정점을 거쳐갈지 말지를 기준으로, 다음과 같은 점화식을 이용해 정점 $a$와 $b$ 간의 최단 거리를 구하게 된다. $$dist[a][b]=\min(dist[a][b], dist[a][k] + dist[k][b])$$ 따라서 인접 행렬을 이용해서 그대로 구현할 수 있다. 자기 자신으로 이동하는 거리는 0, 간선이 이어져 있지 않은 배열의 나머지 ..

https://www.acmicpc.net/problem/6198은근히 발상이 어려워서 고민을 했다. ​포인트는 한 건물에서 볼 수 있는 건물의 수를 따로따로 더하는 것이 아니라, 0~N-1까지 스캔하면서 해당 건물이 보이는 건물의 수를 더해준다고 생각하는 것이다. 예제를 가지고 순차적으로 사고해 보면, i번째 건물의 턴에서 자기보다 높이가 낮은 건물들은 치워주면 된다고 생각할 수 있다. 이때 순차적으로 스캔하기 때문에 최신(직전)의 건물들만 치워주면 높이 내림차순으로 자동 정렬되기에 추가적인 절차가 필요하지 않다. 후입선출이므로 스택을 사용한다. import sysinput = sys.stdin.readlineN = int(input())h = [int(input()) for _ in range(N)]..