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기에 존재하는 금액의 총 합, 레스토랑 존재 여부를 다룰 수 있고 위 문제는 출발..

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을..

Approach Inversion counting임을 파악하고 병합정렬을 활용해서 풀어줄 수도 있다. 잘 생각해보면, B의 i번째 위치에 놓인 점에 의해 교차점이 발생하는 횟수는 자기보다 먼저 대응된 것 중에 자신보다 큰 것의 개수와 같다. 이렇게 되면, i번째 위치에 놓인 점의 이동 횟수를 구하는 시점에 자신보다 숫자가 큰 것의 개수만 구한 것과 B의 i ~ inf번째 위치에 놓인 것 중 대응된 것의 개수를 구하는 것이 동치가 된다. 예를 들어, a의 i번쨰 수가 B에 대응되는 index가 $b_{a_i}$라고 할 떄, 결과적으로 해당 선에 의해 교차점이 생기는 상황은 $b_{a_i}$부터 50000(inf) 위치 사이에 놓인 대응된 점의 개수와 동치이다. https://viyoung.tistory.c..