2. 완전탐색 (Brute Froce)과 백트래킹(Backtracking)

2-1. 완전탐색 (Brute Force)

완전탐색이란, 단순히 모든 경우를 확인하는 기법이다.

Naiive하게 떠올릴 수 있는 아이디어라 쉽게 접근이 가능하지만, 테스트 케이스에 따라 소요 시간이 엄청 커질 수 있다.

그래서 가장 먼저 고민할 수 있는 아이디어이지만, 경계심을 가지고 문제의 조건을 보아야함.

표본의 수와 시간복잡도 계산 등 전체적으로 고려하여 선택하는 것이 중요하다.

그래서 문제를 풀기 전 설계 후 시간 복잡도 계산을 간단하게나마 해보는 것이 습관처럼 되어야한다.

 

완전탐색의 대표적인 건, 조합과 순열이다.

문제를 해결하기 위해 모든 경우를 전부 탐색해야 하는 경우를 말하며

이 때 만약, 어떠한 조건을 통해 더 탐색하지 않아도 되는 promising한 경우가 있다면 가지치기(pruning)를 통해 backtracking을 사용할 수도 있다. (밑에서 설명)

N 개중 (중복을 허용 해서 || 중복을 허용하지 않고 ) M 개를 (순서있게 나열하기 || 고르기)

- N과 M list 시리즈

https://www.acmicpc.net/workbook/view/2052

문제집: N과 M (시리즈)

재귀함수와 완전탐색을 연습해볼 수 있다.

기본 틀에서 조건을 붙여가며 활용을 연습해볼 수 있음.

고를 수 있는 수의 종류확인. 중복여부확인(방문여부 등으로 check해주어야함) , 순서가 중요한지 check 등.

 

재귀함수는 종료조건부터 생각하는 것이 좋다.

 

- 연산자 끼워넣기 
https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

 

정리 및 구현 시 고려할 점

 1. 완전탐색( 나올 수 있는 모든 경우에 대해 탐색한다)

  Naiive하게 가장 먼저 떠올릴 수 있는데, 항상 '아닌 것 같은데..' 에서 고민하고 다른 방법을 찾다가

  못 찾고 검색해보면 결국 완전탐색이었던 경우가 많았다.

  간단하지만 확실하게 계산을 통해서 논리적으로 접근하는 것이 중요하다고 생각함.

 2. 탐색 방법에 대한 생각을 정확하게 해야함.

   2.1 TOP- DOWN

       재귀함수 > 종료조건이 중요함. 

   2.2 BOTTOM-UP 

       순서가 맞는가 생각해볼 수 있음.

 3. 상태 공간에 대한 이해.

     - 탐색 공간에 대해 정의할 때 상태를 이해해야함.
     - https://www.acmicpc.net/problem/2251

2251번: 물통

    해당 문제를 풀면서 탐색공간에 대한 이해를 하게됨.

 

2-2. 백트래킹(Backtracking)

완전탐색은 모든 경우를 다 탐색해야한다는 장점이 있지만 , 그렇기 때문에 시간이 많이 소요된다는 단점이 있다.

백트래킹은 완전탐색의 장점 '모든 경우를 다 탐색한다는 점'  + '가능하다면' 이 붙어 가능한 경우를 다 탐색한다고 생각할 수 있다.

'모든경우를 다 탐색' + '가능한가?' => '가능한 경우를 모두 탐색'

탐색 중에 조건에 맞지 않다면 이전 상태로 돌아가서 다시 탐색해야하는 경우가 많기 때문에 재귀함수를 사용하는 경우가 많다. 

Promising함수를 통해 가지치기(Pruning)을 어떻게 하는가에 따라 탐색 시간이 많이 차이가 난다.

이후 설명할 DFS 탐색방법에 적합한 방법이다.

 

정리 및 구현 시 고려할 점

1. 백트래킹은 '가능한 경우를 모두 탐색'하는 탐색 기법이다. (완전탐색의 special case)

2. 재귀함수를 통해 구현하는 경우가 많다.
 2-1. 재귀함수를 구현할 때는 조건 설정과 어디서 부터 다시 탐색하는가에 초점을 둔다.

 2-2. promising함수 구현을 잘해야함.

대표적인 문제로 N-Queen 문제가 있다.