이번에는 브루트 포스(Brute Force)에 대해 알아보자.
브루트 포스(Brute Force).
brute: (큰) 짐승, 짐승 같은, 난폭한
force: 힘, 폭력
힘으로 밀어붙이는, 무차별 대입 방식 정도로 해석할 수 있다.
흔히들 브루트포스 또는 완전 탐색이라고 부르는 알고리즘 개념이다.
이름 그대로 모든 경우의 수를 탐색하는 것을 골자로 한다.
PS(Problem Solving, 알고리즘을 적용하는 문제 풀이)에는 '구현' 또는 '시뮬레이션' 태그와 함께 문제에 등장하는 일이 잦다.
열쇠를 들고 다니면 가끔 난처한 상황에 처할 수 있기에, 번호로 된 자물쇠를 선호하는 사람들이 있다.
그러나 이러한 자물쇠는 흔히들 말하는 '노가다' 방식으로 풀 수 있다.
비밀번호를 잊어버려도, 누군가가 나쁜 마음을 먹어도, '0000'부터 '9999'까지 전부 입력해보면 되는 것이다.
운이 나빠서 비밀번호가 '9999'라고 할지라도, 1만 번의 시행만 한다면 확정적으로 자물쇠를 풀 수 있다.
물론 사람이 1만 번을 시도하는 것은 상당히 고되고 재미없는 작업이겠지만, 컴퓨터가 1만 번의 연산을 하는 것은 아주 쉬운 일이다.
컴퓨터에게 고작 1만 번의 시행은 가벼운 일인 것이다.
네이버 회원가입을 진행할 때, 비밀번호의 조건은 다음과 같다.
- 8~16자의 영문 대/소문자, 숫자, 특수문자를 사용할 것
소문자와 대문자를 합쳐 52자, 숫자 10자, 특수문자 32자(네이버 고객센터에 제시되어 있다!)를 합치면 총 94종류의 문자가 있다.
8자 길이의 비밀번호라고 하더라도 948 = 약 6000조 경우의 비밀번호가 가능하다.
안전진단의 문제로 너무 쉬운 패턴을 금지한다거나, 동일한 문자의 반복 등장을 금지하는 등의 조건이 붙으면 비밀번호의 가짓수는 줄어들기는 할 것이다. 9자 길이, 10자 길이.. 다양한 길이의 비밀번호가 남아 있어 6000조의 종류보다는 훨씬 많겠지만 말이다.
비밀번호를 해킹하는 입장에서 아무런 조건 없이(사람들이 이름과 생일을 비밀번호에 자주 쓰는 걸 고려해도) 알아내려면,
얼마나 고생해야 할지 감이 잡히는가?
따라서, 완전 탐색 알고리즘은 문제의 복잡도에 아주 취약하다.
입력의 범위를 조금 더 늘린다던가 하는 조건 변경이 이루어지면, 소모하는 시간과 메모리가 기하급수적으로 오르는 것이다.
장점은, 모든 경우를 탐색하기 때문에 항상 정답을 도출할 수 있다는 것이다.
개념 자체는 설명할 것이 얼마 없으니, PS(문제 풀이)를 통해 완전 탐색이 어떤 느낌을 갖는 지 알아보도록 하자.
이미지를 클릭하면 문제로 이동할 수 있다.
백준은 국내에서 가장 PS 접근성이 높은 사이트이므로, 코딩테스트를 준비해야 한다면(그리고 대부분이 준비해야한다)
회원가입 해두는 것이 좋다.
첫째 줄에 카드의 개수와 목표하는 숫자를 입력받는다.
둘째 줄에 카드의 숫자들을 입력받는다.
문제에서 친절하게도, 정답이 항상 있는 경우만 입력이 주어진다고 한다.
public class Main {
public static void main(String[] args) {
int n, m;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int cards[] = new int[n];
for (int i = 0; i < n; i++) {
cards[i] = sc.nextInt();
}
}
}코드의 뼈대다.
Scanner를 이용해서 첫 번째 줄인 n(카드의 개수), m(목표로 하는 숫자)를 선언하고 초기화한다.
여러가지 자료 구조를 사용할 수 있겠지만, 가장 범용적이고 쉬운 배열을 이용하기로 했다.
카드의 개수가 n개니까, 반복문을 통하여 배열 'cards'에 두 번째 줄의 카드 숫자들을 배열에 넣어두었다.
이 문제의 핵심은
- 어떤 기준으로 카드 3장을 뽑을 것인가?
- 그 숫자들의 합을 어떻게 관리할 것인가?
낮은 숫자와 큰 숫자의 조합으로 m에 가까워지는 경우가 있을 테니 뽑는 순서를 조작할 수는 없고,
결국 모든 조합을 탐색해야 한다는 결론에 이르게 된다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n, m;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int[] cards = new int[n];
for (int i = 0; i < n; i++) {
cards[i] = sc.nextInt();
}
int result = 0;
int sum;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
sum = cards[i] + cards[j] + cards[k];
if (sum <= m) {
if (result < sum) {
result = sum;
}
}
}
}
}
System.out.println(result);
}
}
3중 반복문을 통하여 모든 카드 조합의 합을 'sum' 변수에 대입했다.
바깥 반복문의 초기식 변수를 안쪽 반복문의 조건식에 이용하는 방법은 앞으로도 종종 써먹을 수 있는 발상이다.
이러한 방식으로 조합(Combination)을 구현했다.
만약 'sum'이 목표로 하는 'm' 이하라면, result와 비교하고 값이 더 크다면 result에 대입한다.
문장은 어려워 보이지만, 결국 초기값이 0인 result에 대해 'result ＜ sum ≤ m'인 경우만 'result'에 'sum'을 대입하는 것이다.
'result'는 점점 'm'에 가까워질 것이고, 모든 경우의 수를 돌면 자연스레 'm'에 최대한 가까운 카드의 합을 구할 수 있다.
모든 경우의 수를 탐색한 다음 'result'를 출력한다.
모든 경우의 수를 탐색하면, 목표를 탐색한 이후에도 쓸데없는 탐색을 진행하게 될 지도 모른다.
코드에 조건을 추가하면 불필요한 탐색을 줄일 수 있다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n, m;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int[] cards = new int[n];
int idx = 0;
for (int i = 0; i < n; i++) {
int k = sc.nextInt();
if (k > m - 2) continue;
cards[idx] = k;
idx++;
}
int result = 0;
int sum;
for (int i = 0; i < idx; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
sum = cards[i] + cards[j] + cards[k];
if (sum <= m) {
if (result < sum) {
result = sum;
}
}
if (result == m) {
System.out.println(result);
return;
}
}
}
}
System.out.println(result);
}
}
코드의 개선점은 크게 2가지다.
- 카드의 숫자 'k'를 입력 받을 때, 'm - 2'보다 큰 숫자는 입력하지 않고 건너뛴다.
카드 3장의 합을 'm' 이하이면서 'm'과 최대한 근접하게 만들어야 하는 것이 문제의 조건이다.
또한, 모든 카드의 숫자는 10만을 넘지 않는 양의 정수라 했다. 즉, 최솟값은 1이다.
만약 어떤 카드의 숫자가 'm - 1' 이상이라면, 다른 두 카드가 1이라도 합이 'm + 1'이 되어버린다.
즉, 아예 필요 없는 카드이므로 배열에 넣지 않는다.
배열의 인덱스 관리를 위해 'idx'라는 변수를 따로 추가하여 사용했다. - 'result'가 'm'과 같다면, 필요한 출력을 하고 코드를 종료한다.
우리의 목표는 'm' 이하이며, 최대한 'm'에 가까운 카드 숫자들의 합을 구하는 것이다.
즉, 조건을 만족하는 가장 큰 수는 'm'이며 그 이후의 탐색은 불필요하다.
운이 좋아 모든 경우의 탐색을 진행하기 전에 'result == m'을 만족한다면, 탐색을 멈춰도 타당하다.
물론, 이런 미세한 개선으로 정답과 오답이 갈리지는 않는다.
그렇지만 가능하다면 코드에 추가하지 않을 이유도 없다.
조금 더 어려운 문제를 하나 더 살펴보도록 하자.
이미지를 누르면 문제로 이동할 수 있다.
브루트포스는 구현이나 시뮬레이션 태그와 함께 등장하는 경우가 많다고 위에서 이야기했다.
이 경우는 구현 태그와 같이 등장한 문제이다.
높이 제한이 0~256의 정수라고 주어졌고, 최소 시간을 출력하라고 했으므로 모든 높이에 대해 시간을 구한 뒤 가장 작은 값을
출력하는 것이 일반적인 해결 방식이다.
구현 태그의 경우, '알고리즘을 알고 있냐'는 문제보다 '어떻게 코드를 써내려 갈 것인가'가 더 핵심에 가깝다.
풀지 못해도 좋으니, 한 번 시도해보도록 하자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int rows = Integer.parseInt(st.nextToken());
int cols = Integer.parseInt(st.nextToken());
int initialInventory = Integer.parseInt(st.nextToken());
TerrainLeveler leveler = new TerrainLeveler(rows, cols, initialInventory);
for (int r = 0; r < rows; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < cols; c++) {
leveler.setHeight(r, c, Integer.parseInt(st.nextToken()));
}
}
leveler.computeBest();
leveler.printResult();
}
}
class TerrainLeveler {
private final int[][] ground;
private final int initialInventory;
private int minHeight = 256;
private int maxHeight = 0;
private int bestTime = Integer.MAX_VALUE;
private int bestHeight = 0;
TerrainLeveler(int rows, int cols, int initialInventory) {
this.ground = new int[rows][cols];
this.initialInventory = initialInventory;
}
void setHeight(int r, int c, int height) {
ground[r][c] = height;
if (height < minHeight) minHeight = height;
if (height > maxHeight) maxHeight = height;
}
void computeBest() {
// 가능한 목표 높이(targetHeight)를 전부 브루트포스로 검사
for (int targetHeight = minHeight; targetHeight <= maxHeight; targetHeight++) {
int time = 0;
int inventory = initialInventory;
for (int r = 0; r < ground.length; r++) {
for (int c = 0; c < ground[0].length; c++) {
int current = ground[r][c];
if (current > targetHeight) {
// 제거: 2초, 인벤토리 + (제거한 블록 수)
int remove = current - targetHeight;
time += remove * 2;
inventory += remove;
} else if (current < targetHeight) {
// 설치: 1초, 인벤토리 - (설치한 블록 수)
int add = targetHeight - current;
time += add;
inventory -= add;
}
}
}
// 인벤토리가 부족하면 이 높이는 불가능
if (inventory < 0) continue;
// 최소 시간 갱신, 시간이 같으면 더 높은 높이 선택
if (time < bestTime || (time == bestTime && targetHeight > bestHeight)) {
bestTime = time;
bestHeight = targetHeight;
}
}
}
void printResult() {
System.out.println(bestTime + " " + bestHeight);
}
}
구현이 어려운 점은, 아무래도 코드 길이가 길다는 점이다.
따라서 코드에 주석을 조금 달아놨다.
항상 높이 0~256을 검사할 필요 없이, 입력을 받을 때 가장 낮은 높이와 가장 높은 높이를 저장해둔다.
그 사이의 범위만 탐색하면 되는 것이다.
진행 과정은 다음과 같다.
- 대상으로 할 높이에 대하여 블럭을 놓고 지운다.
놓고 지우면서 인벤토리 블럭의 변화를 반영하고, 걸리는 시간을 기록해둔다. - 만약 인벤토리 블럭의 수가 0보다 낮다면(불가능한 케이스) 건너뛴다.
실제로 게임을 플레이한다면, 탐색을 진행하면서 인벤토리 블럭의 개수가 0 미만으로 내려갈 수는 없다.
그러나 우리는 가능 여부만을 따진다.
잠시 인벤토리 블럭의 수가 음수로 내려가도 목표 높이의 탐색 종료 시 인벤토리 블럭의 개수가 0 이상이라면
목표 높이로 평탄화 가능한 것으로 간주해도 괜찮다. - 지금까지 걸린 시간들 중 최솟값과, 해당 탐색에서 걸린 시간을 비교한다.
조건에서 주어진 대로 소모된 시간이 같다면 더 높은 높이를 출력해야 하므로, 높이 또한 갱신한다.
'PS > 알고리즘과 자료구조' 카테고리의 다른 글
| Greedy: 그리디 (0) | 2025.12.20 |
|---|---|
| [JAVA] 재귀와 DP(동적 계획법) (0) | 2025.12.20 |
