[ 알고리즘 ] 백트래킹(BackTracking)

백트래킹 이란?

해결책으로 이어질 가능성이 있는 모든 경로를 탐색하면서, 각 단계에서 그 경로가 목표를 달성할 수 없다고 판단되면 이전 단계로 돌아가 다른 경로를 시도하는 방법입니다.

 

백트래킹의 필요성 

• 다양한 문제(특히 최적화 문제와 결정 문제)에서 최적의 해를 찾거나 해가 존재하는지를 확인할 때 사용.

---

백트래킹의 원리

 

• 백트래킹의 기본 개념
  • 선택: 가능한 옵션 중 하나를 선택.
  • 제약: 선택이 문제의 조건을 만족하는지 검사.
  • 목표: 해결책에 도달했는지 확인.

백트래킹과 다른 알고리즘과의 비교

- 브루트 포스 알고리즘

브루트 포스(Brute Force)는 문제의 모든 가능한 경우를 차례대로 시도해보며 정답을 찾는 방법입니다.

가장 단순하고 직관적인 접근 방식이지만, 가능한 모든 경우를 검토해야 하므로 문제의 크기가 커질수록 계산 시간이 기하급수적으로 증가하는 단점이 있습니다

예제 코드: N-퀸 문제의 브루트 포스 접근 .

NO

 

이 코드는 모든 가능한 퀸의 배치를 생성하고 각 배치가 유효한지 검사합니다.

---

- 백트래킹 알고리즘

백트래킹은 브루트 포스의 기본적인 아이디어를 사용하지만, 모든 경우를 맹목적으로 검토하지 않습니다.

대신, 현재의 선택이 미래에 유효한 해결책으로 이어질 수 없다고 판단되면, 그 선택을 취소(Backtrack)하고 다른 선택을 시도합니다. 이 접근 방식은 많은 경우의 수를 미리 배제하여 계산 효율을 크게 향상시킵니다.

예제 코드: N-퀸 문제의 백트래킹 접근

NO

이 코드는 각 행에 퀸을 하나씩 배치하면서, 같은 열이나 대각선에 다른 퀸이 없는지 검사합니다.

유효하지 않은 배치는 즉시 중단하고 다른 옵션을 시도합니다.

 

비교 및 효율성 강조

• 시간 복잡도:
  • 브루트 포스는 모든 경우를 검토하므로 시간 복잡도가 매우 높습니다.
    
  • 백트래킹은 유효하지 않은 경우를 조기에 제거하여 훨씬 빠르게 해답에 도달할 수 있습니다.
• 공간 복잡도:
  • 백트래킹은 실행 중에 상태를 변경하고 되돌릴 수 있어, 추가적인 공간을 적게 사용합니다.
• 적용 가능성:
  • 백트래킹은 조합 최적화 문제와 같이 가능한 해가 수많은 경우에 특히 유리합니다.

---

백트래킹은 이러한 점에서 브루트 포스보다 효율적이며, 실제 문제 해결에 더 자주 사용되는 것 같습니다.