Brute Force Algorithm (무차별 대입 알고리즘) 정리

Brute Force란?

• 문제의 정의와 개념에 기반한 직관적이고 직접적인 해결 방식
• 대부분 문제 설명을 그대로 구현하는 형태

---

장점과 단점

장점

• 적용 범위가 넓고 단순함
• 정렬, 탐색, 행렬 곱, 문자열 매칭 등 중요한 문제에도 사용 가능

단점

• 비효율적인 경우가 많음
• 느려서 실용성이 떨어질 수 있음
• 다른 기법보다 구조적이지 않음

---

Brute Force 주요 기법

1. 최적화 문제 (Optimization Problems)

• 목표: f(x) 값을 최대화하는 x ∈ S 찾기
• 예시: 배열에서 최대값 찾기
• 알고리즘: 배열을 순차 스캔하여 최대값 반환
• 시간복잡도: Θ(n)
• 공간복잡도: Θ(1) (in-place)
• 안정성: 있음

---

2. Generate and Test (생성과 검사)

• 모든 해를 생성하고 조건을 검사
• 예시: 그래프에서 클리크(Clique) 찾기
• 시간복잡도: Θ(2ⁿ)

---

3. Backtracking (백트래킹)

• 제약 조건이 있는 문제에 적합
• 해를 점진적으로 구성하고 조건을 만족하지 않으면 백트랙
• 예시: 미로 찾기
• 시간복잡도: Θ(bᵈ)
• 공간복잡도: Θ(d)
  • b: branching factor
  • d: depth

---

4. Fixing Parameters (매개변수 고정)

• 일부 매개변수를 고정하여 탐색 공간 축소

예시: 책 구매 최적화

• n개의 책을 m개의 서점에서 구매
• 각 책은 여러 서점에서 판매되고 서점마다 우편비가 다름
• 목표: 전체 최소 비용 계산

전략

1. 각 서점에 대해 "사용/사용 안 함" 결정 (2^m 조합)
2. 선택된 서점 내에서 각 책을 가장 저렴한 곳에서 구매
3. 각 조합에 대해 총 비용 계산 후 최솟값 선택

• 시간복잡도: Θ(m × n × 2^m)

---

5. Meet in the Middle (중간에서 만나기)

• 문제의 절반만 탐색하고 나머지는 효율적으로 처리

• 예시: 부분 집합 합 문제 (Subset Sum Problem)

  • 정수 집합 S에서, 어떤 부분 집합의 합이 T가 되는지 확인

• 시간복잡도: Θ(n × 2ⁿᐟ²)

---

사용 가이드라인

적절한 사용 시기

• 프로토타입 개발
• 간단한 문제
• 정답의 정확성이 중요한 경우
• 교육/학습용, 작은 테스트 케이스

기법별 팁

• Generate and Test: 아주 작은 문제에만 사용
• Backtracking: 제약 조건으로 가지치기가 가능할 때
• Fixing Parameters: 일부 매개변수를 고정해 복잡도 감소 가능할 때
• Meet in the Middle: 문제를 절반으로 나눌 수 있을 때

---

대표 예시 문제 1 ) Second Largest in an Array (Optimization)

class Solution {
    int print2largest(int arr[], int n) {
        // code here
        int max= Integer.MIN_VALUE;
        int max2 = max;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>max){
                max2=max;
                max=arr[i];
            }
            else if(arr[i]<max && arr[i]>max2)
            max2=arr[i];
        }
        if(max2==max || max2==Integer.MIN_VALUE)
        return -1;
        return max2;
    }
}

대표 예시 문제 2 )

Problem Description
The problem is to find the maximum sum of a contiguous subarray within a given integer array.For example, given arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4], the optimal subarray is [4, -1, 2, 1], which has the maximum sum of 6.

API
public int maxSubarraySum(int[] arr)

Input

arr: An array, where each element is between -1000 and 1000.

Output:

An integer representing the maximum sum of a contiguous subarray.

Constraint

The input size N:  1 ≤ N ≤ 100

Main method for Test

public class Test {

    public static void main(String[] args) {

        Itm itm = new Itm();

        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        System.out.println(itm.maxSubarraySum(arr)); // Expected output: 6

    }
}

Solution

public class Itm {

  public int maxSubarraySum(int[] arr) {

    int maxSum = 0;

    for (int i = 0; i < arr.length - 1; i++) {
      int currentSum = 0;
      for (int j = i + 1; j < arr.length; j++) {
        currentSum += arr[j];
        if (currentSum > maxSum) {
          maxSum = currentSum;
        }
      }
    }

    return maxSum;
  }
}