알고리즘 공부방

https://www.ioi-jp.org/joi/2017/2018-ho/index.htmlhttps://oj.uz/problems/source/307 1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다. 1. stove 만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?전체 구간을 기준으로 난로를 켜..

문제 https://www.acmicpc.net/problem/1507 어떤 그래프에서의 임의의 두 정점 간의 최단거리가 모두 주어졌을 때, 조건을 만족하며 간선의 개수를 최소화할 수 있는 그래프를 찾는 문제이다. 풀이 기본적인 풀이는 $N^2$ 개의 간선을 모두 생성한 후, 필요 없는 간선을 하나씩 지워 가며 문제를 해결한다. 그렇다면 과연, 필요 없는 정점을 어떻게 구할 수 있을까? u->v 의 간선을 삭제하기 위해서는 u->w->v 의 경로와의 거리와 비교해 볼 필요가 있다. 1) adj[u][v]v 의 간선을 삭제해서는 안된다. u->v 의 최단거리는 다른 경유점을 거쳐 가면 안됀다는 뜻이기 떄문이다. 2) adj[u][v]==adj[u][w]+adj[w][v] u->v 의 간선을 굳이 놔둘 필요..

플로이드-워셜 알고리즘은 그래프에서 모든 점들의 쌍 (u, v) 간의 최단거리를 다 구하는 알고리즘이다. 경유점을 다음과 같이 정의하자. u -> x1 -> x2 -> x3 -> x4 -> v 일때, x1, x2, x3, x4는 경유점. 즉, 어떤 경로에서 시작점과 끝점을 제외한 정점들을 의미한다. 이렇게 정의하고, DP 를 사용한다. k-1번째 루프에서는 1~k-1의 정점들만을 경유점으로 하는 최단경로들의 값을 dp 테이블에 저장한다. 이제, 새로운 정점 k가 들어왔다고 생각하자. 최단거리는 k를 경유점으로 포함하는가, 하지 않는가로 나뉘고, 이는 다음과 같은 점화식으로 표현할 수 있다. $dp[k][i][j]=min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])$ 따라..

SPFA 는 벨만 포드 알고리즘의 확장 알고리즘이다. 벨만 포드에서 1 단계의 완화를 시킬때, 간선들을 임의로 골라서 완화시켰기 때문에 비효율적인 면이 있었다. 어떠한 정점의 최단거리가 감소하지 않았다면, 그 정점에서 시작하는 간선들을 완화시키는 것은 의미가 없다. 이를 이용하면, 어떠한 정점이 완화되어 최단거리가 바뀌었다면, 그 정점으로부터 시작하는 간선들만 완화해주면 된다. 이는 BFS 와 비슷하게 큐를 이용하여 구현할 수 있다. 처음에 시작점을 큐에 넣어논 후, 그 정점으로부터 완화를 시키고, 또 성공적으로 완화된 정점들에 대해서 다시 큐에 넣어준다. 이 방법도 벨만포드와 마찬가지로 $O(VE)$ 이다. 하지만, 만약 어떤 정점 v가 이미 큐에 들어가 있고, 아직 큐에서 나오지 않은 상태인데, 지금..

벨만-포드 알고리즘은 다익스트라 알고리즘과는 다른 방법으로 그래프에서의 단일 시작점에서의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 $O(ElogV)$의 매우 빠른 시간복잡도를 갖고 있지만, 음수간선에 대해 최단거리를 구하지 못한다는 단점이 있다. 벨만-포드 알고리즘은 이를 보완하여 음수 간선에 대해서도 최단거리를 구할 수 있게 해 준다. 기본적으로, 그래프에서 각 간선을 "완화"하는 작업을 반복한 후, 이러한 과정을 적질히 계속하여 결국은 모든 노드에 대해 최단 거리를 구해 낸다. 일단, 모든 간선에 대해 이와 같은 성질이 성립한다. u에서 v로의 간선 w가 존재한다면, $dist[v]dist[u]+w$ 라면 $dist[v]=dist[u]+w$ 로 조금 더 작게 만들어 줄 수 있다. 이를 ..

다익스트라 알고리즘은 그래프에서의 최단 거리를 구하는 알고리즘이다. 기본적으로 너비 우선 탐색과 비슷한 방법으로 작동한다. 사실, 너비 우선 탐색은 다익스트라에서 모든 간선의 길이가 1인 특수한 경우라고 봐도 된다. 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단경로를 계산한다. 여기선 너비우선탐색과는 다르게, 지금까지 큐에 넣은, 우선순위 큐(Priority Queue를 이용하여) 방문할 정점들 중 가장 거리가 짧은 정점을 골라 그곳을 방문한다. 여기서 중요한 점은 bfs에서는 vis check 를 큐에 넣기 직전, 즉 실제로는 방문하지 않았지만, 발견 되었고, 곧 방문할 정점에 표시해 준다. 즉, 큐에 한번이라도 들어가기 위해선 vis check 를 해줘야 다른 정점이 이 정점을..