전체 글(301)
-
[백준] 1916: 최소 비용 구하기
최소 비용을 구하는 알고리즘 중 이 문제는 출발점과 도착점 간 거리만 최소로 구하면 되므로 다익스트라 알고리즘을 쓰면 된다. 사용한 자료구조 ✔︎ vector dist 출발점으로부터의 거리 기록 ✔︎ vector weights 출발점별로 (도착점, 간선 길이) 기록 ✔︎ priority_queue pq 최소 힙에 출발점 기준 거리와 노드 기록 처음에 다익스트라를 시작할 때 start에 대한 초기화가 필요하다. dist[start] = 0 세팅한 후 (start, 0)라는 pair를 만들어서, 즉 start로부터의 거리를 start부터 삽입해야 한다. 그 후 간선이 짧은 순으로 출발점으로부터 거리가 단축되는지 확인한다. /** * https://www.acmicpc.net/problem/1916 * 출발점..
2022.05.13 -
[그래프 알고리즘] 다익스트라와 크루스칼의 차이
평소에 다양한 그래프 알고리즘을 알고 있는데, 어느 순간 무슨 차이가 있지라는 생각이 들며 헷갈리기 시작했다. 특히 크루스칼, 프림 알고리즘은 MST(최소 스패닝 트리)의 일종이고, 다익스트라는 하나의 정점에서 다른 모든 정점(일대다)로의 최단 경로를 위한 알고리즘임은 이론상 알고 있으나, 응용할 때 어떤 알고리즘을 써야할지 난감했다. 그래서 서치한 결과 찾은 차이점 정리! 다익스트라 크루스칼 구현 방법 우선순위 큐 + dist[점화식] 우선순위 큐 + Union-Find 중심 정점(Node) 중심 간선(Edge) 중심 시작점 출발점이 정해져 있는 경우 간선이 가중치가 작은 것부터 시작 용도 일대다 정점 간의 최소 거리 파악 최소 신장 트리(MST) 파악 모든 정점 방문 정점 중심이므로 모든 정점의 끝까..
2022.05.13 -
[백준] 16437: 양 구출 작전
https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 해당 문제는 DFS, BFS 유형 문제로 출제되어있으나 사실 풀다보면 위상정렬이 적합할 것 같아서 위상정렬로 풀었다. 왜냐하면 하나의 노드의 parent가 하나라는 점이 위상정렬을 가능케하였고, child 노드를 탐색한 후에 parent 노드를 탐색할 수 있었기 때문이다. 물론 이러한 특징들이 있어도 DFS로도 풀수 있는 문제이긴 하다. child의 양 수를 모두 수합한 다음 현..
2022.05.13 -
[백준] 1937: 욕심쟁이 판다
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) ..
2022.05.13 -
[백준] 2933: 미네랄
https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 복잡한 DFS 문제를 풀고 싶어서 도전했다가 아주 큰 코 다쳤다. 사실 DFS부분은 큰 무리 없이 처리하였으나 시뮬레이션 과정에서, 마치 테트리스 같이 이동하는 게 정말 쉽지 않았다. 이 문제는 크게 1) 창영이와 상근이가 번갈아가며 막대기 던지기 ➡️ 시뮬레이션 2) 분리된 클러스터 존재 유무 파악 ➡️ DFS(바운드 주의) 3) 존재할 시에는 중력의 힘으로 내리기 ➡️ 시뮬레이션(y좌표를 기준으로 내림차순 ..
2022.05.12 -
[백준] 나머지 합
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..
2022.05.12