억지 기법

억지 기법(brute force)은 가장 단순한 알고리즘 기법이다.

 

이 기법은

"문제 정의를 가장 그대로 반영한 알고리즘"

"무식하게 모든 경우의 수에 대해 처리를 하는 알고리즘"

정도로 정의할 수 있다.

 

아래와 같은 간단한 문제가 있을 때,

 

"1부터 10까지의 합을 출력하라"

 

아래와 같이 간단하게 푸는 방법이 존재한다.

---

fn main() {
    let mut sum = 0;

    for i in 1..=10 {
        println!("{}", i);
        sum += i
    }

    println!("{}", sum);
}

---

 

이처럼 문제의 정의를 그대로 적용하는 것을 억지 기법이라고 한다.

 

이러한 문제는 10회만 반복하지만, 만약 10억 회를 반복하는 경우라면?

점점 수행속도가 느려지게 될 것이다.

 

이러한 문제는 수학적 정의를 사용하면 매우 효율적으로 풀린다.

가우스 합의 정의는 다음과 같다.

 

(더하려는 수의 갯수)*(처음 수 + 마지막 수)/2

 

이를 이용한 방법은 아래와 같다.

---

fn main() {
    let sum = 10*(10+1)/2;

    println!("{}", sum);
}

---

위의 방법은 합하는 수의 개수가 몇 개든 한 번 만에 해결된다.

 

자, 그러면 억지 기법이 좋지 않은 혹은 쓸모없는 알고리즘 기법일까?

맞다. 물론 나의 의견이다.

 

아니라고 하는 곳의 의견은 다음과 같다.

1. 해결하지 못하는 것보다 해결이라도 할 수 있는 것이 좋다.
2. 쉬운 문제를, 혹은 입력이 작다는 것이 보장되는 문제를 어렵게 풀 이유가 없다.
3. 매우 광범위한 문제에 적용할 수 있다.
4. 다른 알고리즘보다 특정 상황에서 오히려 더 빠를 수 있다.
5. 더 효율적인 알고리즘을 위한 알고리즘 기반이 될 수 있다.

인정한다.

위에서 수학적 정의를 이용해 푸는 방법도 만약 이런 게 있다는 것을 모른다면 저렇게 극적으로 효율적으로 풀기 굉장히 어려웠을 것이다.

그러므로, 나는 억지 기법이 쓸모없다고 하는 것이다.

알면 된다.

4번의 경우는 정말 특수한 경우에만 해당하므로 무시하자.