핵심 요약
- 해를 찾는 도중 해가 아니어서 막힐경우, 되돌아가서 다시 해를 찾아가는 기법
- 시간 복잡도를 감소시킬 수 있는 기법
- 최적화 문제, 결정 문제 등을 풀 때 활용한다.
- 유망성 판단(promising)이 중요하다!
사용처
DFS 등
대표 문제
백준 9663, N-Queen 문제.
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
'Algorithm' 카테고리의 다른 글
| [C++] BFS(Breadth-First Search) (0) | 2023.10.03 |
|---|---|
| [C++] DFS(Depth-First Search) (0) | 2023.10.03 |
| 분할 정복(Divide & Conquer) (0) | 2023.10.02 |
| [C++] 비트마스킹(Bitmasking) (1) | 2023.10.02 |
| DP(Dynamic Programming) (1) | 2023.10.02 |