[프로그래머스] JavaScript Lv2 - 타겟 넘버(43165)

개요

문제 이름: 타겟 넘버 (43165)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165
플랫폼: 프로그래머스
알고리즘 분류: 깊이/너비 우선 탐색(DFS/BFS)
소요 시간: 5시간

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 주어진 숫자들을 더하거나 빼서 특정 타겟 넘버를 만드는 모든 방법의 수를 찾는 것입니다. 이는 전형적인 깊이 우선 탐색(DFS) 또는 재귀를 사용하는 문제입니다.

 

문제 접근 방식

• 각 숫자에 대해 더하거나 빼는 두 가지 선택지가 있습니다.
• 모든 숫자에 대해 이 선택을 수행하고, 마지막에 결과가 타겟 넘버와 일치하는지 확인합니다.
• 일치하는 경우의 수를 세어 반환합니다.

 

문제 지시 사항

• 주어진 숫자 배열의 각 요소를 더하거나 빼서 타겟 넘버를 만드는 모든 경우의 수를 구하세요.
• 숫자의 순서는 바꿀 수 없습니다.
• 각 숫자는 반드시 더하거나 빼야 합니다 (건너뛰기 불가).

 

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이 우선 탐색 (Depth-First Search, DFS)

DFS는 그래프나 트리 구조에서 가능한 한 깊이 들어가면서 탐색을 진행하는 알고리즘입니다. '타겟 넘버' 문제에서 DFS는 매우 적합한 방법입니다.

 

DFS의 특징

• 재귀적으로 구현하기 쉽습니다.
• 메모리 사용량이 비교적 적습니다.
• 해를 찾을 때까지 깊이 탐색합니다.

 

DFS 예시

// numbers = [1, 1, 1, 1], target = 2
		0
   /       \
  +1        -1
 /   \     /   \
+2    0   0    -2

// DFS 구현
function dfs(numbers, target, index, sum) {
    if (index === numbers.length) {
        return sum === target ? 1 : 0;
    }
    return dfs(numbers, target, index + 1, sum + numbers[index]) +
           dfs(numbers, target, index + 1, sum - numbers[index]);
}

function solution(numbers, target) {
    return dfs(numbers, target, 0, 0);
}

 

'타겟 넘버' 문제에서의 DFS 적용

• 각 숫자에 대해 더하기와 빼기 두 가지 선택을 합니다.
• 한 선택을 한 후, 다음 숫자로 즉시 이동합니다.
• 모든 숫자를 사용할 때까지 이 과정을 반복합니다.
• 마지막 숫자까지 도달하면 결과를 확인하고 백트래킹합니다.

 

너비 우선 탐색 (Breadth-First Search, BFS)

BFS는 현재 위치에서 가까운 곳부터 탐색하는 알고리즘입니다. '타겟 넘버' 문제는 BFS로도 해결할 수 있지만, DFS에 비해 구현이 조금 더 복잡합니다.

BFS의 특징

• 큐(Queue)를 사용하여 구현합니다.
• 메모리 사용량이 많을 수 있습니다.
• 최단 경로 문제 해결에 유용합니다.

 

예시

// numbers = [1, 1, 1], target = 1
Level 0:    [0]
Level 1:   [1, -1]
Level 2: [2, 0, 0, -2]
Level 3: [3, 1, 1, -1, 1, -1, -1, -3]

// BFS 구현
function solution(numbers, target) {
    let queue = [0];
    for (let i = 0; i < numbers.length; i++) {
        let levelSize = queue.length;
        let nextQueue = [];
        for (let j = 0; j < levelSize; j++) {
            let sum = queue[j];
            nextQueue.push(sum + numbers[i]);
            nextQueue.push(sum - numbers[i]);
        }
        queue = nextQueue;
    }
    return queue.filter(sum => sum === target).length;
}

 

 

'타겟 넘버' 문제에서의 BFS 적용

• 각 레벨(숫자의 인덱스)에서 가능한 모든 합계를 큐에 저장합니다.
• 다음 레벨로 이동할 때마다 이전 레벨의 모든 경우의 수를 고려합니다.
• 마지막 레벨에 도달하면 타겟 넘버와 일치하는 경우의 수를 세어 반환합니다.

 

DFS와 BFS 비교

• 메모리 사용
  • DFS: 재귀 호출 스택 깊이만큼의 메모리 사용 (O(n), n은 numbers의 길이)
  • BFS: 마지막 레벨에서 최대 2^n개의 요소를 저장 (O(2^n))
• 시간 복잡도
  • 둘 다 모든 가능한 경우를 탐색하므로 O(2^n)
• 구현 난이도
  • DFS: 재귀를 사용하여 비교적 간단하게 구현 가능
  • BFS: 큐를 사용하여 구현하며, 레벨 관리가 필요해 조금 더 복잡
• 문제 적합성
  • '타겟 넘버' 문제의 경우, 모든 숫자를 사용해야 하므로 DFS가 더 직관적이고 효율적

 

결론

'타겟 넘버' 문제에서는 DFS가 더 적합한 해결 방법입니다. DFS는 구현이 간단하고 메모리 사용이 효율적이며, 문제의 특성(모든 숫자를 사용해야 함)에 잘 맞습니다. 하지만 BFS로도 해결할 수 있기는 합니다.

 

시도

1차 시도 (성공)

function solution(numbers, target) {
    let count = 0;  // 타겟 넘버를 만드는 방법의 수

    function dfs(index, sum) {
        // 모든 숫자를 사용했을 때
        if (index === numbers.length) {
            // 합계가 타겟과 일치하면 카운트 증가
            if (sum === target) {
                count++;
            }
            return;
        }

        // 현재 숫자를 더하는 경우
        dfs(index + 1, sum + numbers[index]);
        // 현재 숫자를 빼는 경우
        dfs(index + 1, sum - numbers[index]);
    }

    dfs(0, 0);  // 초기 호출: 인덱스 0, 합계 0에서 시작
    return count;
}

이 코드는 DFS를 사용한 재귀적 접근 방식입니다.

1. count 변수를 초기화하여 타겟 넘버를 만드는 방법의 수를 저장합니다.
2. dfs 함수를 정의합니다.
   1. index: 현재 처리 중인 숫자의 인덱스
   2. sum: 현재까지의 합계
3. 조건: 모든 숫자를 사용했을 때(index === numbers.length)
   1. 현재 합계(sum)가 타겟과 일치하면 count를 증가시킵니다.
4. 재귀 호출
   1. 현재 숫자를 더하는 경우: dfs(index + 1, sum + numbers[index])
   2. 현재 숫자를 빼는 경우: dfs(index + 1, sum - numbers[index])
5. 초기 호출 dfs(0, 0)로 재귀를 시작합니다.
6. 최종적으로 count를 반환합니다.

시간 복잡도: O(2^n), 여기서 n은 numbers 배열의 길이입니다. 각 숫자에 대해 2가지 선택(더하기 또는 빼기)을 하므로, 총 2^n개의 경우의 수를 탐색합니다.

공간 복잡도: O(n), 재귀 호출 스택의 최대 깊이가 numbers 배열의 길이와 같기 때문입니다.

 

2차 시도 (성공)

function solution(numbers, target) {
    // 기저 조건: 모든 숫자를 사용했을 때
    if (numbers.length === 0) {
        // 타겟 값에 도달했으면 1 반환, 아니면 0 반환
        return target === 0 ? 1 : 0;
    }
    
    // 재귀 호출:
    // 1. 현재 숫자를 더하는 경우
    // 2. 현재 숫자를 빼는 경우
    return solution(numbers.slice(1), target - numbers[0]) + 
           solution(numbers.slice(1), target + numbers[0]);
}

이 코드는 더 간결한 재귀적 접근 방식을 사용합니다.

• 조건: numbers 배열이 비어있을 때
• target이 0이면 유효한 경우이므로 1을 반환, 아니면 0을 반환합니다.
• 재귀 호출
  • 현재 숫자(numbers[0])를 더하는 경우: solution(numbers.slice(1), target - numbers[0])
  • 현재 숫자를 빼는 경우: solution(numbers.slice(1), target + numbers[0])
  • 두 경우의 결과를 더해서 반환합니다.

이 방식은 target을 조정하면서 재귀 호출을 합니다. 마지막에 target이 0이 되면 유효한 경우입니다.

 

시간 복잡도: O(2^n), 첫 번째 시도와 동일합니다.

공간 복잡도: O(n), 재귀 호출 스택의 최대 깊이가 numbers 배열의 길이와 같습니다. 하지만 slice 메서드로 인해 추가적인 공간이 사용될 수 있습니다.

 

사용된 메서드

• slice(start, end): 배열의 일부를 새로운 배열 객체로 반환합니다. start부터 end 전까지의 요소를 포함합니다. end를 생략하면 배열의 끝까지 포함합니다.
  [예시] array.slice(1) - 첫 번째 요소를 제외한 나머지 모든 요소를 포함하는 새 배열을 반환합니다.