| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 |
- tensorflow
- back propagation
- DP
- lazy propagation
- dfs
- 플로이드 와샬
- 알고리즘
- 조합론
- pytorch
- 이분 탐색
- 자바스크립트
- 우선 순위 큐
- 너비 우선 탐색
- 다익스트라
- 문자열
- 회고록
- BFS
- 가끔은 말로
- dropout
- c++
- NEXT
- object detection
- 크루스칼
- 가끔은_말로
- Overfitting
- 세그먼트 트리
- 미래는_현재와_과거로
- 2023
- 백트래킹
- 분할 정복
- Today
- Total
목록2-SAT (2)
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을 통해 만들었습니다. 각..