브루트포스 알고리즘과 모의고사

브루트포스 알고리즘

완전 탐색 알고리즘의 한 종류이지만 완전 탐색의 또 다른 이름으로 쓰이기도 한다.
브루트 포스 알고리즘은 완전탐색으로 답을 도출하는 알고리즘이며,
대부분은 반복문과 조건문을 통하여 답을 도출한다.

장점: 모든 경우의 수를 전부 탐색하기 때문에, 100%의 정확성을 보장한다.
단점: 모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다.

완전탐색 vs 브루트포스

브루트 포스와 완전탐색은 의미차이가 거의 없기 때문에 때때로 같은 의미로 쓰이기도 한다.

하지만, 이 둘은 아주 작은 차이가 있다.
먼저, 완전 탐색 알고리즘은 모든 경우의 수를 전부 탐색하는 방식의 알고리즘을 칭하며, 그 결과를 찾는 것보다 탐색한다는 과정에 중점을 둔다.

하지만 브루트포스 알고리즘은 문제를 해결 하기 위하여, 모든 경우를 탐색하고 답을 도출하는 알고리즘으로, 결과를 찾는 것에 중점을 둔다.

따라서 주 된 목적이 탐색과정이냐, 답을 도출하는 것이냐의 차이점이 있다.

브루트포스 사용방법

선형구조

선형구조란 자료를 구성하는 데이터를 순차적으로 나열시킨 형태다.

• 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것이다.
• 자료들 간의 앞뒤 관계가 1:1의 선형관계
• 배열, 리스트, 스택, 큐가 이에 해당된다.

문제에 등장하는 자료구조가 선형구조라면 다음과 같은 순서로 풀이하면된다.

1. 주어진 문제를 선형구조로 바꾼다.
2. 자료들을 구조에 맞는 방법으로 해를 구할 때까지 탐색한다.
3. 탐색된 해를 문제 출력 조건에 맞게 출력한다.

1. 반복문

1부터 100까지의 숫자 중에서 2로 나누어 떨어지고(짝수이고), 9로 나누어 떨어지는 숫자를 구하는 예시

public class SimpleBruteForceExample {
    public static void main(String[] args) {
        // 1부터 100까지 숫자를 하나씩 확인한다.
        for (int i = 1; i <= 100; i++) {
            // 숫자가 2로 나누어 떨어지고(짝수이고), 9로도 나누어 떨어지면 출력한다.
            if (i % 2 == 0 && i % 9 == 0) {
                System.out.println(i);
            }
        }
    }
}

2. 재귀함수

5 팩토리얼을 구하는 예시

public class Example {

    public static void main(String[] args) {
        System.out.println("5 factorial = " + factorial(5));
    }

    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

5 factorial(4) 호출됨.
이는 4 factorial(3)을 호출함.
그 다음 3 factorial(2)를 호출함.
그 다음 2 factorial(1)을 호출함.
factorial(1)은 기본 조건에 도달하여 1을 반환함.

factorial(1)은 1을 반환 (기본 단계)
factorial(2)는 2 factorial(1)이 되므로, 2 1 = 2
factorial(3)는 3 factorial(2)이 되므로, 3 2 = 6
factorial(4)는 4 factorial(3)이 되므로, 4 6 = 24
factorial(5)는 5 factorial(4)이 되므로, 5 24 = 120

이렇게 재귀함수로 모든 경우의 수를 탐색할 수 있음.

선형구조 - 시간복잡도

최선의 경우(Best case): 찾고자 하는 요소가 자료구조의 첫 번째 위치에 있을 때다. 이 경우, 단 한 번의 비교만으로 원하는 값을 찾을 수 있으므로, 최선의 경우의 시간 복잡도는 (O(1))다.

평균적인 경우(Average case): 평균적으로 찾고자 하는 요소가 자료구조의 중간 부근에 위치할 가능성이 있으므로, 평균적인 시간 복잡도도 (O(n))으로 볼 수 있다.

최악의 경우(Worst case): 찾고자 하는 요소가 자료구조의 마지막에 위치하거나 아예 존재하지 않을 때다. 이 경우, 모든 요소를 검사해야 하므로 최악의 경우의 시간 복잡도는 (O(n))다.

비선형구조

• 비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 자료구조다.
• 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계를 지닌다.
• 트리와 그래프가 대표적이며, 계층적 구조를 나타내기에 적절한 자료구조다.

비선형구조 - 시간복잡도

DFS, BFS의 시간복잡도와 동일하다.

주의점

결국 브루트 포스는 모든 경우의 수를 탐색해야 하기 때문에,
만약 탐색해야 할 요소의 숫자가 엄청 크다면 시간복잡도는 그에 비례하여 매우 커질 수 있다.
따라서 가장 좋은 방법은 모든 경우를 탐색하면서 각 경우에서 불필요한 연산을 하지 않는 것이 중요하다.

정리

브루트포스의 풀이 방법은 문제에 등장하는 자료구조가 선형/비선형에 따라 나뉜다. 선형이라면, 순차탐색(반복문, 재귀함수)을 하면 되고 비선형 알고리즘이라면 dfs,bfs를 사용하여 풀이하면 된다. 단, 불필요한 연산은 최대한 피할 수 있으면 피하는 것이 베스트다.

---

---

제출코드

없음.
answer의 길이와 찍기 수열의 길이가 다른데 도대체 어떻게 비교해야 할지 몰랐다.

예를 들어, 찍기 수열이
{1,2,3,4,5} 이고
문제의 정답이
{5,4,3,2,1,5,4,3,2,1,5,4,3,2,1,5,4,3,2,1}
일 때 둘을 어떻게 비교해야 할지 떠오르지 않았다.

모범답안

import java.util.*;

class Solution {
    public List<Integer> solution(int[] answers) {
        int[] first = {1, 2, 3, 4, 5};
        int[] second = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int[] score = {0, 0, 0};

        // 점수 계산
        for (int i = 0; i < answers.length; i++) {
            if (answers[i] == first[i % 5]) {
                score[0]++;
            }
            if (answers[i] == second[i % 8]) {
                score[1]++;
            }
            if (answers[i] == third[i % 10]) {
                score[2]++;
            }
        }

        // 최대 점수 구하기
        int max = Math.max(score[0], Math.max(score[1], score[2]));

        // 최대 점수를 가진 수포자 리스트 생성
        List<Integer> answer = new ArrayList<>();

        for (int i = 0; i < 3; i++) {
            if (max == score[i]) {
                answer.add(i + 1);
            }
        }
        return answer;
    }
}

시간복잡도

• answers 배열의 길이를 n이라고 할 때, for 루프는 n번 반복한다.
  -> O(N)

• 고정된 크기(3)의 배열을 순회하는 반복문
  -> O(1)

따라서, 전체 코드의 시간 복잡도는 O(n) + O(1) = O(n)

배운점

• 이처럼 비교하고자 하는 두 배열의 길이가 다를 땐, 인덱스를 잘 조정하면 된다!
• 이 문제에서는 first[i%5] 와 같은 패턴을 사용했다. %는 나머지 연산자인데,
  만약 answer가 {5,4,3,2,1,5,4,3,2,1}이고 찍기배열이 {1,2,3,4,5}라고 가정하자.
  만약 5번째 인덱스에 있는 5를 비교하려고 할 때 일반적인 반복문으로 구할 수가 없다. 왜냐하면 길이가 다르기 때문이다.
  따라서 이러한 경우에는 인덱스에 i % 5를 작성하면 해결할 수 있다.
  ex) i = 5, 찍기배열 길이 = 5, 찍기배열 목표 인덱스 [0] -> [i % 5]
  -> 5 / 5의 나머지 = 0이다. 따라서 찍기배열의 0번째 인덱스와 비교하게 된다.

• 두 개 이상의 정수들 중에서 max값을 구하는 로직

int max = Math.max(score[0], Math.max(score[1], score[2]));

알다시피 max()는 두 개의 인자를 받는데, 세 개는 어떻게 받아야할까?
쉽다. 두번째 인자로 Math.max(비교값1,비교값2)를 넣으면 된다.

네개의 점수들도 마찬가지 일 것이다.

Math.max(Math.max(score[0],score[1]), Math.max(score[2],score[3]));

참고

https://olrlobt.tistory.com/33
https://goodgid.github.io/DS-Linear-and-NonLinear/