알고리즘 공부방

2-SAT 문제는 다음과 같다. (a or b) 꼴의 식 여러 개를 and 연산으로 연립한 것이다. 이때 각 a, b, c 변수는 true, false 를 값으로 하는 변수이다. 각 변수에는 not 을 붙일 수 있다. 이 문제는 변수들 간의 방향 그래프로 모델링 한 후, SCC를 사용하여 해를 구할 수 있다. 첫 번째로, 각 항의 (a or b)는 모두 true 가 되어야 한다. 이제 하나의 항만 생각해 보자. (a or b) 가 성립하기 위해서는 a가 false이면 b가 true / b가 false이면 a가 true 여야 한다. 이를 명제로 표현하면 !a -> b , !b -> a 이다. 이 명제들이 모두 성립한다면 (a or b) 가 성립한다. 이제, 모든 항들을 2개의 명제로 바꾸었다. 항의 개수가..