Algorithm 공부 #08 - 탐색(깊이 우선 탐색과 너비 우선 탐색)

Algorithm 공부 - 탐색(깊이 우선 탐색과 너비 우선 탐색) 깊이 우선 탐색(Depth-First-Search) ● 그래프 완전 탐색 기법 ● 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정한 후 최대 깊이까지 탐색을 마친 후 다른 분기로 이동 ● 노드의 개수를 V, 엣지의 개수를 E라 하면 시간 복잡도는 O(V+E) ● 단절점 찾기, 단절선 찾기, 위상 정렬, 사이클 찾기 등의 문제에 활용됨 ● 탐색 방법 1. 인접 리스트로 그래프 표현하기 + 방문 여부를 체크할 배열 만들기 + 스택에 시작 노드 삽입하기 2. 스택에서 노드를 POP한 후 그 노드와 인접 노드 삽입하기, 없다면 다음 노드로 이동 3. 스택 자료구조에 값이 없을 때까지 계속해서 반복 백준 2751번 수 정렬하기2 https..
Algorithm/알고리즘 공부 일기 2024. 3. 3. 11:14
1
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/11   »
일 월 화 수 목 금 토
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
글 보관함