본문 바로가기

분류 전체보기

 (698)
최단 경로. [11404] [1. 문제 설명] N 개의 정점에 M 개의 edge 가 있을 때, 모든 도시 쌍 (A, B) 에 대해서 A에서 B로 가는데 필요한 최소비용을 출력한다. [2. 풀이 접근] 다익스트라 알고리즘 => 정점의 개수는 edge 의 개수에 비해 무시할 수 있으므로 (계산 편리성을 위해), 이 문제에서 다익스트라 시간 복잡도는 O(ELogV), 최대 O(100000*7) => 필요한 전체 경로 개수 N^2, 최대 10000 => 전체를 구해야 할 때, (10^4)*(10^5)*7 == 7*10^9 => 대략 7초, 시간 초과 발생 가능성이 높음 플로이드-워셜 알고리즘 (위키피디아 참조) [A. 개요] edge 의 가중치가 음이거나 양인 (음수 사이클이 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘 (문제 입..
최단 경로. [11657] [1. 문제 설명] 그래프 내 음수 가중치가 있을 때, 1번 정점에서 각 정점으로의 최단 경로를 출력 음수 사이클이 발생하는 경우는 -1 하나만 출력 특정 노드를 도달 할 수 없는 경우에 -1 출력 [2. 풀이 접근] edge 에 음수 가중치가 있는 경우는 다익스트라 알고리즘을 이용하여 최단 경로를 구할 수는 없다. 다익스트라 알고리즘은 정점을 지날 수록 경로의 가중치가 커지는 것을 기반으로 하기 때문이다. (정점을 여러 개 지났는데, 오히려 가중치가 작아지는 경우...) 이 경우, 벨만포드 알고리즘을 이용하여 최단 경로를 계산하는데, 여기서 중요한 것은 음수 사이클이 발생하는 것을 판단하는 것이다. A -> B -> C 로 갈 때, A -> B 의 weight 가 +2 이고, B -> A 의 weigh..
최단경로. [9370] [1. 문제 설명] 임의의 출발지에서 임의의 목적지들에 최단 경로로 갈 때, 특정 경로를 거치는 경로 역시 각 목적지들에 대해 최단 경로가 될 수 있는가? [2. 풀이 접근] A. 오답이었던 접근 방법 1 다익스트라 탐색 중, 특정 경로를 통과한 정보를 추가로 저장함 (from -> to 가 문제에 제시된 각 노드라면 true, 그렇지 않다면 false) 다익스트라 탐색 중, 목적지 노드에 도착한 경우, from node 내 정보를 토대로, 특정 경로를 통과했다면, 해당 목적지는 특정 경로를 통과했다고 저장. (경로 코스트의 합이 최소랑 같다면 => 최단 경로가 여러개 있는 것으로, true 일때 만 저장(default: false), 경로 코스트의 합이 최소라면 => true, false 상관 없이 저..
최단 경로. [13549] [1. 문제 설명] 수평선의 임의 시작점에서 특정 위치까지 가장 빨리 이동할 때 걸리는 시간 현재 위치 x에서 1초 후에 x-1, x+1 로 이동하거나 0초 후에 순간이동 할 경우 2x 위치로 이동할 수 있음. [2. 풀이 접근] 다익스트라로 접근 할 필요는 없음 이동하는데 걸리는 시간은 0 아니면 1이고, 순간이동하는 경우는 같은 노드로 봐도 되므로, (x 나 2x 나 방문 순서가 같다.) 모든 edge 는 1 의 가중치를 갖는다고 볼 수 있음 따라서, bfs 로 최단 경로를 구할 수 있다. 1차 풀이에서 틀렸 던 점은 왼쪽으로 이동하는 경우 x 가 음수가 될 수 있는데, 이에 대한 예외처리 (out of bound) 를 하지 않은 것이다. [3. 코드]
최단 경로. [1504] [1. 문제 설명] 임의로 주어진 두 정점을 반드시 통과하면서 1번 정점에서 N번 정점으로 최단거리를 구한다. (이 과정에서 한번 이동했던 정점은 물론 간선도 다시 이동 할 수 있다.) [2. 풀이 접근] A. 오답이었던 접근 방식 현재 반드시 지나야 하는 정점의 개수를 기록하여 int costs[2][N]; 을 업데이트 함 => 비슷한 문제가 있었음. (https://testkernelv2.tistory.com/337) 반드시 지나야 하는 정점의 개수를 셀 때, 같은 정점을 두번지나는 경우를 방지하기 위한 처리 => 현재 인접 정점을 테스트 할 때, heap 에서 pop 한 노드에 저장된 slice 를 순회하여 같은 정점인지 아닌지를 체크 후, 업데이트 한번에 다익스트라 실행으로 답을 구할 수 있을 것..
03. 동적 계획법 - 예제1 [예제1 => 합친 LIS] [예제2 => 원주열 외우기]
03. 동적 계획법 [1. 개요] 큰 의미에서 분할 정복과 같은 접근 방식 그러나 하나의 문제의 답을 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함 두 번 이상 계산되는 부분 문제를 중복되는 부분문제라고 한다. 계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적을 증가한다. (같은 값을 두번 이상 계산할 일이 빈번해질 수 있다.) 한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법을 메모이제이션이라 한다. 보통 동적 계획법 알고리즘 구현은 아래와 같은 두 단계로 구성 문제를 완전 탐색을 이용해 해결 중복되는 부분 문제를 한번만 계산하도록 메모이제이션을 적용 [2. 메모이제이션] 수학의 함수와 프로그래밍에서 함수는 사실 서로 다르다 프로그래밍을 할 때는 함수의 불변성이 성립하지 않을 수 있기 때문이다. ..
02. 분할 정복 예제 - 2 [1. 예제 => 팬미팅]
최단 경로. [1753] [1. 문제 설명] 방향그래프에서 edge 의 weight 가 주어질 때 시작점에서 그래프 내 모든 정점에 최단 거리로 방문할 때, 모든 정점의 최단 거리 값을 출력한다. [2. 풀이 접근] 다익스트라는 우선순위 큐를 사용하여 구현 할 경우 그 시간 복잡도는 아래와 같다 O(V + ElogV) 이며, 여기서 E 는 Edge 의 개수, V 는 Vertex 개수 이다. heapify 에 대하여 처음 풀이에서 heapify 를 하여 우선순위를 재조정하는 코드가 있었다. => 힙에 이미 푸쉬되었지만, 다른 경로를 거쳐 오는 경우가 더 빠른 경우 가 발생할 수 있으므로 실행시간이 다소 늦음 => heap 에 푸쉬된 특정 정점을 찾기 위해 O(n) 에 시간이 걸리기 때문 => heap 은 오름/내림 차순 등으로 정..
이분 그래프 https://testkernelv2.tistory.com/338?category=536991

티스토리툴바