브루트포스 알고리즘
: 무식하게 전부 다 시도해보는 방식. 가능한 모든 경우를 일일이 확인하면서 정답을 찾는 방식
✅ 브루트포스 알고리즘의 특징
- 방식: 모든 경우를 하나하나 다 탐색해서 답을 찾음
- 장점
- 구현이 간단하다.
- 정답을 확실히 찾을 수 있다.
- 단점
- 시간이 오래 걸린다. (비효율적)
- 입력이 커지면 시간 초과 발생 가능
- 사용 예시
- 조합, 순열, 패턴 찾기
- 범위가 작거나, 최적화보다 확실한 정답이 중요한 문제
✅ 언제 사용하면 좋은가?
- 입력 범위가 작고 (N ≤ 1,000, N ≤ 10,000 정도)
- 가능한 모든 경우의 수를 따져도 시간이 충분할 때
✏️ 요약
브루트포스는 단순하지만 강력한 접근 방식.
"될지 안 될지 모르니까 전부 다 해본다"는 마인드로, 경우의 수가 작을 때는 오히려 최적의 선택이 될 수 있다.
✔️ 브루트 포스 구현 방식
브루트 포스 = 탐색 방식에 대한 아이디어
- 구현 방식
- 단순 반복문
: 가능한 경우를 모든 for/while문으로 돌려보는 가장 기본적인 방식
: 예) 1~1000 중 3의 배수 찾기 - 중첩 반복문
: 2중, 3중 반복문을 통해 가능한 조합을 모두 탐색
: 예) 체스판 문제, 암호 조합 찾기 - 순열
: n개의 원소 중에서 r개를 순서를 고려해 나열한 모든 경우를 시도
: 예) 숫자 자리를 바꿔 최댓값 만들기 - 조합
: n개 중 r개를 순서 없이 뽑는 모든 경우를 시도
: 예) 로또 번호 만들기 - 부분 집합
: 집합의 모든 부분 집합을 고려해서 탐색
: 예) 특정 합을 만족하는 부분 집합 찾기 - DFS (깊이 우선 탐색)
: 그래프/트리 구조 또는 상태공간을 깊게 탐색하면서 경우를 시도
: 미로 탐색, 경로 찾기 - BFS (너비 우선 탐색)
: DFS와 유사하지만, 더 넓게 퍼지면서 경우를 시도
: 예) 최소 이동 횟수 찾기 - 백트래킹 (Backtracking)
: 가지치기를 하면서 불필요한 탐색은 중단하며 가능한 경우만 탐색
: 예) N-Queen 문제, 스도쿠 - 비트 마스킹
: 집합의 포함/제외 여부를 비트로 표현해서 빠르게 부분 집합 탐색
: 예) 2^n 경우의 수를 비트로 처리
- 단순 반복문
