
문제 https://www.acmicpc.net/problem/5917 알고리즘 Dijkstra 풀이 최단거리 중 하나의 간선의 값을 두배로 하였을 때의 최댓값을 구하는 문제입니다. 다익스트라임은 최단거리임을 보고 알 수 있습니다. 문제 제한은 N이 100 이하, M은 10000 이하입니다. 단순한 접근으로는 M의 간선들을 하나씩 두배로 만든 후 그때마다 새로이 다익스트라를 사용하는 것입니다. 하지만 M제한이 10000이므로 이 방법은 무리가 있습니다. 이 방법에는 불필요한 부분이 있습니다. 바로 최단거리에 포함되지 않는 간선들 또한 두 배로 바꾸는 것입니다. 이는 아무런 의미가 없는 행동입니다. N개로 이루어진 노드에서 최단거리는 최대 N−1개의 간선을 통해 이루어져 있습니다. 즉..

문제 https://www.acmicpc.net/problem/10652 알고리즘 Dijkstra, BFS 풀이 Bessie와 Elsie가 돌아다닐때 드는 에너지와 Piggy Back 상태에서 드는 에너지가 주어졌을 때, N까지 도달하기 위한 최소에너지는 구하는 문제입니다. 3인통화 문제와 굉장히 유사합니다. 도착지도 하나의 소처럼 취급을 하여 세 마리의 소에서 각각 다익스트라를 사용하면 문제가 해결됩니다. 다만, 각 소마다 그래프를 이동할 때 드는 비용은 동일하므로 다익스트라 대신 BFS를 사용하면 더 빠르게 문제를 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i..

문제 www.acmicpc.net/problem/20968 알고리즘 Dijkstra 풀이 소의 품종마다 서로 연락할 수 있는 관계가 주어졌을 때, 첫 번째 소가 맨 마지막 소에게 메시지를 전달하기 위한 최솟값을 구하는 문제입니다. 일반적으로 PQ를 이용한 다익스트라의 시간복잡도는 O(ElogV)입니다. 문제에서 N제한이 50000이므로 무작정 다익스트라를 사용하게 되면 시간 초과를 받게 됩니다. 빨간색 원이 현재 PQ에서 꺼낸 소라고 하겠습니다. 녹색은 빨간색 품종이 연락할 수 있는 품종을 의미합니다. 만일 위와 같이 녹색품종들이 모두 빨간색에서 메시지를 받을 수 있다면 굳이 첫 번째를 제외한 2, 3, 4번째들을 검사할 필요는 없습니다. 즉 현재 소에서 연락 가능한 품종들마다 가장 가까이 있는 ..

문제 www.acmicpc.net/problem/2398 알고리즘 Dijkstra 풀이 세명이 통화를 하기 위해 간선들을 연결하기 위한 최소비용, 그 때 사용하는 간선들을 출력하는 문제입니다. 사람들이 그래프 위에서 움직여 최적의 장소에서 모이는 문제로 해석해보겠습니다. 각 사람마다 각 노드마다의 최소거리를 알 수 있다면 즉, 한 지점마다 세 사람의 최소거리를 안다면 우리는 어디 지점에서 세 사람이 만나야 하는지 알 수 있습니다. 사람마다 다익스트라를 돌려 총 세번의 다익스트라를 수행하고 그때마다 그 사람이 어디 노드에서 어디 노드로 갔는지를 기록하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (..

문제 www.acmicpc.net/problem/2276 알고리즘 다익스트라 풀이 NXM 격자판에 표면의 높이들이 주어질 때, 채울 수 있는 최대 물의 높이를 구하는 문제입니다. 격자판의 밖에서 격자판으로 물이 스며가는 형태로 구현을 했습니다. 즉 다익스트라의 시작점은 격자판의 테두리 부분이고 도착점은 테두리를 제외한 칸이라고 생각할 수 있습니다. 다익스트라는 하나의 시작점으로부터 하나의 도착지를 구하는 알고리즘이라 이를 적용하려면 약간의 테크닉을 써야합니다. A개의 시작점과 B개의 도착점이 주어졌다면, A개의 시작점들의 조상 시작점과 B개의 도착점들의 조상 도착점을 하나씩 만드는 것입니다. 아래코드에서는 각각 i*j, i*j+1로 사용하였습니다. 그리고 모든 격자판을 연결하는데, 높이가 높은 ..
- Total
- Today
- Yesterday
- Oracle
- dijkstra
- spring
- Suffix Array
- DP
- 세그먼트트리
- SCC
- 스위핑
- kmp
- implementation
- greedy
- 2-SAT
- 트라이
- 좌표압축
- dfs
- 펜윅트리
- string
- union find
- spring boot
- bfs
- 이분매칭
- sweeping
- sorting
- 정렬
- Segment tree
- 동적계획법
- 이분탐색
- hld
- knapsack
- Fenwick
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |