내 맴

백트래킹 알고리즘 (파이썬) 본문

Algorithm/개념 공부

백트래킹 알고리즘 (파이썬)

뺙사우르수 2020. 5. 7. 16:29
728x90

- 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

728x90
저작자표시 비영리 동일조건

'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
'Algorithm/개념 공부' Related Articles more