Doby's Lab

2-SAT에 대하여 공부해봅시다. 2-Satisfiability의 약자로 boolean variable들의 충족 가능성을 묻는 문제입니다. BOJ 2-SAT 3(11280), 2-SAT 4(11281)를 기반으로 연구합니다. 공부하는 데에 도움이 된 블로그 링크들 1(https://blog.naver.com/kks227/220803009418) 2(https://everenew.tistory.com/140) 22.04.03 연구일지 CNF(Conjunctive Normal Form) 식을 true가 될 수 있게 boolean variable의 조합이 있는지 조합이 있다면 어떤 조합으로 이루어지는지 알아내는 알고리즘입니다. 2-SAT에서 CNF는 2-CNF로 이는 한 Clause당 boolean varia..

https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net Solved By: 2-SAT, SCC 처음으로 풀어본 2-SAT 문제였습니다. 2-SAT에 대해서는 주말에 간단하게 정리할 예정이며 직전 포스팅에 공부했던 포스팅들의 링크를 걸어두었습니다. 변수와 NOT 변수에 대해서 {2 * i, 2 * i + 1}로 각각 모델링하여 SCC를 Tarjan Algorithm을 통해 만들었습니다. 각..