Approach 잘 생각해보면 SCC 안에 있는 것들은 사실상 하나의 도미노로 취급해도 된다. (SCC에 속한 친구들은 그 중 1개만 넘어뜨리면 어차피 다 넘어가므로) 즉, SCC단위로 보았을 때, indegree가 없는 SCC들의 개수를 출력해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tuple; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; vector edge[100001]; stack s; int scc_num; int idx[..

Approach 전형적인 SCC Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tuple; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; vector edge[10001]; int idx[10001]; int idx_low[10001]; bool in_stack[10001]; bool scc_check[10001]; int scc_value[10001]; int scc_num = 0; stack s; int cur_time = 0; void tarja..

Approach 일단, 그리디한 관점으로 보면 가능한 ATM 기기를 최대한 많이 거쳐가는 것이 유리하다. 하지만, 모든 ATM 기기를 전부 다 갈 수 없는데, 그 이유는 Directed graph이기 때문이다. 그런데, SCC에서는 위 문제가 완전히 해결된다. SCC의 특성이 해당 컴포넌트 내부에서 임의의 두 노드를 잡았을 때 반드시 해당 두 노드를 연결하는 path가 존재한다는 것이다. 즉, SCC 내부에 존재하는 ATM은 전부 다 방문할 수 있게 된다. 또한 추가적으로 SCC를 만들게 되면 장점이 DAG가 만들어진다는 것이다. 이를 이용하여 Topological sorting을 할 수 있게 된다. 즉, SCC단위로 ATM기에 존재하는 금액의 총 합, 레스토랑 존재 여부를 다룰 수 있고 위 문제는 출발..

Introduction Tarjan's algorithm is a popular algorithm for finding strongly connected components (SCCs) in a directed graph. A strongly connected component is a subset of vertices in a directed graph where every vertex is reachable from every other vertex in the subset. In other words, the vertices in an SCC are strongly connected to each other.The algorithm works by performing a depth-first sea..

Approach 현대대수나 집합론에서 다루는 것처럼, 연산 자체를 잘 정의해주면 된다. 궁극적으로 이 문제가 naive하게 풀기 어려운 이유는 본질적으로 연산을 함에 있어 덧셈과 곱셈 중 곱셈의 우선순위가 더 높기 때문이다. 잘 생각해보면 본질적으로 더하고 곱하는 연산은 다음과 같이 정의할 수 있다. f : R X R X R |-> R 이다. 즉 예를 들어서 기존에 가지고 있는 값을 x, 곱하는 수를 y, 더하는 수를 z라고 하면 x * y + z로 나타낼 수 있는데, 궁극적으로 3개의 실수값을 1개의 실수값으로 대응시키는 함수를 통과시켰다고 할 수 있다. 이를 좀 단순하게 표현하면 $f_{a, b}(c)$ 이런 형식으로 표현할 수 있을 것이다. 그렇다면, 연산을 여러번 적용한다는 의미는 합성함수를 정의..

Approach https://viyoung.tistory.com/406 [백준 2820번] [Lazy propagation / Euler Tour] 자동차 공장 Approach https://viyoung.tistory.com/400 [백준 14268번] [오일러 투어 테크닉 / Lazy propagation] 회사 문화 2 Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다.. viyoung.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tu..

Approach https://viyoung.tistory.com/400 [백준 14268번] [오일러 투어 테크닉 / Lazy propagation] 회사 문화 2 Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다. 좀만 생각해보면, 직급 관계는 트리 구조를 활용하여서 표현할 수 있고 해당 노드를 기준으로 아래 viyoung.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tuple; int move_x[4] = {-1, 1, 0, 0}; in..

Approach 구간에 대한 정보를 변경하는 쿼리와 구간에 대한 질의를 하고 있는 쿼리를 보내고 있는 상황이므로, Lazy propagation임은 쉽게 파악할 수 있었을 것이다. 그러면, lazy를 어떻게 정의할 것인지를 파악하는 것이 중요할 것이다. 아이디어 자체는 이 문제와 상당히 유사하다. https://viyoung.tistory.com/399 [백준 12844번] [Lazy propagation] XOR Approach 문제를 보자마자 구간에 대한 정보를 계속해서 업데이트 하는 상황이므로 Lazy propagation 문제임은 직관적으로 잘 파악했을 것이다. 하지만, 기본적인 합 세그와 달리 XOR 연산을 처리하는 viyoung.tistory.com 이 문제도 XOR의 성질을 활용하여 XOR을..