1. 백트래킹(Backtracking)과 DFS의 차이
- 어떤 노드에서 부터 더이상 가능성이 없는 노드를 따라가지 않음으로 시도의 횟수를 줄인다.
⇒ 이 과정을 (Prunning, 가치치기) 라고 부른다.
- 백트래킹의 과정
- 상태 공간 트리의 DFS 를 실시한다.
- 각 노드가 유망한지를 점검한다.
- 만일 노드가 유망하지 않으면, 부모 노드로 돌아가서 검색을 계속한다.
- 백준의 N과 M문제가 대표적임
Uploaded by N2T
티스토리 뷰
반응형
반응형
'Algorithm > APS' 카테고리의 다른 글
| [APS] 16. 상호배타집합 파이썬(Python)으로 구현하기 (1) | 2022.10.03 |
|---|---|
| [APS] 15. Prim 알고리즘 파이썬(Python)으로 구현하기 (1) | 2022.10.03 |
| [APS] 13. 퀵 정렬(Quick Sort) (0) | 2022.10.03 |
| [APS] 12. 병합정렬(합병정렬) Merge Sort (0) | 2022.10.03 |
| [APS] 11. Python으로 조합(Combination)만들기 (0) | 2022.09.22 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 알고리즘
- JavaScript
- frontend
- 쟝고
- 사피
- APS
- django
- RDB
- BOJ
- 프로그래밍
- Algorithm
- React drei
- Python
- three.js
- React Three Fiber
- 개발자
- CSS
- SSAFY
- 리액트
- JS
- 비전공자
- react
- Vue
- 싸피
- 백준
- 파이썬
- 프레임워크
- 프론트엔드
- 코딩
- 완전탐색
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함