반응형
브루트포스(Brute-force) 란?
Brute Force, 무식하게 힘으로 라는 의미를 가지고 있다.
브루트포스는 완전 탐색 이라고도 불리며, 가능한 모든 경우의 수를 하나도 빠짐없이 전부 시도해보는 방법이다. 즉, 자물쇠의 비밀번호를 맞히기 위해 '0000'부터 '9999'까지 모든 숫자를 하나씩 돌려보는 것과 같은 원리이다.
장점
- 코드를 작성하는 방법이 직관적이라, 초보자도 쉽게 구현할 수 있다.
- 가능한 모든 경우를 확인하기 때문에, 정확도를 100% 보장한다.
단점
- 시간과 자원 비용이 매우 높다.
- 문제의 규모 및 복잡도에 예민하다. 문제의 규모가 커지면 확인해야 할 경우의 수가 늘어나, 정답을 찾기까지 너무 오래 걸린다.
브루트포스는 가장 기초적인 알고리즘으로, 문제 해결의 기본 원리를 이해하는 데 도움을 준다. 그럼 이제 어떻게 구현하는지 예시를 확인해보자.
브루트 포스 구현
반복문 (For Loop) 활용
for 문을 중첩하여 모든 경우의 수를 하나씩 만들어 나간다.
문제 : 두 개의 주사위를 던졌을때, 두 눈의 합이 6이 되는 모든 경우 찾기
public class SimpleLoopExample {
public static void main(String[] args) {
System.out.println("두 주사위의 합이 6이 되는 경우:");
// 첫 번째 주사위 (1부터 6까지)
for (int i = 1; i <= 6; i++) {
// 두 번째 주사위 (1부터 6까지)
for (int j = 1; j <= 6; j++) {
// 두 주사위의 합이 6이면 출력
if (i + j == 6) {
System.out.println("(" + i + ", " + j + ")");
}
}
}
}
}
첫 번째 주사위가 1일 때, 두 번째 주사위 1~6을 모두 시도하고, 첫 번째 주사위가 2일 때, 두 번째 주사위 1 ~ 6을 모두 시도하는 식으로 가능한 모든 조합을 전부 확인한다.
재귀 (Recursion) 활용
재귀 함수가 자신을 호출하며 모든 경우의 수를 탐색해 나간다.
문제: 숫자 1, 2, 3을 사용해서 만들 수 있는 두 자리 숫자를 모두 만들어라. (중복 허용)
public class SimpleRecursionExample {
// 숫자를 조합해서 결과를 저장할 배열
private static int[] result = new int[2];
// 사용할 수 있는 숫자 배열
private static int[] numbers = {1, 2, 3};
// 재귀 함수 (k는 현재 채워야 할 자리)
public static void findCombinations(int k) {
// 두 자리가 모두 채워졌으면 출력하고 종료
if (k == 2) {
System.out.println(result[0] + "" + result[1]);
return;
}
// 0부터 2까지 반복 (숫자 1, 2, 3을 차례로 넣어보기)
for (int i = 0; i < 3; i++) {
result[k] = numbers[i]; // k 자리에 숫자를 넣는다
findCombinations(k + 1); // 다음 자리를 채우러 간다
}
}
public static void main(String[] args) {
System.out.println("1, 2, 3으로 만들 수 있는 두 자리 숫자:");
findCombinations(0); // 첫 번째 자리(0)부터 시작
}
}
findCombinations(0)이 호출되면, 첫 번째 자리에 1, 2, 3을 각각 넣어보고, 각 경우에 대해 findCombinations(1)을 호출해서 두 번째 자리를 채운다. 자기 자신을 계속 호출하여 모든 가능성을 탐색한다.
브루트 포스 관련 알고리즘 문제 보러가기
브루트 포스, 언제 사용해야 하는가?
- 주어진 데이터의 크기가 작을 때
- 시간 제한이 1~2초일 때, 주어진 데이터의 크기가 작다면 ( n < 20) 브루트포스를 우선적으로 고려할 수 있다.
- 최적화 이전에 구현 해보기
- 브루트포스로 완전 탐색 해법을 구해본 뒤, 시간 초과가 발생하면 다른 알고리즘으로 최적화 한다.
반응형
