backtracking1 2-SAT References Algorithms (Sanjoy Dasgupta) Contents Backtracking 2-SAT를 그래프 문제로 변환 백준 11277번, 11278번, 11280번, 11281번 이번 포스팅에서는 아래의 포스팅에서 언급했었던 2-SAT 문제에 대해서 살펴볼 예정입니다. NP-Complete Problems (1) NP-Complete Problems (2) 포스팅에서 2-SAT를 그래프로 변환한 다음 SCC를 찾음으로써 다항 시간에 해결할 수 있다고 했습니다. 하지만, 그 전에 먼저 백트래킹 기법을 이용하여 SAT 문제를 푸는 방법에 대해서 살펴보겠습니다. Backtracking 백트래킹은 해의 일부분만을 보고 이 해가 답이 될 수 없다는 것을 판단할 수 있는 경우가 많다는 관찰.. 2022. 4. 28. 이전 1 다음
