| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- pytorch
- 알고리즘
- NEXT
- back propagation
- 가끔은_말로
- 크루스칼
- c++
- dropout
- 백트래킹
- 조합론
- Overfitting
- 이분 탐색
- dfs
- BFS
- 회고록
- DP
- 플로이드 와샬
- 세그먼트 트리
- 2023
- 너비 우선 탐색
- 분할 정복
- 미래는_현재와_과거로
- 우선 순위 큐
- 자바스크립트
- 문자열
- lazy propagation
- 가끔은 말로
- tensorflow
- object detection
- 다익스트라
- Today
- Total
목록SCC (2)
Doby's Lab
2-SAT 연구일지
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..
SCC, Tarjan Algorithm 연구 일지
SCC 알고리즘에는 Kosaraju Algorithm, Tarjan Algorithm이 있습니다. Kosaraju 알고리즘이 구현에는 편하지만 타잔 알고리즘이 SCC 노드끼리의 위상 정렬을 알 수 있기 때문에 공부하였습니다. 제일 최신화된 연구일지는 22.04.23 연구일지입니다. 이를 참고하여 읽어주시길 바랍니다. 22.04.22 연구일지 Time Complexity >> O(|V| + |E|) 동작 원리 +DFS와 Stack에 대한 사전 지식이 있어야 합니다. 1. 인접 배열을 이용한 DFS를 돌립니다. 2. DFS를 돌리면서 스택에 해당 노드를 담습니다. 2.1 next 노드의 sccOrder가 정해져 있지 않다면 next 노드를 가지고서 DFS를 돌리고, 제일 작은 minOrder 갱신합니다. 2..