[Algorithm] Brute Force(완전 탐색)

[jane1choi]

Brute Force(완전 탐색)란?

Brute Force = Brute (짐승 같은, 동물) + Force (힘)
의미 그대로 짐승 같이, 무식하게 힘으로 해결하는 것, 알고리즘에서는 무차별 대입 정도로 해석할 수 있을 것 같습니다.

브루트 포스 문제의 접근 방법은 굉장히 쉽습니다. 답이 될 수 있는 모든 경우를 확인해보는 것입니다.
가장 원초적이고, 직관적인 해결 방법으로, 문제를 해결하기 위해 가능한 모든 경우와 그 경우의 결과를 구하기 때문에
브루트 포스 알고리즘으로 문제를 풀면 무조건!! 정답이 나올 수 밖에 없습니다.

그렇다면, 모든 문제에서 브루트포스를 쓰면 되잖아?🤔 라는 의문이 생기게 됩니다!
하지만! 브루트포스의 가장 큰 단점은 숫자가 커지면 커질수록 그만큼 시간 복잡도가 엄청나게 커집니다!
따라서 입력 데이터의 크기가 작고, 내가 구현할 시간복잡도 내에 해결 가능할 때만 사용해야 합니다.

시간 복잡도

먼저 시간 복잡도에 대해 간단하게 설명하자면,
시간 복잡도를 고려한다는 것은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’ 라는 말입니다.

효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 것이며, 이러한 시간 복잡도는 주로 빅-오 표기법을 사용해 나타냅니다.

• Big-O(빅 오) 표기법: O(n) 알고리즘 최악의 실행 시간을 표기합니다. 가장 많이 그리고 가장 일반적으로 사용하는 표기법입니다. 아무리 최악의 상황이라도 최소 이정도의 성능은 보장한다는 의미이기 때문에 Big-O 표기법을 가장 많이 사용합니다.

완전 탐색의 시간 복잡도는 O(n) 입니다.
(최악의 경우) 배열의 갯수 n만큼 순회하기 때문입니다.
Brute Force는 접근 방법이 간편하긴 하지만, 그만큼 시간복잡도 면에서 단점이 있습니다.

어떤 방식으로 풀까?

1. 반복문

func sequencial(_ array: [Int], num: Int) -> Bool {
    for element in array {
        if num == element {
            return true
        }
    }
    return false
}

배열 전체를 순회하며 찾는 값이 있으면 true, 없으면 false를 리턴합니다.

2. 재귀 함수
   재귀함수(Recursive Call)는 함수 안에서 자기 자신을 호출하는 형태로, 완전 탐색을 위해 원하는 결과값을 얻기까지 재귀를 반복하는 방식입니다.

func recurAdd(_ num: Int) -> Int {
    if num == 1 {
        return 1
    }
    return (num + recurAdd(num - 1))
}

위의 recurAdd 재귀 함수의 탈출 조건은 파라미터로 들어오는 num 값이 1인 경우입니다.
때문에, num이 1이 될 때까지 계속 자기 자신 함수를 호출시키면서 원하는 값을 얻습니다.
만약 파라미터인 num이 100이라면, 100 + 99 + 98… + 1
단, 탈출 조건이 없다면 무한 재귀에 빠질 수 있는 위험이 있기 때문에 탈출 조건을 꼭 명시해주어야 합니다!