[2024 동계 모각코] 9주차 계획
9주차 계획
개요
9주차(2. 26 ~ 3. 4)의 계획입니다.
- 30장 최단 경로 알고리즘
- 서론
- 문제: ROUTING
- 문제: FIRETRUCKS
- 문제: NTHLON
- 문제: TIMETRIP
- 문제: DRUNKEN
- 문제: PROMISES
- 31장 최소 스패닝 트리
- 서론
- 문제: LAN
- 문제: TPATH
30장 최단 경로 알고리즘
서론
그래프의 두 노드의 경로를 파악하는 알고리즘 다익스트라에 대해 배우고, 다익스트라의 단점을 보완한 Bellman-Ford 알고리즘과, All-pair shortest path algorithm의 Floyd-marshall 알고리즘에 대해 배웁니다.
문제: ROUTING
단순히 priority_queue를 활용하여 다익스트라를 구현하는 문제지만, 크기 제한 때문에 애먹었던 문제입니다.
큐 반복문 내부에서 distance가 줄어드는게 아님에도 q.push()를 하는 바람에.. 메모리 초과가 났습니다.
문제: FIRETRUCKS
다중 출발점 최단 경로 문제를 풀어봅시다.
multi-source에 대해서도 여러 번 다익스트라가 아닌 다익스트라 한번으로만 풀 수 있습니다!
문제: NTHLON
문제를 잘 읽고, 다익스트라를 잘 적용해보는 문제입니다.
문제: TIMETRIP
이번에는 음수 간선과 사이클이 있어도 최단 경로를 탐색할 수 있는(정확히는 있어도 판별이 가능해 알고리즘이 동작하는) 벨만 포드 알고리즘으로 문제를 풀어봅시다.
문제: DRUNKEN
Floyd-Warshall 알고리즘을 이용해봅시다.
노드를 계속 포함시켜가며 최단 거리를 단축하는 알고리즘인데, 이를 포함시켜가는 순서는 아무렇게나 해도 상관없다는 것을 이용해서,
단속 시간을 기준으로 노드를 오름차순 정렬하면, 지금 하고 있는 노드의 단속 시간은 현재까지 지나온 노드의 단속 시간의 최댓값이므로 이를 이용하여 점화식을 하나 만들어서 푸는 문제입니다.
문제: PROMISES
이번에도 Floyd-Warshall 알고리즘을 이용해서 먼저 dist를 업데이트 후 edge에 따라 업데이트 해가며 업데이트가 안되는 edge를 세는 문제입니다.
아이디어까진 떠올렸으나, 생각하지 못한 조건이 있어 아쉬웠습니다.
31장 최소 스패닝 트리
서론
최소 스패닝 트리(MST)를 구하는 알고리즘으로 Union-find와 같이 사용하는 Kruscal’s algorithm과, 다익스트라 방식과 비슷한 Prim’s algorithm을 배워봅시다.
문제: LAN
MST의 가중치를 구하는 문제입니다.
문제: TPATH
문제를 변형하여 그래프의 최소 너비 경로를 찾아봅시다.