| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- hilt
- onLayout
- recyclerview
- sqlite
- CollapsingToolbarLayout
- 백준
- Android
- room
- 코틀린
- Algorithm
- lifecycle
- View
- notification
- onMeasure
- Behavior
- activity
- 안드로이드
- 알림
- Coroutine
- DataBinding
- 알고리즘
- HTTP
- ViewModel
- kotlin
- LiveData
- AppBarLayout
- CoordinatorLayout
- Navigation
- CustomView
- BOJ
- Today
- Total
목록Strongly Connected Component (2)
개발일지
Algorithm in A..Z - SSC(Tarjans)
개념 강한 연결 요소(Strongly Connected Component)는 방향 그래프에서 서로 왕복할 수 있는 가장 큰 정접들의 집합입니다. 작동원리 1. DFS를 하면서 방문하는 순서대로 값을 할당하고, 스택에 넣는다. 2. DFS를 하면서 방문하지 않는 정점이나, 방문했지만 아직 SCC에 속하지 않은 정점들에게 할당된 값 중 가장 작은 값을 리턴한다. 3. 자신에게 할당된 값과 리턴값이 같으면 SCC이다. * 타잔 알고리즘은 스택을 사용하여 SCC를 추가하기 때문에 위상정렬이 된다. 시간복잡도 1. DFS할 때 O(V + E) O(V + E) 문제 2150 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Conne..
Algorithm in A..Z - SCC(Kosaraju)
개념 강한 연결 요소(Strongly Connected Component)는 방향 그래프에서 서로 왕복할 수 있는 가장 큰 정접들의 집합입니다. 작동원리 1. 정방향 그래프로 DFS를 하면서 탐색이 끝나는 순으로 스택에 넣는다. 2. 스택에서 하나씩 꺼내면서 역방향 그래프로 DFS를 진행한다. 3. 역방향으로 DFS를 진행하면서 방문하는 정점들이 SCC이다. 시간복잡도 1. 정방향 그래프로 DFS -> O(V + E) 2. 역방향 그래프로 DFS -> O(V + E) O(V + E) 문제 2150 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000..