완전탐색 기법이란?

가능한 모든 값을 대입해보는 무식한(?) 방법에 해당된다.

 

문제 내용 속에서 특정 규칙을 찾아서 모든 Case를 대입해보지 않고도 풀리는 경우도 있지만

충분한 제한 공간과 시간이 주어진다면 특정 수학 공식이나 최적화 없이

문제 내용을 거의 그대로(?) 프로그래밍 언어로 반영해주면 된다.

0 ~ 9 까지 4자리로 구성된 Password가 있다고 가정해보자.

그렇다면 0000 ~ 9999 까지의 Case가 존재하는데

"홀수이다", "짝수이다", "Password를 이루는 숫자는 모두 다르다" 라는 조건이 없다면

간단하면서 가장 확실한 방법은 하나씩 다 입력해보는 것이다.

 

경우의 수 = 10 × 10 × 10 × 10 = 10,000 으로 1초안에 해결할 수 있다.

▶ 알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? 

▶ 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기  

다른 알고리즘 유형처럼 설계하는 과정이 오래 걸리거나

특별한 규칙을 찾아내지 않아도 되는 편이다. → 동적계획법(Dynamic Programming, DP) 

 

<문제 요구 사항을 최적화하는 과정>

▶ 연속된 부분 합(연속합) - 1 (완전 탐색) 

▶ 연속된 부분 합(연속합) - 2 (Prefix Sum) 

▶ 연속된 부분 합(연속합) - 3 (DP) 

 

직관적인 내용을 코딩할 수 있는가?에 대한 문제라고 생각하기에

개인적으로 좋아하는 알고리즘 유형 중 하나이다.

특정 프로그래밍 언어를 학습할 때, 이런 유형의 문제가 많이 도움되는 것 같다.

 

여러 기업에서도 초반 문제 1~2개 정도가 출제되는 편이다.

삼성의 경우, 완전탐색 기반의 BFS / DFS & 구현 / 시뮬레이션 / 설계 유형이 나온다.

▶ 삼성 SW 기출 모음 

[문제 모음] 삼성 sw 기출 (코딩 테스트)

 

완전탐색 기법 종류

- Brutue-Force (반복문 / 조건문으로 전체영역을 탐색하는 기법)

- 비트마스크 (Bitmask) 

- 재귀(Recusion) 함수

- 순열과 조합 

- BFS (Breadth-First Search, 너비 우선 탐색)  

- DFS (depth-first search, 깊이 우선 탐색)  

 

Reference

- [BOJ] 10448 유레카 이론

- [BOJ] 2503 숫자 야구 

- [BOJ] 1062 가르침

- [BOJ] 3085 사탕 게임

- [BOJ] 2231 분해합

- [BOJ] 2309 일곱 난쟁이

- [BOJ] 2210 숫자판 점프