브루트 포스

개요

브루트 포스는 모든 경우의 수를 다 해보는 것이다.
(이때, 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간제한을 넘지 않아야 한다.)

단계

브루트포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해 볼 수 있다.
1. 문제의 가능한 경우의 수를 계산해본다.
• 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다.
2. 가능한 모든 방법을 다 만들어본다.
• 하나도 빠짐 없이 만들어야 한다.
• 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다.
3. 각각의 방법을 이용해 답을 구해본다.
• 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다.
• 브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 *방법 1개를 시도해보는데 걸리는 시간
복잡도)가 걸린다.

시간복잡도

O(방법의 수 X 방법 1개의 시간복잡도)