브루트포스(Brute Force) 알고리즘

✒️ 브루트포스(Brute Force) 알고리즘

• 가능한 모든 경우의 수를 탐색하여 정답을 찾는 방법
• 특별한 최적화 기법이나 자료구조 없이 모든 경우를 하나씩 시도해 보는 것

✒️ 동작 원리

1. 문제의 모든 가능한 조합이나 경우를 나열
2. 각 경우를 차례대로 확인하며 조건을 만족하는지 검사
3. 정답을 발견하면 반환하거나 모든 조건을 검사한 후 답을 도출

✒️ 장단점

장점

특별한 알고리즘을 배우지 않아도 바로 사용 가능
최적화된 알고리즘이 없더라도 정답을 보장

단점

탐색 공간이 커지면 시간복잡도가 증가해 일정 시간 내에 문제를 풀기 어려움

✒️ 사용 시기

문제의 입력 크기가 작을 때

✒️ 입력 크기의 기준은?

1. 순열

• 입력 크기 : n <= 10
• n개의 원소로 순열을 만드는 경우, 경우의 수는 n!로 증가
  • n=10, 10!=3,628,800 (가능)
  • n=11, 11!=39,916,800 (탐색 기간 급격하게 길어짐)

2. 조합

• 입력 크기 : n <= 20
• n개의 원소에서 k개를 고르는 조합의 경우의 수
  - n=20, k=10 => 184,756 (가능)

3. 부분 집합 구하기

• 입력 크기 : n <= 20
• 부분 집합의 개수는 2^n
  • n=20, 2^20=1,048,576 (조금 느려질 수 있음)

3중 루프 탐색

• 입력 크기 : n <= 100
• n개의 원소를 3중 루프로 탐색하는 경우 시간 복잡도는 O(n^3)
  • n=100, 100^3=1,000,000 (한계)

문자열 매칭

• 입력 크기 : n <= 1,000
• n개의 문자를 갖는 문자열에서 패턴 매칭 시 O(n*m)
  • n=10,000, m=50 => 500,000 (조금 느림)

배열 내 합 계산

• 입력 크기 : n <= 1,000
• n개의 원소에서 부분 합을 계산하는 경우, 시간 복잡도는 O(n^2)
  • n=1,000, 1,000^2 = 1,000,000 (조금 느림)