백트래킹 알고리즘이란?
해를 찾는 도중 해가 아니어서 막히게 되면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 백트래킹은 한정 조건을 가진 문제를 풀려는 전략이다. 어떤 문제를 푸는데 있어 모든 경우의 수를 시도하여 문제의 정답을 찾아나간다. 하지만 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는 것에 있어 모든 경우의 수를 탐색하는 DFS와 차이가 있다.
백트래킹 특징
- 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 더 이상 가지 않고 되돌아 가기 때문에 반복문의 횟수까지 줄일 수 있어 효율적이다.
-이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미다.
- 하지만 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 된다.
- 주로 문제 풀이에서 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 되돌아가서 다른 경우를 탐색하게 된다.
백준 예시 문제
| 15649 ~ 15666 | N과M(1) ~ N과 M(12) | https://www.acmicpc.net/problem/15649 |
| 9663 | N-Queen | https://www.acmicpc.net/problem/9663 |
| 15686 | 치킨 배달 | https://www.acmicpc.net/problem/15686 |
| 1182 | 부분수열의 합 | https://www.acmicpc.net/problem/1182 |
| 1759 | 암호 만들기 | https://www.acmicpc.net/problem/1759 |
| 6603 | 로또 | https://www.acmicpc.net/problem/6603 |
| 1941 | 소문난 칠공주 | https://www.acmicpc.net/problem/1941 |
[참고]
https://www.youtube.com/watch?v=exwk905In0U&list=PLodgw23vNd_UFQeV8GQtVHrT38VWE6iJv
https://hcr3066.tistory.com/27
알고리즘 기법[전체 탐색] - 백트래킹(Backtracking)
백트래킹(Backtracking) 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정을 말한다. -일반적으로 최적화 문제를 해결할 때
hcr3066.tistory.com
https://veggie-garden.tistory.com/24
[Python] 백트래킹 (+ DFS와 차이)
백트래킹이란? 백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그
veggie-garden.tistory.com
https://80000coding.oopy.io/85650ea5-e541-4b12-9b86-a958a99b7533
백트래킹(BackTracking)
백트래킹 이란?
80000coding.oopy.io
'코딩테스트준비 > 알고리즘' 카테고리의 다른 글
| 재귀 함수(Recursive Function) (0) | 2024.01.07 |
|---|---|
| 구현:시뮬레이션과 완전 탐색 (0) | 2023.11.05 |
| 다익스트라 알고리즘 (Dijkstra Algorithm) (0) | 2023.09.10 |
| 그리디 알고리즘(Greedy Algorithm) (0) | 2023.04.10 |
| 이분탐색(Binary Search) (0) | 2023.03.31 |
