꾸준한 개발일기

문제 리뷰 0-1 BFS의 정의에 대해 다시 한번 생각하게 된 문제. 0-1 BFS에서 최소거리를 생각할 때, "상태"를 고려해야함을 알게 된 문제. 시간 복잡도 시간제한: 2초, 메모리: 192MB N x M 격자 (N,M: 1,000) O (200 x N^2) 까지 가능 유형 (1,1) → (N,M) 최단 경로 최단 거리 구하기 0-1 BFS ( v ) 문제의 조건에 따라, 가중치 (weight): 한 칸으로 모두 동일하므로 가능 다익스트라 플로이드-워셜 벨만 포드 0-1 BFS "상태" 고려하기 설계에 들어가기 앞서, 0-1BFS 최단거리에 대해 다시 한번 생각해보자. 1. BFS는 "동시에" 퍼져나가는 구조이다. 각 이동은 각각의 "상태"를 가지고 있다고 생각할 수 있다. (1,1) → (1,2)..

문제리뷰 해당 문제는 문제 제목에서 알 수 있듯 "최단경로"를 구하는 문제이다. 또한, Input Size (노드개수, 엣지개수)에 따라 시간복잡도에 맞는 최단경로 알고리즘을 분류해낼 수 있는가?를 의도한 문제인 것 같다. 다익스트라와 플로이드-워셜과 같은 최단경로 알고리즘을 복기할 필요성을 느낀 문제이다. 풀이 시간복잡도 분석 2 "모든 노드"에 대한 최단거리를 구할 수 있고, 시간복잡도는 O(E logV)이다. 따라서, 시작노드 -> v1 -> v2 -> N 과 시작노드 -> v2 -> v1 -> N의 최단거리 중 최솟값을 구하면 시간복잡도도 초과하지 않고 목표로하는 값을 구할 수 있다. 단, 여기서 다익스트라를 dijkstra(시작노드), dijkstra(v1), dijkstra(v2) 총 3번 돌..

https://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 문제분석 시간제한: 1초, 메모리제한: 512MB 1. 시간복잡도 분석 - 통신탑(노드) 개수: 100,000 - 간선의 개수: 100,000 ▶O(V*E) (불가), O(V^2) (불가), O(E^2) (불가) ▶O(V), O(E) or log scale로 낮춰야.. 2. 유형 분석 그래프문제인 것 같긴한데 log scale로 떨어트려야 함. 1) LCA ->..