dh_0e

아이돌 (백준 3648번) 2-SAT 문제에 상근(1번 참가자)이가 항상 합격할 수 있는 경우가 있는지를 찾는 문제. 풀이 과정상근이가 포함된 SCC 집합을 true로 만들고 각 SCC 집합 관계가 맞는지 확인하는 방식은 너무 복잡해짐.상근이가 항상 합격해야 한다는 심사위원의 평가를 하나 만들면 된다. vec[ch(-1)].push_back(1) → (1, 1) 의 평가를 하나 추가하여 1번 참가자가 무조건 합격하게끔 만드는 식으로 한정지어줌#include#include#include#include#includeusing namespace std;stack st;vector vec[2'001];bool vi[2'001];int p[2'001];int id = 0, scc = 0;auto ch = [](i..

2-SAT - 4 (백준 11281번) 2-SAT-3 에서 식을 true로 만들 수 있는 변수들의 값을 출력하면 되는 문제. 풀이 과정2-SAT 문제에서 변수 값을 정할 때 위상 정렬(Topological Sort) 순서를 거꾸로 따라감그래프에서 A → B 라는 건, A를 결정해야 B를 알 수 있다는 뜻이며 이게 위상 정렬 순서가 된다(A가 B보다 앞에 옴).근데 만약 우리가 A를 참(True)으로 정했는데, 이게 어찌어찌 흘러가서 A ⇒ ... ⇒ ¬A 라는 모순을 만들면 식이 성립할 수 없다.이런 모순을 피하는 가장 안전한 방법은, 함의 관계의 맨 끝, 즉 종착지부터 값을 정하는 것. 종착지는 위상 정렬 순서에서 가장 나중에 오므로, 위상 정렬의 역순으로 거슬러 올라가면서 값을 결정한다. 이렇게 하..

2-SAT - 3 (백준 11280번) SCC 알고리즘 문제를 풀다가 만난 또 다른 알고리즘인 2-SAT 기본 문제이다. 처음에 태그를 보지 않고, 2-CNF 식을 그래프로 만들어보려고 하루 이상을 고민했지만 비슷하게나마 접근하는데에 그쳤다. 2-SAT 문제에 대한 설명은 아래 블로그를 보고 공부했다. 2-SAT 문제(2-Satisfiability Problem) (수정: 2019-11-16)안녕하세요. 이번에 강의할 내용은 2-SAT(2-Satisfiability)이라는 좀 생소할 수 있는 내용입니다! 이...blog.naver.com먼저 명제를 단방향 간선들로 바꿔서 그래프를 만들어준 뒤, 타잔 알고리즘으로 SCC 구현을 한다. 이후, 각 변수에 대해 자신의 not 형 변수가 같은 SCC에 들어있으면..