dh_0e

풀이 과정 SCC 변형 문제로 타잔 알고리즘으로 해결하였다.p배열을 구한 뒤, SCC 간 위상 관계를 생각해보면 사이클이 없는 트리처럼 생각할 수 있다. 이 트리의 root 개수를 구해주면 된다.타잔 알고리즘으로 각 연결 요소 집합(p배열) 구한다.각 vertex의 edge를 탐색하여 자신이 넘어뜨릴 수 있는 다른 도미노의 집합(B)이 자신의 집합(A)과 다르면 B는 다른 집합에 의해 넘어지는(root가 아닌) 도미노 집합임을 저장한다. (if (p[i] != p[next])vi_2[p[next]] = 1;)집합에 존재하는 모든 vertex가 다른 도미노에 의해 넘어지지 않는 집합(root)의 개수를 구한다. #include#include#include#include#includeusing namespa..

Strongly Connected Component(강한 연결 요소) 알고리즘 기본 문제. 모르고 풀이를 떠올렸을 때, dfs로 비슷하게까지는 생각했는데, 알아보니 타잔 알고리즘이나 코사라주 알고리즘을 사용해야 했고, 비교적 간단한 타잔 알고리즘을 사용해 풀었다. id를 사용해서 깊이만큼 초기값을 가지는 것, 다음 vertex의 id값을 받아서 내 parent 값보다 작으면 갱신한다는 부분이 킥이었다.아래 블로그에 두 알고리즘을 자세히 설명되어있다. SCC - 강한 연결 요소 찾기강한 연결 요소 (SCC, Strongly Connected Component) 란, 유향 그래프에서 정점의 부분집합이 부분집합 내의 다른 모든 정점에 대해 방문 가능한 경우를 말한다. 쉽게 말해 사이클이 생기는 그룹을 엮으re..

다익스트라로 최단 거리를 구하면서 경로를 역추적해서 최단 거리의 간선들을 모두 삭제한 뒤, 다시 다익스트라로 두 번째 최단 거리를 구하는 문제. 구현과 반례 찾는데에 꽤나 어려움을 느꼈고, 결과도 틀렸습니다, 시간 초과가 아닌 메모리 초과가 나와서 콜 스택이 터진건지 내가 모르는 메모리 관리 방법이 있는건지 디버깅 하다가 결국엔 로직 오류를 찾아서 해결했다.. 풀이 과정 다익스트라로 최단 거리를 구하면서 before_node에 해당 node로 최단 거리만에 갈 수 있는 node들을 저장해준다. 이때, 새로운 최단 거리가 나오면 before_node를 clear한 뒤, 다시 node를 저장한다. 최단 거리로 도착할 수 있는 node가 중복으로 나온다면 해당 node 또한 push_back해준다.도착 nod..

LCA 2(백준 11438번)처럼 희소 배열을 이용한 최소 공통 조상(Binary Lifting) 알고리즘을 활용한 문제. [PS] LCA 2 / C++ (백준 11438번)희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfdh-0e.tistory.com구현이 꽤 복잡하지만 설계를 잘 하고, LCA를 적절하게 구현하면 쉽게 풀 수 있다. #include#include#includeusing namespace std;vector> vec[100001];int depth[100001], vi[100001];pair> p..

희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfs()함수로 트리를 만들며 각 node들의 parent 정보를 희소 배열에 저장하는데 이때, 희소 배열을 2차원으로 parent[i][j]=i번째 node에서 $2^j$번째 부모를 저장하는 방식으로 만들어준다. N 2. depth 배열을 만들어 각 node들의 깊이 또한 저장해준다. 주요 식은 다음과 같다.parent[i][j]=parent[parent[i][j-1]][j-1]; 3. 다음 입력받은 두 노드의 깊이를 맞춰준다. 이때, 2의 거듭제곱으로 큰 값부터 작은 ..

읽자마자 세그먼트 트리가 떠올랐던 문제. 값이 아닌 인덱스를 출력하는 문제이기 때문에 세그먼트 트리를 적절히 변형하여 풀어야 한다. 풀이 과정 값과 인덱스 모두 저장해야 하기 때문에 tree[] 배열을 pair로 선언해주고, 모든 함수 또한 return 값을 pair로 하여 세그먼트 트리를 구현해주면 된다. pair init(int start, int end, int node): 세그먼트 트리를 만드는 함수로 기존 세그먼트 트리 로직에 최솟값과 그 인덱스를 pair로 가져오게끔 수정하면 된다. 이때, 최솟값이 같을 경우 인덱스가 작은 것을 출력하기 때문에 조건문은 if(left_node.firstright_node.first)tree[node]=left; 가 된다. pair update(int start..