평소에 다양한 그래프 알고리즘을 알고 있는데, 어느 순간 무슨 차이가 있지라는 생각이 들며 헷갈리기 시작했다. 특히 크루스칼, 프림 알고리즘은 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 ..

Greedy Algorithm - 결정해야할 때 그 순간에 가장 좋다고 생각하는 것(기준이 필요)을 선택하면서 답을 찾아가는 알고리즘 - 그 때는 최적일지도 모르지만 최종적으로는 답이 최적이 아닐 수도 있다. - 기준을 하나 선택해서 계속 적용하는 것 - 왜 그 기준을 선택하는 것이 정답인지를 증명해야 한다. 그리디 알고리즘의 흔한 예시인 거스름돈 문제는 사실 동전이 배수 관계이기 때문에 성립 가능하다. 💚1080 행렬 결국에는 0, 1밖에 없으므로 궁극적으로 연산을 아예 안 하는 것과 1회 한 것으로 나눌 수 있다. 3 X 3보다 큰 행렬을 바꾸는 연산을 할 때 가장자리가 연산횟수가 1회로 가장 적다. 그걸 기준으로 바꾸는 연산을 할지 말지 결정해야 한다. 행렬을 순회하면서 가장자리의 정보를 가지고 판..