Brute force 알고리즘 +NP문제

1. 브루트 포스 알고리즘

브루트포스 알고리즘
- 모든 가능한 경우의 수를 탐색하여 문제를 해결하는 방법이다
- 가장 단순하고 직관적인 문제 해결 방식이다
- 완전 탐색이라고도 한다

장점:
- 구현이 쉽고 단순하다
- 확실하게 정답을 찾을 수 있다

단점:
- 시간복잡도가 높다 (대부분 O(n²), O(2ⁿ) 등)
- 데이터가 커지면 시간이 기하급수적으로 증가한다

간단한 예제

// 1. 배열에서 두 수의 합이 target이 되는 조합 찾기
function findTwoSum(arr, target) {
    for(let i = 0; i < arr.length; i++) {
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[i] + arr[j] === target) {
                return [i, j];
            }
        }
    }
    return null;
}

// 사용 예시
const numbers = [2, 7, 11, 15];
console.log(findTwoSum(numbers, 9)); // [0, 1]

// 2. 문자열이 회문(palindrome)인지 확인하기
function isPalindrome(str) {
    for(let i = 0; i < Math.floor(str.length / 2); i++) {
        if(str[i] !== str[str.length - 1 - i]) {
            return false;
        }
    }
    return true;
}

// 사용 예시
console.log(isPalindrome("level")); // true
console.log(isPalindrome("hello")); // false

브루트 포스가 주로 사용되는 경우:
1. 문제의 크기가 작을 때
2. 더 효율적인 알고리즘을 찾기 어려울 때
3. 여러 알고리즘의 결과를 검증할 때
4. 최적화 문제를 해결할 때

실제 코딩테스트나 알고리즘 문제에서 자주 나오는 브루트 포스 유형:
- 순열과 조합 문제
- 부분집합 문제
- 문자열 매칭
- 배열에서 특정 값 찾기

 

2. NP(Nonedeterministic Polynomial time)문제와 브루트 포스

 

np문제란 다항 시간 내에 문제의 해답을 '확인'할 수 있는 문제를 의미한다. 즉 주어진 해의 정답 여부를 다항 시간 내에 판별해 내는 문제이다.

 

NP(Nondeterministic Polynomial time) 문제의 특징:
1. 문제의 해답을 찾는 것은 어렵지만
2. 주어진 해답이 맞는지 검증하는 것은 쉽다 (다항 시간 내 가능)

브루트 포스와 NP 문제의 관계:
- 대부분의 NP 문제는 브루트 포스로 해결할 수 있다
- 하지만 시간복잡도가 지수적으로 증가하여 현실적으로 큰 입력값에서는 사용하기 어렵다

대표적인 NP 문제들과 브루트 포스 접근 예시: 외판원 순회 문제와 부분합 문제

// 외판원 순회 문제(Traveling Salesman Problem)
// graph: 도시 간 거리를 담은 2차원 배열 (인접 행렬)
// 반환값: 모든 도시를 한 번씩 방문하고 돌아오는 최단 거리
function tsp(graph) {
   const n = graph.length; // 도시의 총 개수
   
   // 0번을 제외한 도시 번호 배열 생성 [1, 2, ..., n-1]
   const cities = Array.from({length: n-1}, (_, i) => i + 1);

   // 배열의 모든 순열을 반환하는 함수
   // 예: [1,2,3] -> [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
   function getAllPermutations(arr) {
       if (arr.length <= 1) return [arr];
       return arr.reduce((acc, item, i) => {
           // 현재 숫자를 제외한 나머지 숫자들로 순열을 만들고
           // 현재 숫자를 맨 앞에 붙여서 새로운 순열 생성
           const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
           return acc.concat(
               getAllPermutations(rest).map(p => [item, ...p])
           );
       }, []);
   }

   let minDistance = Infinity;  // 최단 거리를 저장할 변수
   const routes = getAllPermutations(cities);  // 가능한 모든 도시 방문 순서

   // 모든 가능한 경로를 검사
   for (let route of routes) {
       let distance = graph[0][route[0]];  // 시작 도시(0)에서 첫 번째 도시까지의 거리
       
       // 경로 상의 도시들 사이의 거리를 더함
       for (let i = 0; i < route.length - 1; i++) {
           distance += graph[route[i]][route[i+1]];
       }
       
       // 마지막 도시에서 시작 도시(0)로 돌아오는 거리를 더함
       distance += graph[route[route.length-1]][0];
       
       minDistance = Math.min(minDistance, distance);
   }

   return minDistance;
}

// 사용 예시
const graph = [
   [0, 10, 15, 20],   // 0번 도시에서 각 도시까지의 거리
   [10, 0, 35, 25],   // 1번 도시에서 각 도시까지의 거리
   [15, 35, 0, 30],   // 2번 도시에서 각 도시까지의 거리
   [20, 25, 30, 0]    // 3번 도시에서 각 도시까지의 거리
];

console.log(tsp(graph));  // 출력: 80 
// 최단 경로: 0 -> 1 -> 3 -> 2 -> 0 (거리: 10 + 25 + 30 + 15 = 80)
// 시간복잡도는 O(n!)이다. 크기가 커질수록 기하급수적으로 증가한다

 

// 부분합 문제(Subset Sum Problem)
// arr: 숫자 배열
// target: 목표 합계
// 반환값: 부분집합의 합이 target이 되는 경우가 있으면 true, 없으면 false
function subsetSum(arr, target) {
   // 재귀적으로 부분집합의 합을 확인하는 함수
   // index: 현재 검사할 배열의 인덱스
   // sum: 현재까지 선택한 원소들의 합
   function findSubsets(index, sum) {
       // 현재까지의 합이 목표값과 같으면 true 반환
       if (sum === target) return true;
       
       // 배열 끝까지 도달했거나, 현재 합이 목표값을 초과하면 false 반환
       if (index >= arr.length || sum > target) return false;
       
       // 현재 원소를 선택하는 경우를 검사
       // 예: [1,2,3]에서 1을 선택하고 다음 원소로 넘어감
       if (findSubsets(index + 1, sum + arr[index])) return true;
       
       // 현재 원소를 선택하지 않는 경우를 검사
       // 예: [1,2,3]에서 1을 건너뛰고 다음 원소로 넘어감
       if (findSubsets(index + 1, sum)) return true;
       
       // 모든 경우에서 실패하면 false 반환
       return false;
   }
   
   // 첫 번째 원소부터 시작하여 합이 0인 상태에서 시작
   return findSubsets(0, 0);
}

// 사용 예시
const numbers = [2, 4, 6, 8];
const target1 = 10;
const target2 = 15;

console.log(subsetSum(numbers, target1));  // true (2 + 8 = 10 또는 4 + 6 = 10)
console.log(subsetSum(numbers, target2));  // false (어떤 부분집합도 합이 15가 될 수 없음)

// 다른 예시
const numbers2 = [3, 34, 4, 12, 5, 2];
console.log(subsetSum(numbers2, 9));  // true (4 + 5 = 9)
console.log(subsetSum(numbers2, 35)); // false

/*
시간복잡도: O(2ⁿ) - n은 배열의 길이
각 원소를 선택하거나 선택하지 않는 두 가지 경우를 모두 검사
백트래킹(재귀)을 사용하여 모든 가능한 부분집합을 확인
sum > target 조건으로 불필요한 탐색을 줄임

부분합 문제는 NP-Complete 문제의 대표적인 예시로, 입력값이 커질수록 연산 시간이 기하급수적으로 증가
*/

 

 

/*
블랙잭
: 카드의 합이 21을 넘지 않는 한도 내에서 각자가 가진 카드의 합을 최대한 크게 만들면 승리
딜러는 N장의 카드를 랜덤하게 나눠준다. 각 카드에는 양의 정수가 적혀있다.
플ㅔ이어는 3장의 카드를 골라 합을 구한다. 이 합이 M을 초과하지 않는 한도 내에서  가장 큰 수를 만들어야 한다.

입력: 
첫 째 줄에는 카드의 개수 N(3<=N<=100)과 M(10<=N<=300000)이 주어진다
둘 째 줄에는 N장의 카드에 적힌 수가 공백으로 구분되어 주어진다.

출력: 세 카드의 합의 최댓값을 출력한다.

입력예시:
5 21
5 6 7 8 9

출력: 21

주진 카드 중 3장을 선택하는 모든 경우의 수를 탐색하고, 이 중 합이 M이 초과하지 않는 한도 내에서 최댓값을 찾는다.
*/

const N = 5;
const M = 21;
const cards = [5,6,7,8,9];
let answer = 0;

for(let i = 0; i < N; i++) {
    for(let j = i + 1; j < N; j++) {
        for(let k = j + 1; k < N; k++) {
            let sum = cards[i] + cards[j] + cards[k];
            if(sum <= M) {
                answer = Math.max(answer, sum);
            }
        }
    }
}

console.log(answer);    //21

NP 문제의 특징:
1. 입력 크기가 커질수록 계산 시간이 기하급수적으로 증가한다
2. 현재까지 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다
3. 최적해를 찾는 것이 매우 어렵다

실제 개발에서 NP 문제를 다루는 방법:
1. 작은 입력값에 대해서는 브루트 포스 사용
2. 큰 입력값에 대해서는 근사 알고리즘 사용
3. 휴리스틱(발견적) 알고리즘 사용
4. 동적 프로그래밍이나 그리디 알고리즘 등으로 부분 최적해 찾기

NP 문제에서 브루트 포스는 정확한 해답을 보장하지만, 실용적이지 않은 경우가 많아 대부분 다른 최적화 방법들을 함께 고려해야  한다.