2-SAT (2-satisfiability)
작성중입니다!
2-satisfiability 문제, '투셋'이라고 읽습니다.
SCC 문서를 먼저 읽는 것을 추천합니다.
코드
정리
- 2-SAT 이란?
- SCC(강연결요소)의 응용 사례 중 유명한 문제
- SAT 문제 : 논리식이 주어질 때, 논리식을 참으로 만드는 논리 변수 조합이 존재하는지 찾는 문제
- 2-SAT : 2개 이상의 변수 or 연산들이 and 연산으로 결합된 형태(2-CNF, Krom formulars)의 논리식을 다루는 문제
- 2-SAT 문제는 SAT 문제와 달리 다항시간에 해결할 수 있다.
- 아이디어
- 내용
- 알고리즘
- 내용
관련 문제
- 2-SAT - 1: https://www.acmicpc.net/problem/11277
- 2-SAT - 2: https://www.acmicpc.net/problem/11278
- 2-SAT - 3: https://www.acmicpc.net/problem/11280
- 2-SAT - 4: https://www.acmicpc.net/problem/11281
- 가위바위보: https://www.acmicpc.net/problem/2207
- Perfect Election: https://www.acmicpc.net/problem/3747
- TORNJEVI: https://www.acmicpc.net/problem/3153