최소 비용을 구하는 알고리즘 중 이 문제는 출발점과 도착점 간 거리만 최소로 구하면 되므로 다익스트라 알고리즘을 쓰면 된다. 사용한 자료구조 ✔︎ vector dist 출발점으로부터의 거리 기록 ✔︎ vector weights 출발점별로 (도착점, 간선 길이) 기록 ✔︎ priority_queue pq 최소 힙에 출발점 기준 거리와 노드 기록 처음에 다익스트라를 시작할 때 start에 대한 초기화가 필요하다. dist[start] = 0 세팅한 후 (start, 0)라는 pair를 만들어서, 즉 start로부터의 거리를 start부터 삽입해야 한다. 그 후 간선이 짧은 순으로 출발점으로부터 거리가 단축되는지 확인한다. /** * https://www.acmicpc.net/problem/1916 * 출발점..

평소에 다양한 그래프 알고리즘을 알고 있는데, 어느 순간 무슨 차이가 있지라는 생각이 들며 헷갈리기 시작했다. 특히 크루스칼, 프림 알고리즘은 MST(최소 스패닝 트리)의 일종이고, 다익스트라는 하나의 정점에서 다른 모든 정점(일대다)로의 최단 경로를 위한 알고리즘임은 이론상 알고 있으나, 응용할 때 어떤 알고리즘을 써야할지 난감했다. 그래서 서치한 결과 찾은 차이점 정리! 다익스트라 크루스칼 구현 방법 우선순위 큐 + dist[점화식] 우선순위 큐 + Union-Find 중심 정점(Node) 중심 간선(Edge) 중심 시작점 출발점이 정해져 있는 경우 간선이 가중치가 작은 것부터 시작 용도 일대다 정점 간의 최소 거리 파악 최소 신장 트리(MST) 파악 모든 정점 방문 정점 중심이므로 모든 정점의 끝까..

DFS를 풀다가 잠깐 이거 중복되겠는데라고 생각이 들었으나 우선은 마저 DFS로 풀었다. DFS에서 그냥 탐색이 아니라 상하좌우 중 한 가지 경로를 택해야 하므로 += operator가 아니라 max 값을 추출해야 한다. 역시나 바로 시간 초과가 발생하였다. #include #include #include using namespace std; int dx[] = {0, 0, -1, 1}; int dy[] = {1, -1, 0, 0}; bool visited[501][501]; long long trees[501][501]; int n; bool inside(int x, int y) { return x >= 0 && x = 0 && y < n; } int dfs(int x, int y) ..

https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 복잡한 DFS 문제를 풀고 싶어서 도전했다가 아주 큰 코 다쳤다. 사실 DFS부분은 큰 무리 없이 처리하였으나 시뮬레이션 과정에서, 마치 테트리스 같이 이동하는 게 정말 쉽지 않았다. 이 문제는 크게 1) 창영이와 상근이가 번갈아가며 막대기 던지기 ➡️ 시뮬레이션 2) 분리된 클러스터 존재 유무 파악 ➡️ DFS(바운드 주의) 3) 존재할 시에는 중력의 힘으로 내리기 ➡️ 시뮬레이션(y좌표를 기준으로 내림차순 ..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합은 맞는데 구간을 구하면서 O(N^2)으로 탐색하다보니 시간이 초과됐다. 그런데 방법을 찾다보니 O(N) 혹은 O(M)이라는 시간복잡도를 가질 수 있다. For문을 돌면서 나머지가 M이 되는 구간을 찾는 것이 아니라, 아예 나머지가 동일한 수끼리 저장을 해놓는다. 그리고 나머지가 동일한 구간합(0에서부터 A까지, 0에서부터 B까지)끼리 빼면 B..

분할 정복(Divide & Conquer) - 분할 정복은 문제를 2개 또는 그 이상의 작은 부분 문제로 나눈 다음 푸는 것(분할) - 푼 다음에는 다시 합쳐서 정답을 구함(정복) - 대표적인 분할 정복 알고리즘 📌 퀵 소트 📌 머지 소트 📌 큰 수 곱셈(카라추바 알고리즘) 📌 FFT ✅ DP와 분할정복의 차이 작은 부분 문제가 중복이 되는가?의 차이다 DP는 작은 부분이 중복되기 때문에 메모이제이션으로 중복 제거 분할 정복의 경우에는 중복되지 않기 때문에 한 번씩만 연산하면 된다. 이분 탐색(Binary Search) 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘 정렬이 전제되어야 한다. 리스트의 크기를 N이라고 했을 때, O(lgN)의 시간이 걸린다. 상한과 하한(Upper & Lower ..