[알고리즘/Algorithm] 완전탐색 / Brute-Force Algorithm 이론 정리 및 예제 풀이
안녕하세요,
최근 알고리즘 문제풀이를 공부하다보니 이론을 다시금 정리해봐야겠다는 생각이 들었습니다.
가장 먼저 완전탐색 알고리즘을 정리해보려고 합니다.
완전탐색 / 브루트포스(Brute-Force) 알고리즘이란? / Exhaustive Algorithm
완전탐색 알고리즘이란 뭘까요?
말 그대로 모든 경우의 수, 혹은 모든 요소들을(완전히) 탐색하는 알고리즘입니다.
모든 경우의 수를 탐색하기 때문에 '무식하게 푼다'는 의미인 Brute-Force라고도 불립니다.
주로 완전탐색 알고리즘 문제를 풀면
가능한 모든 요소들/경우의 수를 탐색을 하여 정답을 도출을 합니다.
간단하게 예를 들자면 다음과 같습니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// 크기 1000
int[] items = new int[1000];
for(int i = 0;i < 1000; ++i) {
items[i] = input.nextInt();
}
// case 1: 반복문
for(int i = 0; i < items.length; ++i) {
// 각 요소들에 대해 수행할 로직
System.out.println(items[i]);
}
// case 2: 재귀
func(items, 0);
}
public static void func(int[] items, int nowIdx) {
// 종료조건
if(nowIdx > items.length - 1) return;
// 각 요소들에 대해 수행할 로직
System.out.println("now: " + items[nowIdx]);
// 조건에 따라 재귀 호출
func(items, nowIdx + 1);
}
}
따라서 시간복잡도도 그만큼 증가하여 시간초과가 날 수 있기 때문에
탐색 요소가 얼마나 되는지, 메모리/시간제한이 얼마나 되는지가 중요합니다.
따라서 탐색 요소의 수가 너무 많지 않을 경우에 선택하는 알고리즘 입니다.
저의 경우 안전하게 1000만 건(10,000,000)이 넘어가면 반복문 한 번으로 탐색가능한 경우가 아니라면 시간 초과의 위험이 있어 그런 경우에는 동적계획법 등으로 방법을 찾아봅니다.
시간 복잡도 계산 방법에 대해서는 저도 추가로 공부하여 포스팅 해 보도록 하겠습니다 :)
완전탐색에서 출발하는 다른 알고리즘도 많습니다.
완전탐색 로직이지만 메모이제이션을 사용하는 동적 계획법, 그래프 알고리즘이자 완전탐색인 DFS/BFS 등이 있습니다.
따라서 다른 알고리즘을 공부하기 전에 완전탐색을 먼저 공부하고 확실히 알고 넘어가는 게 좋다고 생각하여 먼저 정리했습니다.
그럼 예제를 풀어보겠습니다.
예제는 백준 온라인 저지 사이트(Baekjoon Online Judge)에서 풀어보았습니다.
예시 문제 풀이 - 반복문
먼저 반복문으로 해결한 경우입니다.
예제문제: BOJ 2309 일곱 난쟁이
https://www.acmicpc.net/problem/2309
9명의 난쟁이 신장이 주어지면 7명의 키의 합이 100이 되는 난쟁이를 찾아 키를 출력하는 문제입니다.
이 경우는 가능한 경우를 찾아 난쟁이들을 모두 탐색해야합니다.
난쟁이가 2명 이므로 for문 두 개로 전부 탐색하면서 조건에 맞는 경우를 찾아주었습니다.
public int[] getTrueDwarves(int[] dwarves) {
// 반복문 풀이
int[] answer = new int[7];
int height = 100;
int total = 0;
// 난쟁이들의 총 신장
for(int i = 0; i < dwarves.length; i++) {
total += dwarves[i];
}
// 난쟁이 두 명의 합이 height과 같을 때 까지 확인
for(int i = 0; i < dwarves.length; i++) {
for(int j = i+1; j < dwarves.length; j++) {
if(total - (dwarves[i] + dwarves[j]) == height) { // 정답을 찾을 경우
dwarves[i] = 1000;
dwarves[j] = 1000;
break;
}
}
if(dwarves[i] == 1000) {
break;
}
}
Arrays.sort(dwarves);
for(int i = 0; i < 7; ++i) {
answer[i] = dwarves[i];
}
return answer;
}
이렇게 반복문으로 모든 조건을 확인해줄 수 있습니다.
문제의 조건에 '가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.' 라고 되어있으므로 가능한 경우를 찾은 즉시 break;로 로직을 빠져나왔습니다.
만약 '가능한 모든 경우의 수를 구하시오'라고 한다면 break;없이 조건에 해당 될 때 마다 count를 해주면 됩니다.
예시 문제 풀이 - 재귀
다음은 재귀 함수로 문제를 풀어보겠습니다.
예제 문제: BOJ 10974 모든 순열
https://www.acmicpc.net/problem/10974
주어진 숫자 n에 대하여 모든 순열을 사전순으로 출력하는 문제입니다.
먼저 '재귀함수'란, 반복적으로 자기 자신을 호출하는 함수입니다.
따라서 무한루프에 빠지지 않게 종료조건이 필수입니다.
아래는 제가 작성한 모든 순열을 탐색하는 재귀 함수입니다.
// 재귀 함수
public static void permut(int n, int nowIdx, boolean[] check, int[] answer) {
if(nowIdx > n) return;
if(nowIdx == n) { // n개 탐색 시 출력
for(int i = 0; i < answer.length; i++) {
if(i == answer.length - 1) {
System.out.println(answer[i]);
} else {
System.out.print(answer[i] + " ");
}
}
return;
}
for(int i = 0; i < n; ++i) {
if(check[i]) continue; // 방문 여부 확인
check[i] = true; // 방문
answer[nowIdx] = i + 1; // 탐색 결과 저장
permut(n, nowIdx + 1, check, answer);
check[i] = false; // 방문 해제
answer[nowIdx] = 0;
}
}
위와 같이 방문 여부를 체크해주고, 방문한 숫자로 순열을 만들어 가면서 탐색하는 로직을 만들어 주었습니다.
함수 Parameter로는 아래와 같은 변수들을 전달해주었습니다.
| 1 | n | n개를 탐색해야 하고, 탐색 대상이 1~n이므로 n |
| 2 | nowIdx | 현재 탐색중인 순열의 인덱스 |
| 3 | check | 각 숫자의 방문 여부를 확인하기 위한 배열 |
| 4 | answer | 탐색한 결과인 순열을 저장해주기 위한 배열 |
함수 내에서 for문으로 각 숫자의 방문 여부를 확인합니다.
아직 방문하지 않은 숫자의 경우 방문(재귀호출)을 진행합니다.
만약 방문했는데 순열을 완성하였을 경우(nowIdx == n)에는 생성한 순열을 출력해줍니다.
return시에는 (출력 이후로)방문한 숫자의 방문 여부를 해제하고 순열(answer)에서 숫자를 빼 줍니다.
아래 표로 9번째 과정까지 나타내 보았습니다.
| 호출(n=3) | 1) 1번째 호출 (n, 0, check, answer) | 2) 2번째 (n, 1, check, answer) | 3) 3번째 (n, 2, check, answer) | 4) 4번째 (n, 3, check, answer) |
| check | [1, 0, 0] | [1, 1, 0] | [1, 1, 1] | |
| answer | [1, 0, 0] | [1, 2, 0] | [1, 2, 3] | |
| answer 출력 | ||||
| 6) 3번째 후 return | 5) 4번째 후 return | |||
| check | [1, 0, 0] | [1, 1, 0] | ||
| answer | [1, 0, 0] | [1, 2, 0] | ||
| 7) 2번째 - for문 진행 | 8) 5번째 (n, 2, check, answer) | 9) 6번째 (n, 3, check, answer) | ||
| check | [1, 0, 1] | [1, 1, 1] | ||
| answer | [1, 3, 0] | [1, 3, 2] | ||
| answer 출력 |
위 표와 같은 과정을 반복하여 차례로 출력하는 함수입니다.
실제로 저는 헷갈릴 때 이렇게 적어보면 이해하는 데 도움이 되었습니다! 특히 손으로 적어보는 경우가 많습니다.
main에서의 호출은 아래와 같이 해주면 됩니다.
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
boolean[] check = new boolean[n];
int[] answer = new int[n];
permut(n, 0, check, answer);
}
이렇게 구성하면 재귀함수로도 모든 순열을 탐색할 수 있습니다.
이렇게 완전탐색 알고리즘에 대해서 정리해보았습니다.
어쩌면 수학 다음으로 가장 먼저 생각해볼 수 있는 방법이기도 합니다.
이전에 공부할 때 이분탐색, 동적계획법도 완전탐색에서 시작해서 방법을 찾아나가도록 공부했기 때문에 가장 먼저 정리해보았습니다!
