깊이 우선 탐색(DFS) 란 그래프를 탐색하는 방법 중 하나이다. 그림 1을 예시로 들어보자. DFS는 이름 그대로 깊이를 우선으로 탐색하는 방법인데 탐색을 시작할 정점을 A라고 정해보자. A에서 시작했을 때, A와 연결되어 있는 정점은 B, C이다. 이때 DFS는 자신과 연결되어 있는 정점을 먼저 탐색한다. 일단 B부터 탐색해 보겠다. 여기서 초록색은 이미 탐색한 정점, 파란색은 현재 도달한 정점이다. 여기서 B는 D와 E 를 갈 수 있다. A 도 갈 수 있지만 이미 탐색을 했기 때문에 D 와 E 중 하나를 탐색해 준다. 이번엔 D에서 탐색할 수 있는 정점을 보면 H밖에 없다. 그러므로 H를 탐색해 준다. H에 도달했을 때, H에서 갈 수 있는 정점은 E다. 만약 이 그래프에 방향이 있다면, 방향에 따..
그래프(Graph) 그래프란 정점과 간선으로 이루어진 집합을 말한다. 이런 이미지가 있다고 할 때 숫자가 쓰여있는 원을 정점 정점 사이를 잇는 선을 간선 이라고 한다. 이때 간선은 두 정점 사이 여러 개 있을 수 있으며, 방향이 존재하거나 가중치가 존재하는 등 여러 형태가 있으며, 이를 이용한 다양한 그래프가 존재한다. 트리(Tree) 트리란 그래프의 종류 중 하나로 나무처럼 생겼다고 해서 붙여진 그래프의 하위분류이다. 트리는 그래프와 비슷하게 생겼지만 방향을 제외했을 때, 사이클이 존재하면 안 된다. 그림 1은 그래프는 될 수 있지만 2-3-4-5의 사이클이 존재하기 때문에 트리일 수 없다. 그림 2는 사이클이 존재하지 않기 때문에 그래프와 트리 모두 해당된다. 또 그래프는 다른 정점들과 떨어진 정점들..
- Total
- Today
- Yesterday
- KOI
- 그래프 이론
- 개발
- 다이나믹 프로그래밍
- 트리에서의 다이나믹 프로그래밍
- 이분 탐색
- 알고리즘
- 잡봇
- 최소 스패닝 트리
- 구현
- Python
- 누적 합
- 그리디 알고리즘
- A Dance of Fire and Ice
- 이분매칭
- 느리게 갱신되는 세그먼트 트리
- 세그먼트 트리
- discord bot
- 수학
- 깊이 우선 탐색
- 선분 교차 판정
- 그래프 탐색
- 완전 탐색
- 트리
- 자료구조
- codeforces
- BOJ
- C++
- 자료 구조
- 정렬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |