🎨 배경

개인적으론, 코딩테스트에 많이 나오지 않는 개념인 것 같습니다. 그만큼 어렵지 않은 개념이기도 해서 그런가 싶습니다. 하지만 꼭 소홀이 하게 되면 까먹게 되는데, 쉬운 만큼 내가 까먹었다고 인지할 때면 충격이 겁나게 큽니다...('머리가 어떻게 됐나'라고 느낄 정도)

더 이상 그 충격을 받고 싶지 않아 이렇게 글을 써봅니다.

💡 개념

백트레킹(Backtracking)은 문제를 해결하기 위해 모든 가능한 경우를 시도하는 알고리즘입니다. 재귀 호출을 사용하여 현재 상태에서 가능한 모든 다음 상태를 탐색하고, 제약 조건을 만족하지 않는 경우 이전 상태로 되돌아가 다시 탐색합니다.

1. 현재 상태에서 가능한 모든 다음 상태를 탐색
2. 다음 상태가 제약 조건을 만족하는지 확인
   2-1. 만족한다면 탐색 종료
   2-2. 만족하지 않는다면 이전 상태로 되돌아간다.
3. 모든 상태를 다 확인할 때까지 위를 반복합니다.

⏱️ 시간복잡도
백트래킹 알고리즘의 시간 복잡도는 주로 문제의 조건에 따라 달라지지만, 이 문제의 경우, 선택할 수 있는 숫자가 N개이고, 수열의 길이가 M이므로 총 경우의 수는 O(N^M)입니다. 따라서 최악의 경우에는 지수 시간이 소요될 수 있습니다.

😀 장점:

• 간단하고 구현하기 쉽다.
• 다양한 문제에 적용할 수 있다.
• 모든 경우의 수를 탐색하기 때문에 최적의 해를 찾을 수 있다.

🙁 단점:

• 모든 경우의 수를 탐색하기 때문에 시간 복잡도가 크다.
• 메모리의 사용량이 많다.

🤔 생각해볼것:

• DFS하고 많이 달라보이지 않습니다.

  DFS가 재귀를 통해 구현된다는 점에서 비슷하지만, 백트래킹의 경우 현재 가는 길이 더 이상의 해가 아니라고 판단되면 돌아옵니다.

• 이 문제를 풀면서 시간복잡도를 해결하는게 관건인 것 같습니다.
• itertools을 사용하여 문제를 좀 더 간결하게 풀 수 있어, 코딩테스트 문제에서 백트래킹 하나만을 두고 문제로 내지 않을 것 같습니다.
  
  ⬆️ 출처: 파이썬 공식 문서

📝 대표적인 문제
https://www.acmicpc.net/problem/9663