개발일지

https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 접근 Tarjan 알고리즘으로 SCC를 구현하면 특성상 하위의 SCC가 먼저 결정된다. 그렇기 때문에 x < ¬x 를 만족하면 x가 참이된다. 상근이가 합격하려면 ¬x가 False면 합격이기 때문에 그래프를 구현할 때 역방향으로 그래프를 구현하여 ¬x가 False가 될 수 있는지 확인한다. (명제의 대우는 동치이기 때문에 가능하다.) 코드 #include using namespace std; constexpr int NONE = -1; int..

개념 충족 가능성 문제 중 하나로써 아래와 같은 형태를 2-SAT 문제라 한다. * 충족 가능성 문제 : Boolean으로 이루어진 식이 있을 때 해당 식이 True인 경우를 찾는 문제 f=(¬x1∨x2)∧(¬x2∨x3)∧(x1∨x3)∧(x3∨x2) 인 경우에 f를 true로 만드는 경우 ¬ : NOT ∨ : OR ∧ : AND 괄호 안의 OR 연산으로 이루어진 것을 절(Clause)이라고 표현하고 AND와 절로 이루어진 식을 CNF(Conjunctive Normal Form)라고 한다. 각 절의 변수의 개수가 2개면 2-SAT이라 하고 N개면 N-SAT이라고 한다. 2개 같은 경우 SCC 알고리즘을 사용하여 쉽게 해결할 수 있지만, 3개 이상의 SAT 문제에서는 NP-Hard 문제이다. 작동원리 1. ..

개념 강한 연결 요소(Strongly Connected Component)는 방향 그래프에서 서로 왕복할 수 있는 가장 큰 정접들의 집합입니다. 작동원리 1. DFS를 하면서 방문하는 순서대로 값을 할당하고, 스택에 넣는다. 2. DFS를 하면서 방문하지 않는 정점이나, 방문했지만 아직 SCC에 속하지 않은 정점들에게 할당된 값 중 가장 작은 값을 리턴한다. 3. 자신에게 할당된 값과 리턴값이 같으면 SCC이다. * 타잔 알고리즘은 스택을 사용하여 SCC를 추가하기 때문에 위상정렬이 된다. 시간복잡도 1. DFS할 때 O(V + E) O(V + E) 문제 2150 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Conne..