( ु ´͈ ᵕ `͈ )ु JS:: 코딩테스트를 위한 완전탐색과 탐욕법

완전 탐색과 탐욕법은 몇 번 사용해보면 다른 매커니즘을 통해 돌아가지만,

사실 코딩테스트 학습 초반에는 꽤나 헷갈렸던 알고리즘이다.

 

어떤 경우에 사용하는지 간단하게 정리해보겠다.

 

완전탐색(Brute Force)

완전탐색은 왜 Brute Force(무자비한 힘)일까?

이 방법이 무차별 공격처럼 가능한 모든 경우를 하나하나 시도하기 때문이다.
이러한 무식한 방법 때문에 Brute(야수, 잔인한)라는 단어가 사용되었다.
힘으로 밀어붙이는 상황처럼, 가능한 모든 경우를 다 시도해본다는 의미에서 파생되었다.

직관적이고 단순하지만 비효율적일 수 있다.

 

이 알고리즘은, 미로 안에서 출구를 찾기 위해 모든 길을 가보는 것과도 같다.

모든 경로를 시도하며 출구를 찾게되면, 반드시 출구를 찾겠지만 시간이 많이 걸릴 수 있다.

 

조합 문제
  - 예) 여러 개의 숫자 중 3개의 숫자를 선택해 그 합이 0이 되는 조합을 찾기

퍼즐 문제
  - 예) 퍼즐의 모든 배치를 시도해 정답을 찾는 문제

// 세 개의 숫자를 선택해 그 합이 0이 되는 경우의 수
function findTriplets(arr) {
    let count = 0;
    const n = arr.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] === 0) {
                    count++;
                }
            }
        }
    }
    return count;
}

console.log(findTriplets([-2, 3, 0, 2, -5])); // 결과: 2

---

탐욕법(Greedy Algorithm)

매 순간 최적이라고 생각되는 선택을 해 문제를 해결하는 방법

현재 상황에서 가장 좋아 보이는 선택을 하며 문제를 해결한다.
이러한 선택이 최종적으로 최적의 해결책을 보장할 수 있을 때 사용한다.

 

이 알고리즘은 마치 산에 오를 때, 현재 위치에서 가장 높은 곳으로만 이동하는 것과 같다.

빠르게 정상에 오를 수 있지만, 항상 최적의 경로가 되는 것은 아니다.

 

따라서 근시안적으로 최선의 선택을 하며 전체적으로 최적의 해결책을 찾을 때 사용한다.

 

거스름돈 문제
  - 예) 가장 큰 단위의 동전부터 차례로 거슬러줌

최소 비용 문제
  - 예) 문제를 해결하는 과정에서 항상 현재 가장 저렴한 비용을 선택함

---

두 알고리즘의 차이

 

	완전탐색	탐욕법
시간복잡도	n이 많을수록 기하급수적 상승	일반적으로 더 빠르지만, 항상 최적의 해결책을 보장하지 않음
사용 조건	n의 크기가 작을 때	각 선택이 무조건적으로 최적의 해결책을 보장할 때
예시	숨겨진 보물을 찾기 위해 모든 경로 탐색	높은 곳에서 더 높은 곳으로 정상 오르기