[Algorithm] 구현 - 완전 탐색(Brute Force), 백트래킹

구현이란

• 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 완전 탐색: 모든 경우의 수를 탐색하며 다 계산하는 해결 방법
• 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

구현 문제 접근법

• 사소한 입력 조건 등을 문제에서 명시
• 문제 길이가 긴 편

---

완전 탐색

완전 탐색 문제의 조건

• 경우마다 따질 게 명확
• 특정 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야
• 경우의 수가 모두 탐색할 수 있을 만큼 적음
  • 시간복잡도를 생각하지 않으면 완전탐색으로 모든 문제를 풀 수 있으므로, 처음에 완전탐색 풀이를 생각한 후 차츰 최적화하는 방식도 꽤 많은 문제에서 유용함
  • 모든 경우를 탐색하는 풀이를 생각해 봤는데 N(입력)제한이 매우 작다면 완전 탐색을 의심

완전 탐색 문제를 푸는 법

• 모든 경우(상태)를 만들 수 있는 방법 생각
• 각각의 경우가 문제의 조건을 만족하는지 체크
  • 각각의 경우를 어떻게 확인할 것인지,
    • 보통 각각의 경우를 나타내는 무언가를 인수로 받아서 그 경우에 대한 테스트를 진행하는 함수를 따로 작성
  • 어떻게 가능한 모든 경우를 다 따질 것인지 생각해야 하는 문제 존재
• 문제에 따라 모든 경우를 따질 필요가 없거나 각 경우에 대해 체크할 조건이 없는 등의 상황도 존재

---

백트래킹

• 재귀를 이용한 완전 탐색
  • 문제에서 나올 수 있는 ‘경우'를 하나의 ‘상태’로 보는 관점
  • 현재 상태에서 전이될 수 있는 다음 상태들을 재귀적으로 탐색하다가 특정 조건을 만족하면 문제에서 따져야 하는 무언가가 됨
    • 현재 상태에서 전이될 수 있는 다음 상태?
      • n개 숫자 중 서로 다른 k개를 고르는 경우
      • i번째 숫자를 검토중일 때, 아직 k개를 다 고른 상태가 아니라면 이전 상태에 더해 i번째 숫자를 고르는 상태와 고르지 않는 상태가 존재
      • 재귀에 대한 이해 필요
• 백트래킹의 기본적인 풀이법
  1. 초기 상태가 무엇인가
  2. 거기서 재귀적으로 전이될 수 있는 상태가 무엇인가
  3. 생성하고 있는 상태가 특정 사전 조건을 만족하게 된 경우 문제에서 따져야 하는 상태가 되는지 고민
     1. ex) n개 중 m개를 고른 수열들에 대해서만 무언가 따져야 하는 문제의 경우, m개를 고르지 않은 상태는 따지면 안 됨.) 재귀의 base case같은 것
  4. 생성된 상태를 어떻게 보관하고 어떻게 문제의 조건에 대해 따져 줄지 고민
  5. 생성된 상태에서 어떻게 이전 상태로 돌아가고, 무엇을 보존할지 고민 (말 그대로 Back tracking)

재귀

• 재귀 함수: 자기 자신을 호출하는 함수
  • 자기 자신을 호출할 때 ‘다른 상태를 전달’해서 호출
  • 재귀 호출하면서 상태가 점차 base case(종료 조건)에 가까워져야
  • A$_1$(base case)가 정해져 있고 A$_i$가 A$_{i-1}$ 또는 그 이전 케이스들에 영향을 받아 정해지는 것을 그대로 구현한 것(점화식이라고도 할 수 있음)
• 재귀 함수를 짜면서 생각해야 하는 것
  • 재귀 함수가 가지고 있어야 하는 상태는 무엇인가? 상태를 무엇이 결정하는가?
  • 현재 상태가 정해지기 위해서 어떤 상태들이 필요한가? 현재 상태에 영향을 받지 않는 이전의 상태들만으로 가능한가?
  • 함수들이 재귀 호출을 통해 상태를 주고받을 때 사이클이 형성되지 않는가?
    • ex) A$_3$를 결정하기 위해 A$_2$가 필요한데 A$_2$를 결정하기 위해서는 A$_3$이 필요한 경우
  • 코드가 만들어내는 상황이 점점 재귀 함수의 base case에 가까워지는 방향으로 진행하는가?

---

참고

• 이것이 취업을 위한 코딩테스트다 - 구현
• ICPC 신촌 2022 겨울 알고리즘 캠프 - 완전탐색/백트래킹