브루트포스 알고리즘(Bruteforcing)

브루트포스 알고리즘(Bruteforcing)

• 가능한 모든 경우의 수를 탐색 -> 100%의 정확성 but 높은 시간복잡도
• 시간 복잡도 파악이 중요하다. <- 시간초과 문제
• for문, 재귀, 등 사용

 

브루트포스 알고리즘 사용조건

• 문제에서 달성하고자 하는 솔루션이 정의되어 있다.
• 문제를 해결할 수 있는 풀이의 수가 제한되어 있다. <- 솔루션 수가 무한하거나 너무 크면 효율적X

 

브루트포스 종류

• 선형 구조: 순차 탐색
• 비선형 구조: 백트래킹, DFS, BFS

 

브루트포스의 활용

• 문자열 처리: 문자열의 모든 부분 문자열 생성, 탐색
• 조합(combination) 생성: 주어진 집합의 모든 부분집합을 생성, 탐색
• 완전 탐색: 작은 입력 크기에서 모든 가능한 경우 탐색

 

BOJ - #브루트포스 알고리즘