# 브루트 포스 알고리즘 (Brute force)

## 브루트 포스란?

- 가능한 **모든 경우의 수를 탐색**하여 문제를 해결하는 방식
- 더 효율적인 알고리즘이 존재하는 경우에는 해당 알고리즘을 사용하는 것이 좋다
- 암호학에서 종종 사용된다
- 장점
- 알고리즘을 설계하고 구현하기 매우 쉽다
- 거의 완벽하게 병렬 작업이 가능하다는 특징이 있다
- 항상 정확도 100%를 보장한다
- 단점
- 경우의 수가 많아질수록 시간 복잡도가 높아져 비효율적일 수 있다
- 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다
- 예시
- 배열에서 최대값과 최소값 찾기
- 완전수 찾기
> 완전수 : 자기 자신을 제외한 약수를 더했을 때 자기 자신이 되는 양의 정수. (ex: 28 = 1 + 2 + 4 + 7 + 14)
- 비밀번호 크래킹 (4자리 휴대전화의 비밀번호 찾기)
- 선택 정렬, 버블 정렬, 삽입 정렬도 브루트포스 알고리즘의 일종으로 간주할 수 있다.

## 브루트 포스 예시

1. 블랙잭 문제
- 숫자 카드들 중에서 3장을 선택하여 그 합이 최대한 가까워지는 경우의 합을 구하는 문제
- 백준 알고리즘 2798번 ==[링크](https://www.acmicpc.net/problem/2798)==
2. 분해합 문제
- 주어진 숫자 N의 가장 작은 생성자를 구하는 문제
- 백준 알고리즘 2231번 ==[링크](https://www.acmicpc.net/problem/2231)==
3. 다음 순열 문제
- 주어진 순열의 다음 순열을 구하는 문제
- 백준 알고리즘 10972번 ==[링크](https://www.acmicpc.net/problem/10972)==

> 브루트포스보다 더 효율적인 알고리즘이 존재하는 경우 그 알고리즘이 더 좋은 선택이 될 수 있다.
> 또한 알고리즘 시험에서 브루트 포스를 사용하는 경우 오답으로 간주될 수 있으므로 주의해야 한다.
>
> 일반적으로 다음과 같은 경우 부르트 포스 알고리즘을 고려해볼 수 있다.
>
> - 탐색 공간이 작은 경우
> - 문제의 구조가 단순한 경우
> - 최적해를 찾기 위한 고급 기법이 필요하지 않은 경우

### 블랙잭 문제

- 백준 알고리즘 2798번 ==[링크](https://www.acmicpc.net/problem/2798)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 블랙잭 문제 수도코드 예

1. 카드 리스트를 입력받는다.
2. M 값을 입력받는다.
3. 가장 M과 가까운 합을 찾기 위한 변수를 초기화한다 (예: closestSum = 0).
4. 3개의 카드를 선택하는 모든 조합에 대해 다음을 수행한다.
    a. 선택한 카드의 합을 구한다.
    b. 카드의 합이 M보다 작거나 같고, closestSum보다 크다면 closestSum을 업데이트한다.
5. closestSum을 출력한다.

#### 블랙잭 문제 소스코드 예

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 카드의 개수 입력
        int M = sc.nextInt(); // 목표값 입력
        int[] cards = new int[N];

        for (int i = 0; i < N; i++) {
            cards[i] = sc.nextInt(); // 카드값 입력
        }

        int closestSum = 0;
        for (int i = 0; i < N - 2; i++) {
            for (int j = i + 1; j < N - 1; j++) {
                for (int k = j + 1; k < N; k++) {
                    int sum = cards[i] + cards[j] + cards[k];
                    if (sum <= M && sum > closestSum) {
                        closestSum = sum;
                    }
                }
            }
        }

        System.out.println(closestSum); // 가장 M에 가까운 합 출력
    }
}

### 분해합 문제

- 백준 알고리즘 2231번 ==[링크](https://www.acmicpc.net/problem/2231)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

### 분해합 문제 수도코드 예

1. N 값을 입력받는다.
2. 생성자를 찾기 위한 최소값을 찾기 위해, 1부터 N까지 모든 수에 대해 반복한다.
3. 현재 수(i)와 그 수의 각 자리수를 더하는 함수를 사용하여 분해합을 계산한다.
4. 계산된 분해합이 입력받은 N과 같다면, 현재의 i를 출력하고 프로그램을 종료한다.
5. 만약 1부터 N까지의 모든 수에 대해 반복했음에도 불구하고 생성자를 찾지 못했다면, 0을 출력한다.

### 분해합 문제 소스코드 예

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        for (int i = 1; i < N; i++) {
            int sum = i;
            int current = i;
            
            while (current > 0) {
                sum += current % 10; // 현재 수의 가장 오른쪽 자리 수를 더함
                current /= 10; // 현재 수의 가장 오른쪽 자리를 제거
            }
            
            if (sum == N) {
                System.out.println(i); // 생성자 출력
                return;
            }
        }
        
        System.out.println(0); // 생성자가 없는 경우
    }
}

### 다음 순열 문제

- 백준 알고리즘 10972번 ==[링크](https://www.acmicpc.net/problem/10972)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

### 다음 순열 문제 수도코드 예

1. 순열을 입력받는다.
2. 주어진 순열에서 뒤쪽부터 탐색하여, 처음으로 a[i-1] < a[i]를 만족하는 위치 i를 찾는다.
3. 만약 그러한 i가 존재하지 않는다면(즉, 주어진 순열이 마지막 순열이라면), 첫 번째 순열로 만들어 출력한다.
4. i-1 위치의 값과 교환할, i 위치부터 끝까지 중 a[i-1]보다 큰 첫 번째 값을 찾는다.
5. i-1 위치의 값과 찾은 값을 교환한다.
6. i 위치부터 끝까지를 오름차순으로 정렬한다.
7. 결과 순열을 출력한다.

### 다음 문제 순열 소스코드 예

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 사용자로부터 순열의 길이 N을 입력받음
        int[] permutation = new int[N]; // 순열을 저장할 배열 선언
        for (int i = 0; i < N; i++) {
            permutation[i] = sc.nextInt(); // 순열의 요소를 하나씩 입력받음
        }
        
        if (nextPermutation(permutation)) {
            for (int i = 0; i < N; i++) {
                System.out.print(permutation[i] + " "); // 다음 순열을 출력
            }
        } else {
            System.out.println("-1"); // 다음 순열이 없는 경우 -1 출력
        }
    }
    
    public static boolean nextPermutation(int[] array) {
        int i = array.length - 1;
        // 뒤쪽부터 탐색하여 처음으로 a[i-1] < a[i]를 만족하는 i를 찾음
        while (i > 0 && array[i-1] >= array[i]) i--;
        
        // 마지막 순열인 경우 false 반환
        if (i <= 0) return false;
        
        int j = array.length - 1;
        // a[i-1]보다 큰 첫 번째 값을 뒤에서부터 찾음
        while (array[j] <= array[i-1]) j--;
        
        // a[i-1]과 a[j]를 교환
        int temp = array[i-1];
        array[i-1] = array[j];
        array[j] = temp;
        
        // i 위치부터 끝까지를 오름차순으로 정렬
        // 이미 내림차순으로 정렬되어 있으므로, 오름차순으로 뒤집기만 하면 됨
        j = array.length - 1;
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
        
        // 다음 순열을 성공적으로 생성하였으므로 true 반환
        return true;
    }
}