Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 | 31 |
Tags
- sorting
- 파이썬
- two pointers
- geometry
- Tree
- Data Structure
- array
- 코딩테스트
- string
- 코테
- Number Theory
- Stack
- hash table
- dynamic programming
- Counting
- bit manipulation
- 자바
- Binary Search
- 구현
- implement
- Class
- Math
- greedy
- Binary Tree
- SQL
- Method
- java
- Matrix
- database
- simulation
Archives
- Today
- Total
목록Cycle (1)
코린이의 소소한 공부노트
Tarjan's algorithm
1. Problem - 방향 그래프(directed graph)에서 SCC를 찾아보자. - 강한 요소 결합(Strongly Connected Component, SCC)이란 그래프에 있는 노드 중에서 서로 도달이 가능한 노드들의 집합을 말한다. - 쉽게 말하면, 그래프 안에서 사이클을 이루는 노드의 집합이다. - 타잔 알고리즘은 정점에 대해 DFS(깊이 우선 탐색)을 실행하며 SCC를 찾는다. 2. Input 1) int[][] graph - graph[i][j]는 i번 노드에서 j번 노드로 향하는 간선을 뜻한다. 2) static int vertex - 그래프 내에 존재하는 노드의 수를 의미한다. 3. Output 1) SCC의 개수 2) 각 SCC에 속하는 노드의 번호를 출력 4. Example //..
Back-End/Algorithm
2023. 6. 14. 12:58