문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는 방법
직관적이고 간단하지만 하나씩 경우의 수를 체크하므로 비효율적일 수 있다.
특징
단순함 : 복잡한 알고리즘을 이해하지 않고도 쉽게 구현할 수 있으며, 문제를 해결하는 데 있어서 모든 경우의 수를 고려하기 때문에 매우 직관적이다.
포괄적 탐색 : 가능한 모든 경우를 시도하기 때문에 해답이 반드시 존재한다면 이를 놓치지 않고 찾을 수 있다.
비효율성 : 모든 경우를 탐색하기 때문에 경우의 수가 많아질수록 수행 시간이 급격히 증가할 수 있으므로, 입력 크기가 큰 경우 실행 시간이 매우 길어진다.
시간복잡도 : 일반적으로는 문제가 요구하는 반복 횟수나 탐색 대상의 크기에 따라 결정되며, 많은 경우 시간복잡도는 O(n), O(n^2), O(n^3) 등으로 표현된다.
예시
예를 들어, 자연수 N의 가장 작은 생성자를 구하는 문제에서는 다음과 같이 브루트 포스 접근법을 사용할 수 있습니다.
-
모든 경우를 고려: N의 생성자가 될 수 있는 모든 자연수 M(1 ≤ M ≤ N)을 하나씩 시도합니다.
-
조건 검사: 각 M에 대해, M과 M의 각 자릿수의 합이 N과 같아지는지 확인합니다.
-
정답 출력: 가장 먼저 조건을 만족하는 M을 찾으면 그것이 가장 작은 생성자입니다.
이 방법은 가능한 모든 경우를 시도하여 정답을 찾는 방식으로, 이를 브루트 포스 알고리즘이라고 합니다.
