반응형
백트래킹(backtracking)이란?
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다. 모든 경우의 수를 대상으로 진행하지만, 실제로는 제한된 조건으로 경우의 수를 한정짓기 때문에, 이론적인 경우의 수보다는 더 적은 실행을 보인다. 탐색하다가 가능성이 없다면(조건에 맞지 않는다면) 바로 돌아가기 때문에 실제로 시간이 N^M만큼 걸리지는 않는다.
구현
모든 경우의 수 중에서 맞는 경우를 찾는 방법이므로, 구현은 DFS/BFS 둘 다 가능하다. 그러나 되돌아간다는 점에서 DFS와 유사해 구현도 편하다고 한다.
DFS와 차이점
그럼 백트래킹과 DFS의 차이점은 무엇일까 ??
한줄 요약 : 백트래킹은 모든 경우를 탐색하지 않는데, DFS는 모든 경우를 탐색한다.
1. 백트래킹
- 제한 조건을 보고, 가능성이 없으면 시도를 그만두므로 시간 단축 효과가 있다. (모든 후보를 검사하지 않음)
- 위 내용이 핵심이다. 백트래킹은 순열, 조합과도 유사한 맥락인데 모든 조합을 다 뽑아내고, 그 안에서 조건을 검사하는 건 메모리 초과를 유발한다. 실제로 코테 하면서 메모리 초과를 만날 일이 많지는 않은데, 예를 들어 80개 중에서 3개를 뽑는 경우의 수 이렇게 해버리면 메모리 초과가 날 수 있다는 것이다. (3^80개)
2. DFS
- 모든 경로를 봐야해서, 경우의 수가 많으면 시간이 오래 걸려서 처리할 수가 없다.
주의사항
- 백트래킹에서 가장 중요한 것은, 조건검사이다. 조건을 통해 필요 없는 경우는 쳐내고 필요한 경우의 수에 대해서만 탐색을 진행해야 시간을 아낄 수 있다.
- 또한 검사한 요소에 대해서 다시 검사할 것인지 아닌지에 대해서 문제를 보고 잘 걸러내는 것이 중요하다.
반응형
'알고리즘 > 코테 개념, TIP, 메모' 카테고리의 다른 글
필독!!) DP (Dynamic Programming) (0) | 2024.07.29 |
---|---|
이진탐색 요약 (0) | 2024.07.29 |
문제풀이 TIP (Test Case) (1) | 2024.07.22 |
필독!!) DFS / BFS 정리 + 인접행렬, 인접리스트 (2) | 2024.07.15 |
시간복잡도 요약 (0) | 2024.07.15 |