본문 바로가기
  • 시 쓰는 개발자
알고리즘/코테 개념, TIP, 메모

필독!!) 백트래킹 요약

by poetDeveloper 2024. 7. 22.
반응형

백트래킹(backtracking)이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다. 모든 경우의 수를 대상으로 진행하지만, 실제로는 제한된 조건으로 경우의 수를 한정짓기 때문에, 이론적인 경우의 수보다는 더 적은 실행을 보인다. 탐색하다가 가능성이 없다면(조건에 맞지 않는다면) 바로 돌아가기 때문에 실제로 시간이 N^M만큼 걸리지는 않는다.

구현

모든 경우의 수 중에서 맞는 경우를 찾는 방법이므로, 구현은 DFS/BFS 둘 다 가능하다. 그러나 되돌아간다는 점에서 DFS와 유사해 구현도 편하다고 한다.

DFS와 차이점

그럼 백트래킹과 DFS의 차이점은 무엇일까 ??

한줄 요약 : 백트래킹은 모든 경우를 탐색하지 않는데, DFS는 모든 경우를 탐색한다.

 

1. 백트래킹

  • 제한 조건을 보고, 가능성이 없으면 시도를 그만두므로 시간 단축 효과가 있다. (모든 후보를 검사하지 않음)
  • 위 내용이 핵심이다. 백트래킹은 순열, 조합과도 유사한 맥락인데 모든 조합을 다 뽑아내고, 그 안에서 조건을 검사하는 건 메모리 초과를 유발한다. 실제로 코테 하면서 메모리 초과를 만날 일이 많지는 않은데, 예를 들어 80개 중에서 3개를 뽑는 경우의 수 이렇게 해버리면 메모리 초과가 날 수 있다는 것이다. (3^80개)

2. DFS

  • 모든 경로를 봐야해서, 경우의 수가 많으면 시간이 오래 걸려서 처리할 수가 없다.

 

주의사항

  • 백트래킹에서 가장 중요한 것은, 조건검사이다. 조건을 통해 필요 없는 경우는 쳐내고 필요한 경우의 수에 대해서만 탐색을 진행해야 시간을 아낄 수 있다.
  • 또한 검사한 요소에 대해서 다시 검사할 것인지 아닌지에 대해서 문제를 보고 잘 걸러내는 것이 중요하다.
반응형