반응형
- 백트래킹(BackTraking) 기법은 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서
다시 해를 찾아 가는 기법이다. - 백트래킹 기법은 최적화 (Optimization) 문제와 결정 (decision) 문제를 해결할 수 있다.
- 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제
- 미로찾기
- n-Queen
- Map coloring
- 부분 집합의 합(Subset Sum) 등 - 백트래킹 vs DFS
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라
가지 않음으로써 시도의 횟수를 줄임 (Prunning 가지치기)
- 깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단.
- 깊이우선탐색을 가하기에는 경우의 수가 너무나 많음. 즉, N! 가지의 경우의 수를 가진 문제에
대해 깊이우선탐색을 가하면 당연히 처리 불가능한 문제.
- 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는
여전히 지수함수 시간(Exponential Time)을 요하므로 처리 불가능
<N-Queen>
https://www.acmicpc.net/problem/3344
3344번: N-Queen
문제 8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다. 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다. 이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다. N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇 가지가 있을까? 이 문제는 N>3인 경우에 경우의 수가 적어도 1개 라는 것이 증명
www.acmicpc.net
반응형
'1. 알고리즘 이론 > 4. 백트래킹, DP' 카테고리의 다른 글
| DP(Dynamic Programming) (0) | 2020.03.01 |
|---|