본문 바로가기

알고리즘

 (405)
SCC. [2152] [1. 문제 설명] https://www.acmicpc.net/problem/2152 [2. 풀이 접근] 아래 문제와 유사하다. https://testkernelv2.tistory.com/445 이 문제에서 헷갈릴만한 부분을 몇가지 정리하면 아래와 같다. S 에서 시작해서 T 에서 끝나야 한다. => 만약, S 와 T 가 같은 SCC 에 있다고 했을 때, S ~~~> T ~~~> Z 로 갈 수 있다고 했을 때, Z 를 경유하지 않고 T 에서 끝나야 하는가? 1번 질문에 대해서 Z 경유 없이 T 에서 끝내야 한다면, 문제가 까다로워 질 수 있다. 같은 SCC 내에서 S 에서 T 까지 최대한 많은 도시를 경유해야하는 문제를 또 풀어야 하기 때문이다. 그러나 문제에서 같은 도시를 여러 번 방문 할 수 있다고 ..
최소공통조상. [1761] [1. 문제 설명] https://www.acmicpc.net/problem/1761 [2. 풀이 접근] 구해야 하는 노드 쌍의 개수가 1개라면, 단순한 접근으로 풀 수 있지만, 최대 1만개의 노드 쌍의 거리를 구해야 하므로, 단순한 접근으로는 시간 초과 발생이 매우 높다. 트리가 한쪽 방향으로 스큐되어 있다고 생각해보면, Leaf 에서 Root 까지 올라갈 때, 하나의 노드쌍에 대해서 O(H) 걸림 쿼리 개수는 총 M 개 단순한 접근 시 전체 시간복잡도는 O(HM) => H 는 최대 4만, M 은 최대 1만, 즉, LCA 를 구할 때, 좀 더 빠른 방법으로 구해야 한다. Sparse table 을 전처리 과정에서 구한 뒤, LCA 를 찾아가고, 그 과정에서 이동 거리를 구한다면, 쿼리 하나 당 거의 상..
최소 공통 조상 솔루션 [1. 개요] 최소 공통 조상 문제는 보통 트리에서 임의의 두 노드가 있을 때, 두 노드의 공통 조상을 찾는 문제이다. 트리를 대상으로 하기 때문에, 어떤 노드의 부모노드는 단 하나 만 존재하게 된다. 최소 공통 조상을 찾는 방법은 아래와 같다. 모든 노드의 Height 를 먼저 계산한다. 두 노드의 높이를 맞춘다. 두 노드가 서로 같아 질 때 까지 위로 올라 간다. => 최대 root 까지 갈 수 있다. 먼저 height 를 계산해야 한다. root 노드를 선택한다. => root 노드는 임의의 아무 노드나 선택해도 된다. => 그 이유는 아래 그림 참조 root 노드로 부터 DFS 와 같은 그래프 탐색을 이용하여, 모든 노드를 방문한다. 이 과정에서 각 노드의 height 를 계산 할 수 있다. 위 ..
위상 정렬 솔루션 [1. 개요] 사이클이 없는 연결 그래프에서 위상 정렬이 가능하다. Cycle 이 있다면 위상 정렬을 할 수 없다. DFS 로 구현하는 방법과 BFS 로 구현하는 방법이 있지만, 보통 BFS 로 구현하는 편이 좀 더 쉬운 것 같음 BFS 방식의 위상 정렬 구현 패턴을 정하도록 한다. 구현 상 그 차이점을 단순하게 정리하면 아래와 같다. DFS 로 구현 DFS 이므로 재귀로 구현 가장 먼저 방문 하는 것이 제일 첫번째로 해야 할 작업이며, 가장 마지막에 방문하는 것이 마지막으로 해야 할 작업이라 볼 수 있음 방문 순서는 vector 에 push_back() 으로 저장 시, vector 를 reverse 해야 함 => 혹은 reverse iterator 를 통해. BFS 로 구현 재귀로 구현 할 필요 없음 ..
위상정렬. [1516] [1. 문제 설명] https://www.acmicpc.net/problem/1516 [2. 풀이 접근] 문제에서 다음과 같은 조건이 있다. 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 여러 개의 건물을 동시에 지을 수 있다. N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다. 1번 조건을 통해 일정한 순서를 지켜야 한다는 것을 알 수 있다. 여기에서 위상 정렬을 통해 접근 해볼 수 있음을 알 수 있다. 2번 조건은 조금 까다로울 수 있지만, 3번 조건을 통해 풀이의 힌트를 얻을 수 있다. 전체 건물대신, A 라는 어떤 하나의 건물에만 초점을 맞춰보자. A 라는 건물을 짓기 위해서는 A`, B`, C` 라는 건물을 먼저 지어야 하고, A`, B`, C` 의 건물을 짓기 위해..
최소신장트리 솔루션 [1. 개요] 최소 신장 트리는 아래와 같은 특징이 있다. 트리라는 자료구조의 특성이 그대로 있다. 모든 노드가 연결되어 있으며, 최소 weight 이다. 트리 형태이므로, N-1 개의 edge 를 갖는다. https://testkernelv2.tistory.com/471 최소 신장 트리를 구하기 위해 크루스칼 알고리즘과 프림 알고리즘 두가지가 있으며, 이 중, 한가지 알고리즘의 구현 패턴을 익히도록 한다. 크루스칼 알고리즘 구현 패턴 최소 힙이 필요하다. weight 가 작은 edge 부터 트리에 추가해본다. => 최소힙에서 pop() 한다. => 언어 별 최소 힙 사용 패턴을 알아야 한다. => https://testkernelv2.tistory.com/476 트리 추가시 Cycle 이 발생하면, 이..
최소신장트리. [1647] [1. 문제 설명] https://www.acmicpc.net/problem/1647 [2. 풀이 접근] 하나의 마을에서 집들을 연결하는 도로 => 그래프로 모델링 할 수 있다. 모든 집들이 연결 된 하나의 그래프를 두개의 그래프로 절단해야 한다. 단, 절단 된 두 마을의 유지비의 합을 최소로 해야한다. 여기서 다소 헷갈릴만한(?) 문구가 있는데, 임의의 두 집 사이에 경로가 항상 존재해야 한다. 이 문장은 하나의 마을을 두 개의 마을로 절단해야 할 때, 두 마을에는 적어도 두개의 집이 있어야 한다라고 생각이든다. 그러나, 예제의 정답을 보면 이런 형태가 아니어도 상관 없는 것 같다. 그래서 문제가 좀 단순화되어 아래와 같이 정답을 구할 수 있다. 크루스칼 알고리즘 등을 이용하여 MST 를 구성 => M..
플로이드-워셜 솔루션 [1. 개요] 일관 된 구현 패턴을 유지하도록 한다. 경유지 (k) 출발지 (u) 목적지 (v) 덧셈 간 자료형 내 오버플로우가 발생하지 않는 값을 MAX weight 로 설정하도록 한다. 경로 복원 u -> v 에서 경유지 k 가 사용 된 경우 이를 별도 배열에 저장한다. path[u][v] = k 이 후, 재귀 함수를 이용하여 u ~~~ v 경로를 구하도록 한다. => u ~~~ v => u ~~~ k ~~~ v => u ~ k 에 대한 부분 문제를 해결 => k ~ v 에 대한 부분 문제를 해결 => ... [2. 예제] https://testkernelv2.tistory.com/491 b c d e g
최단경로. [2458] [1. 문제 설명] https://www.acmicpc.net/problem/2458 [2. 풀이 접근] 두 학생의 키를 비교한 결과들을 그래프로 모델링한다. 노드: 학생 번호 간선: 두 학생 간 비교 결과 => 작은 학생에서 큰 학생으로 연결 그래프로 모델링하고 나면, 문제에서 요구하는 부분 문제 (어떤 학생이 자신의 키가 몇 번째인지 알 수 있는가?) 를 아래 질문으로 답할 수 있다. 어떤 노드에서 다른 모든 노드로 가는 경로가 존재하는가? 어떤 노드에서 다른 모든 노드와 그 관계가 형성되는가? => 직접 연결 혹은 간접적으로 연결 여기서 좀 헷갈렸던 부분은 삭선한 부분이다. 왜 다른 모든 노드로 가는 경로로 체크하면 안되냐는 것이다. 위 그림에서 4번만이 자신의 키가 몇번째 인지 알 수 있다. 4번..
최단 경로(벨만-포드) 문제 솔루션 [1. 개요] 시간 복잡도 O(VE) 모든 Edge 의 relax 를 |V| 번 만큼 반복, 마지막 |V| 번째에서 relax 가 발생한다면, 음수 사이클이 있다는 것이다. 함정 벨만-포드 수행 후 어떤 노드 u 까지 가는 경로가 존재하는가? upper[u] != INF 가 아니라고 판단하면 안된다. 그래프가 아래와 같이, 완전히 연결되지 않았다면, 시작점과 연결되지 않은 상태에서, 음수 사이클이 있다면, 적당히 큰 값 M 에 대한 어떤 연산 결과가 참이라면 u 까지 가는 경로가 있다고 판단해야함. => 이 값은 문제 조건에 따라 다름... => weight 조건이 [0, K] 이고 (음수 weight 와 별개로.. 양수 weight 에 대해서만), => 전체 edge 개수가, L 개라면, => M=KL..

티스토리툴바