[08강] 브루트 포스 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 브루트 포스 알고리즘에 대해 알아보겠습니다.

 

목차

1. 브루트 포스 알고리즘
2. 실제 문제에서 브루트 포스 알고리즘

 

 

접근 방식과 알고리즘

접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다.

 

접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고,

알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다.

 

구체적인 예를 들어 설명해보겠습니다.

 

에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고,

그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다.

 

에라토스테네스의 체 알고리즘은 언제 쓰면 될까요?

→ 소수(prime number)를 판별할 때 쓰면 됩니다.

 

그리디 알고리즘은 언제 쓰면 될까요?

→ 매 순간에서 가장 최선의 선택을 하여 답이 나올 때 쓰면 됩니다.

 

어떠신가요?

에라토스테네스의 체 알고리즘 같은 경우는 소수(prime number)를 판별할 때 쓰면 되는 반면,

그리디 알고리즘의 경우는 "매 순간에서 가장 최선의 선택을 하여 답이 나올 때가 언제인데?" 라는 의문이 들 것입니다.

 

따라서,

에라토스테네스의 체 알고리즘과 같이 쓰이는 상황이 구체적인 알고리즘을 알고리즘이라 생각하고

그리디 알고리즘과 같이 쓰이는 상황이 구체적이지 않은 알고리즘을 접근 방식이라 생각하시면 됩니다.

 

접근 방식에 가까운 알고리즘은 대표적으로

브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 등이 있습니다.

 

이러한 접근 방식에 가까운 알고리즘 문제는

알고리즘을 쓸 수 있도록 상황을 해석하는 능력(문제해결능력)이 중요하게 작용합니다.

 

 

 

1. 브루트 포스 알고리즘

브루트 포스(Brute Force)는 Brute(무식한) + Force(힘) 으로

무식하게 모든 경우를 확인한다는 의미입니다.

[브루트 포스 알고리즘]

브루트 포스 알고리즘은 모든 경우를 살펴봄으로써 답을 구하는 알고리즘입니다.

 

이 알고리즘은 모든 경우를 살펴보기 때문에 예외 없이 100% 정답을 도출합니다.

하지만, 모든 경우를 다 살펴보기 때문에 수행 시간이 오래 걸릴 수 있음.

 

브루트 포스 알고리즘은 접근 방식에 가까운 알고리즘이므로

2가지 구체적인 상황을 예로 들어 설명하겠습니다.

 

Case1) 브루트 포스 알고리즘 사용 가능

[문제]
자연수 N이 주어지면, 1부터 N이하의 자연수 중에서 소수(prime number)의 개수를 출력하는 프로그램을 작성하시오.
(단, N은 1,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

이 문제는 브루트 포스 알고리즘을 사용하여 풀 수 있습니다.

 

브루트 포스 알고리즘은 정의는 모든 경우를 살펴 봄으로 써 답을 구하는 알고리즘입니다.

 

따라서 N이 주어지면,

1부터 N의 자연수 각각에 대해 소수인지를 판별하여

소수이면 정답에 1을 더하고, 소수가 아니면 넘어가며 문제를 해결하면 됩니다.

 

이 풀이의 경우,

N개의 자연수가 존재하므로 O(N),

각 수에 대해 소수인지를 판별해야 하므로 O(N)입니다.

 

따라서, 시간 복잡도는 O(N²) 이 나오게 되고 N은 1,000 이하의 자연수이므로,

이 풀이는 100만 번 연산 내에 문제를 해결할 수 있게 됩니다.

 

어떤 수 K가 소수인지를 판별할 때는 2부터 K-1로 나눠보며 처리하므로 O(K)가 걸리게 되지만

여기서는, 어떤 수 K는 항상 N보다 작으므로 넉넉하게 O(N)으로 처리했습니다.

사실, 2부터 √K까지만 살펴보면 되므로 O(√K)로 가능합니다.

이에 대한 자세한 내용은 에라토스테네스의 체 알고리즘 의 약수의 성질 부분을 참고해주세요!

 

위의 풀이를 코드로 구현하면 다음과 같습니다.

 

 

 

 

Case2) 브루트 포스 알고리즘 사용 불가능

[문제]
자연수 N이 주어지면, 1부터 N이하의 자연수 중에서 소수(prime number)의 개수를 출력하는 프로그램을 작성하시오.
(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

이 문제는 브루트 포스 알고리즘을 사용하여 풀 수 없습니다.

 

이 문제를 Case1) 의 풀이인 O(N²) 풀이를 사용하게 되면

최악의 경우인 N=1,000,000인 경우, 1조 번의 연산이 필요하므로 시간초과가 나게 됩니다.

 

따라서,

이 문제는 에라토스테네스의 체 알고리즘을 이용해야 합니다.

에라토스테네스의 체 알고리즘은 여러 수에 대해 소수를 판별해야 할 때 사용할 수 있는 알고리즘입니다.

자세한 내용은 에라토스테네스의 체 알고리즘 을 참고해주세요.

 

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(N log(logN)) 으로

최악의 경우인 N=1,000,000인 경우에도 약 500만 번의 연산 내에 문제를 해결할 수 있습니다.

 

에라토스테네스의 체 알고리즘을 이용한 풀이를 코드로 구현하면 다음과 같습니다.

 

 

 

 

 

2. 실제 문제에서 브루트 포스 알고리즘

브루트 포스 알고리즘은 어떤 상황에서 쓰면 될까요?

 

위에서 말씀드렸듯이,

추상적인 알고리즘이기 때문에 구체적으로 쓰이는 상황을 정의하는 것은 어렵습니다.

 

그렇다면, 추상적인 알고리즘이라는 특성을 이용해봅시다.

 

구체적인 상황에서 쓰이지 않지만 추상적이기 때문에,

언제든지 고려해볼 수 있는 알고리즘에 속합니다.

 

예를 들어, 위의 Case2) 경우도 브루트 포스 알고리즘을 사용하여 문제의 답을 구할 수 있었죠?

시간초과가 나긴 하지만 정답을 구해내는 풀이긴 합니다.

 

따라서 실제 문제에선,

문제를 보고 "이 문제가 브루트 포스 알고리즘으로 풀릴까?" 라는 생각을 함으로써

브루트 포스 알고리즘을 이용할 수 있습니다.

브루트 포스 알고리즘으로 풀어도 시간 초과가 나지 않으면 사용하고,

시간 초과가 나면 다른 풀이를 떠올리면 됨.

 

정리하자면,

브루트 포스 알고리즘은 접근 방식에 가까운 알고리즘인 것을 인지하고

문제를 보고 "이 문제가 브루트 포스 알고리즘으로 풀릴까?" 에 대해 생각해봅시다.

브루트 포스 알고리즘 풀이가 시간 초과가 나서 사용할 수 없어도

브루트 포스 알고리즘 풀이가 핵심 아이디어를 찾는 데에 도움을 줌.

 

[관련 문제]

백준 : 블랙잭 (2798번)

백준 : 로또 (6603번)

백준 : 암호 만들기 (1759번)

 

실제 문제에서 브루트 포스 알고리즘의 자세한 내용은 브루트 포스적 사고과정 글을 참고하시기 바랍니다.

브루트 포스적 사고과정 글은 추후에 작성하여 올리겠습니다.

 

 

 

 

---

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차 : https://gliver.tistory.com/7