완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 뽑아 가져온다.
브루트포스 알고리즘의 강력한 점 = 100%의 확률로 예외없이 정답만을 추출한다.
문제의 모든 정답 후보에게 당신이 정답이냐고 물어보는 것이기 때문에 100% 확률로 정답이 나오는 것이다.
모든 문제는 완전탐색으로 풀 수 있다. 투포인터, 우선순위 큐 등 여러 알고리즘 기법은 완전탐색을 안하고 좀 더 효율적인 방법을 찾기 위한 것이다.
그렇기 때문에 문제가 풀리지 않는다면 완전탐색을 생각해내면 될 것이다.
알고리즘 설계
문제설정
모든 영역을 탐색할 것이다라는 생각을 가지고 접근을 시작한다
문제를 해결하기 위해 여러 단계로 나눌 것이다.
-
해가 존재할 것으로 예상되는 영역을 특정한다. (전체를 탐색한다에서 그 전체가 어디서부터 어디까지인지 설정한다.)
-
정답이 되는 조건을 명시한다. (정답을 걸러내는 로직을 준비한다.)
-
찾은 정답이 해가 될때까지 이를 반복한다.
예시 : 100개의 난수 중 10이하의 숫자를 작은 순서로 열거하라.
-
100개의 난수 중 정답이 있다
-
10이하의 숫자인지 물어본다.
if a <= 10 -
ex) 3 6 1 세 숫자가 나왔다. 아직 해가 되지 못한다.
2-1. 찾아낸 10이하의 숫자 중 정답이 있다.
2-2. 가장 작은 숫자를 찾아낸다.
2-3. 1.. 3,6 중 가장 작은 숫자를 찾아야한다..반복한다.
3-3. 1,3,6 해가 나왔다.
탐색
특정한 구조마다 전체적으로 탐색하는 방법을 익혀둔다.
-
문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.
-
자료들이 어떤 구조로 저장되어 있는지 파악한다.
-
선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다. (사실 dfs는 백트래킹과 관련이 깊다.)
문제 파악할 때 DFS문제다! 라고 접근을 시작하는 것이 아니라,
모든 영역을 탐색해야지->비선형구조네->최단거리와 같이 선착순이 정답의 조건이네->DFS
이런식의 접근이 되어야 한다. 보자마자 DFS구나 생각하는 것은 어려울뿐더러 알고보니 비효율적인 방법이였을 가능성이 크다.
시간
코딩테스트에서 알고리즘의 종류를 파악하는 것이 문제풀이의 여부에 크게 관여한다.
어차피 완전탐색으로 모든 문제가 풀린다면 이러한 고민이 필요가 없지 않은가.
그 이유는 시간 복잡도에 있다. 각 단계마다 모든 영역을 탐색한다면 시간복잡도가 매우 올라간다. 그부분을 고려하여 부분적으로 혹은 전체적으로 다른 알고리즘을 적용하여 설계해야 할 것이다.
시간 복잡도가 높은 경우가 많다. 1초 = 1억회 연산을 기억하자
대표문제
백준4673 셀프넘버 https://www.acmicpc.net/problem/4673
