코테 준비를 다시 시작해보자- 재귀적 탐색

Anny·2024년 12월 24일

https://school.programmers.co.kr/learn/courses/30/lessons/12982

0. 문제

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

function solution(d, budget) {
  const list = d.sort((a, b) => a - b);
  let count = 0;

  for (let i = 0; i < list.length; i++) {
    if (budget >= list[i]) {
      budget -= list[i];
      count += 1;
    } else {
      break;
    }
  }

  return count;
}

console.log(solution([1, 3, 2, 5, 4], 9));

문제를 풀던 도중, 오름차순 정렬 -> 전체에서 오름차순으로 정렬 된 배열의 인덱스 0번 부터 전체 수가 음수가 되기 전 까지 차감의 로직을 사용하면 해결이 가능하단 규칙을 발견해서 문제를 풀었습니다.

하지만 문제 자체로 봤을 때, 최적해를 찾아내 해결하는 방법을 의도한 것 같아 재귀적 탐색을 공부해보았습니다.

1. 전체 코드

function findCombinations(d, target) {
    const results = [];

    function backtrack(start, currentCombination, currentSum) {
        // 현재 합이 목표와 같으면 조합을 결과에 추가
        if (currentSum === target) {
            results.push([...currentCombination]);
            return;
        }
        // 현재 합이 목표를 초과하면 종료
        if (currentSum > target) {
            return;
        }

        // 각 부서의 금액을 탐색
        for (let i = start; i < d.length; i++) {
            currentCombination.push(d[i]); // 현재 금액 추가
            backtrack(i + 1, currentCombination, currentSum + d[i]); // 다음 금액 탐색
            currentCombination.pop(); // 백트래킹: 마지막 금액 제거
        }
    }

    backtrack(0, [], 0);
    return results;
}

// 예시 사용
const d = [1, 3, 2, 5, 4];
const target = 9;
const combinations = findCombinations(d, target);
console.log(combinations); // 출력: [[5, 4], [3, 2, 4]]

2. 로직 분석

1. 조합 탐색

for (let i = start; i < d.length; i++) {
        currentCombination.push(d[i]);
        backtrack(i + 1, currentCombination, currentSum + d[i]);
        currentCombination.pop();
    }

for 루프를 통해 배열 d의 각 금액을 탐색합니다.
현재 금액 d[i]를 currentCombination에 추가하고, currentSum에 더합니다.
다음 호출에서 start 인덱스를 i + 1로 설정하여 중복 조합을 방지합니다.
재귀 호출이 끝난 후, 마지막에 추가한 금액을 currentCombination에서 제거합니다.

2. 종료 조건 1: 목표 금액에 도달했을 시

if (currentSum === target) {
    results.push([...currentCombination]);
    return;
}

현재 합계가 목표 금액과 같으면, 현재 조합을 결과에 추가합니다.

3. 종료 조건 2: 목표 금액을 초과했을 시

if (currentSum > target) {
    return;
}

현재 합계가 목표 금액을 초과하면, 더 이상 탐색할 필요가 없으므로 함수를 종료합니다.

3. 예제 작동 순서

예제 입력

부서의 신청 금액 배열: [1, 3, 2, 5, 4]
목표 금액: 9

작동 순서

초기화: findCombinations 함수가 호출되면, results 배열이 초기화되고 backtrack 함수가 호출됩니다. 초기 인자는 start = 0, currentCombination = [], currentSum = 0입니다.
첫 번째 호출: backtrack(0, [], 0)에서 시작합니다.
- 금액 1을 선택하여 currentCombination이 [1], currentSum이 1이 됩니다.
- 다음 호출: backtrack(1, [1], 1)
두 번째 호출: backtrack(1, [1], 1)에서 금액 3을 선택합니다.
- currentCombination이 [1, 3], currentSum이 4가 됩니다.
- 다음 호출: backtrack(2, [1, 3], 4)
세 번째 호출: backtrack(2, [1, 3], 4)에서 금액 2를 선택합니다.
- currentCombination이 [1, 3, 2], currentSum이 6이 됩니다.
- 다음 호출: backtrack(3, [1, 3, 2], 6)
네 번째 호출: backtrack(3, [1, 3, 2], 6)에서 금액 5를 선택합니다.
- currentSum이 11이 되어 목표 금액을 초과하므로 이 경로는 종료됩니다.
- 백트래킹하여 2를 제거하고 backtrack(3, [1, 3], 4)로 돌아갑니다.
계속 탐색: 이 과정을 반복하여 모든 조합을 탐색합니다. 최종적으로 currentCombination이 [5, 4]와 [3, 2, 4]일 때 currentSum이 9가 되어 결과에 추가됩니다.