내 맴
백트래킹 알고리즘 (파이썬) 본문
- Backtracking Algorithm
✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법
✔ 모든 경우의 수를 전부 고려한다 ( 브루트 포스 Algorithm과 유사)
✔ 최적화(optimization) 문제와 결정(decision) 문제 ( yes or no question) 를 해결할수있다.
✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여
유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다
- 순서
1. State Space Tree에서 DFS를 실시한다
2. 각 Node가 promising한 지 점검
3.
If Node가 promising한 경우 → 자손 Node 탐색
Else non promising한 경우 → 부모 Node로 돌아가서 탐색 계속한다
- DFS (깊이 우선 탐색)이란?
https://luz0911.tistory.com/97?category=765468
DFS ( Depth First Search, 깊이 우선 탐색 ) python으로 구현하기
- DFS ( Depth First Search ) : Root Node 방문 후, 그 Node의 후손들을 왼쪽에서 오른쪽으로 Search - 구현 방법 1. GRAPH 표현해주기 ( python ) : Dictionary 과 List 자료형을 사용해준다 1개의 Node와 연결..
luz0911.tistory.com
- 시간 복잡도
정확하게 계산할 수 있는 방법은 없다. 그러나 promising하지 않은 Node들을 탐색하지 않으므로 브루트 포스 Algorithm으로 해결하는 것 보다 좀 더 빠르다.
- N-Queens ( Backtracking Algorithm의 대표 문제 )
Baekjoon 사이트에 있는 N-queens문제를 풀어놓은 포스팅이다. 설명도 있으니 여기서 봐주시길 바랍니다,,,
https://luz0911.tistory.com/130?category=765467
[ BAEKJOON ] No. 9663 N-Queen
문제 ) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는..
luz0911.tistory.com
'Algorithm > 개념 공부' 카테고리의 다른 글
| Greedy Algorithm - Fractional Knapsack Problem (0) | 2020.04.09 |
|---|---|
| BFS ( Breath First Search, 너비 우선 탐색 ) python으로 구현하기 (0) | 2020.03.30 |
| DFS ( Depth First Search, 깊이 우선 탐색 ) python으로 구현하기 (0) | 2020.03.27 |
| Quick Sort (퀵 정렬) python으로 구현하기 (1) | 2020.03.24 |
| Bubble Sort (버블 정렬) python으로 구현하기 (0) | 2020.03.17 |
