[프로그래머스] 타겟 넘버 (Lv. 2 JavaScript)

📝 문제 설명

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

프로그래머스

목표: n개의 음이 아닌 정수가 주어지면, 이 정수들를 더하거나 빼서(순서를 바꾸지 않고) 주어진 타겟 넘버를 만들 수 있는 경우의 수를 반환해야한다.

핵심 조건:

• 주어지는 숫자의 개수 n은 2 이상 20 이하이다.
• 각 숫자는 1 이상 50 이하의 자연수
• 타겟 넘버는 1 이상 1000 이하의 자연수
• 주어진 숫자 배열의 순서는 바꾸지 않는다.

---

🔍 풀이 과정 (나만의 풀이 전략)

주어진 숫자 배열의 순서를 바꾸지 않고 주어진 숫자를 더하거나 빼서 타겟 넘버를 만드는 경우의 수를 구해야 한다.

이는 매 단계마다 두 가지 선택지가 있음을 의미한다.

1. 현재 숫자를 더하거나 (+)
2. 현재 숫자를 빼거나 (-)

두 가지 선택지가 매 단계마다 반복되므로 이를 시각화하면 이진 트리 형태로 나타낼 수 있다.

루트 노드인 0부터 시작해서 주어진 숫자의 개수만큼 depth를 내려가며 모든 합산 결과를 탐색하는 DFS 알고리즘을 적용할 수 있다. 예를 들어, numbers = [4, 1, 2, 1], target = 4 일 때의 트리 구조는 아래와 같이 모든 숫자를 다 사용할 때까지 뻗어나간다.

[Depth 0]                      0 (시작)
                            /     \
[Depth 1]                +4         -4
                        /  \       /  \
[Depth 2]             +1    -1   +1    -1
                     / \    / \  / \   / \
[Depth 3]           +2 -2  +2 -2 ...  ...
                   / \
[Depth 4]         +1  -1  <- 이 상태(Leaf Node)에서 최종 합산 값이 target과 같은지 체크

• 트리의 깊이(depth)는 현재까지 연산에 사용한 숫자의 개수를 의미
• 탐색 종료 조건은 depth가 주어진 숫자 배열의 크기와 동일할 경우 (모든 숫자를 다 사용)
• answer 카운트 증가 조건은 종료 조건에 도달 했을 때 최종 합산이 target과 동일한지에 따라

주어진 숫자를 현재 총 합산 값에 더하는 경우와 빼는 경우를 재귀 함수를 통해 호출하게 한다. 근데 이게 왜 그런지를 설명 못하겠네 예시에 대해서 직접 트리 그림으로 설명한다면 좋을텐데

아래는 트리에서 내려가면서 더하고 뺀 합산 값을 적은 트리 좌측 노드로 내려간다면 +, 우측 노드로 내려가면 -를 한다.

이 때 depth가 숫자 배열의 크기만큼의 깊이 즉, 주어진 숫자를 다 사용하였고, current의 값이 타겟 넘버와 동일하다면 answer 값을 증가시킨다.

이런식으로 재귀를 통해 트리를 구성하면 정답을 찾을수 있다.

[Depth = 0]                   0
[Depth = 1]              1        -1
[Depth = 2]         2        
[Depth = 3]      3 (target넘버와 동일하나 depth가 조건을 충족 X)      
[Depth = 4]    4   2  
[Depth = 5]  5  3 (조건 만족 answer++)

실제 코드 구현은 아래와 같이 진행하였음.

    let current = 0;
    const permutation = (current, depth) => {
        if (numbers.length < depth) return;
        if ((numbers.length === depth) && (current === target)) {
            answer++;
        }
        const number = numbers[depth] === undefined ? 0 : numbers[depth];

        permutation(current + number, depth + 1);
        permutation(current - number, depth + 1);

    }
    permutation(current, 0);

permutation(current, depth) 함수는 DFS 알고리즘을 기반으로 하며, 이진 트리에서 leaf node까지 탐색을 완료했다면 다시 위로 올라가는 재귀적 구조이다.

1. 이진 트리의 분기
   매 호출마다 현재 깊이의 주어진 배열의 숫자를 총합(current)에 더하는 경우(+)와 빼는 경우(-)의 두 갈래로 나뉘며 permutation 을 재귀 호출한다. 이는 이진 트리에서 왼쪽 자식 노드와 오른쪽 자식 노드로 깊어지며 탐색하는 DFS 동작과 같다.
2. 조건 검사와 탐색 종료
   depth 가 numbers.length 와 같다는 것은 주어진 숫자 배열의 원소들을 모두 탐색에 사용했다는 의미이며 이진 트리에서 바닥 노드 (leaf node)에 도달했다는 것을 의미하기도 한다.
   이 때 최종 누적된 current 의 값이 target 과 같은지를 검사한다. 만약 같다면 answer 의 값을 1 증가시킨다.
   조건을 만족하든 하지 않든 리프 노드에 도달했다면 해당 분기의 탐색은 종료되며, 함수가 반환되면서 이전 갈림길 부모 노드로 돌아가게 된다. (백트래킹)

마지막으로 처음 호출한 permutation(current, 0) 가 종료되었다는 것은 이진 트리에 대한 DFS 탐색이 최종 완료되었음을 의미한다. 이 과정에서 current와 타겟 넘버가 같을 경우에 answer 값을 증가 시키기 때문에 이진 트리에 대한 탐색이 완료되면 결과 값을 알 수 있는 것이다.

🛠️ 트러블슈팅

function solution(numbers, target) {
    var answer = 0;
    let current = 0;
    
    const permutation = (current, depth) => {
        if (numbers.length === depth) {
            return ;
        }
        const number = numbers[depth];
        permutation(current + number, depth + 1);
        permutation(current - number, depth + 1);

        console.log(`추출: ${number}, 현재: ${current}, 깊이: ${depth}, 결과: ${answer}`)
        if ((numbers.length > depth) && (current + number === target) || (current - number === target)) {
            answer++;
        }

    }
    
    permutation(current, 0);
    
    
    return answer;
}

초기 시도에서 있었던 문제점은 탐색이 끝나지 않은 시점에서도 (depth가 배열크기보다 작다면) 타겟 넘버와 일치하는 지 검사하고 answer 값을 증가 시켜 잘못 구현하여 문제가 있었음.

모든 원소를 사용하는 조합/순열이나 DFS 문제에서는 반드시 최종 깊이에 도달했을 때 결과를 확인해야 한다는 점을 인지하지 못한 문제였다.

또한, 최종 타겟 넘버 체크 로직에서 불필요하게 current +- number 와 같은 조건을 걸었는데, 애초에 permutation을 재귀적으로 호출 할때 current 값에 number를 더해 인자로 넘겨주기에 굳이 이렇게 검사할 필요가 없었다.

---

💻 코드 (Code)

function solution(numbers, target) {
    var answer = 0;
    let current = 0;
    
    const permutation = (current, depth) => {
        if (numbers.length < depth) return;
        if ((numbers.length === depth) && (current === target)) {
            answer++;
        }
        const number = numbers[depth] === undefined ? 0 : numbers[depth];
        
        permutation(current + number, depth + 1);
        permutation(current - number, depth + 1);

    }
    
    permutation(current, 0);
    
    
    return answer;
}

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습

DFS의 구현 방법

DFS를 구현하는 방법은 크게 두 가지가 있다.

1. 재귀 함수: 시스템 스택을 이용하는 방법
2. 명시적 스택: Array 나 Stack 자료구조를 직접 선언하여 반복문으로 구현하는 방법

이번 문제에서 사용한 것 처럼 재귀함수로 구현하는 방법은 컴퓨터 내부적으로 스택 메모리 구조를 사용한다. 함수가 호출될 때마다 메모리에 쌓아두고 return을 만나면 다시 쌓아둔 메모리 주소로 돌아가 하나씩 빠져나오는 원리이다. 이를 코드 상으로 명시적으로 그대로 가져오면 직접 const stack = [] 과 같이 만들고 while 문을 돌리는 방식으로 DFS를 구현할 수 있다.

재귀 함수 구현의 경우 재귀가 너무 깊어지면 일반적인 JS 기준 1만번 이상 일경우 스택 오버플로우가 발생할 수 있다. 명시적 스택의 경우 메모리 제한이 시스템 스택에 비해 널널하다. 탐색해야 할 데이터가 방대하고 깊이가 극단적으로 깊을 때 사용한다.

트리 DFS vs 그래프 DFS

자료 구조의 형태에 따라 DFS의 디테일한 점이 달라진다. 트리는 그래프의 한 종류로 모든 트리는 그래프이지만 결정적인 차이는 사이클(순환 경로)가 존재하는지 (이미 방문한 곳을 다시 방문할 수 있는가?) 이다.

1. 트리에서의 DFS

   // 주어진 데이터(array)를 바탕으로 깊이(depth)를 제어하며 탐색
   function treeDFS(depth, currentResult, array) {
       // 1. Base Case: 트리의 가장 바닥(Leaf Node)에 도달했을 때 (종료 조건)
       if (depth === array.length) {
           // 결과 처리 로직 (최종 값 비교, 정답 카운트 등)
           return;
       }
   
       // 2. Recursive Case: 갈라지는 선택지(자식 노드들)를 각각 호출
       // 예: 선택지 A를 고르고 다음 깊이로 이동
       treeDFS(depth + 1, currentResult + array[depth], array);
       
       // 예: 선택지 B를 고르고 다음 깊이로 이동
       treeDFS(depth + 1, currentResult - array[depth], array);
   }
   

   특징: 부모에서 자식으로만 내려가는 일방 통행 수직 구조이다. 사이클이 없으므로 이미 방문한 노드를 기억할 필요가 없다. 즉, visited 배열이 불필요하다.
2. 그래프에서의 DFS

   // graph: 각 노드의 연결 관계를 담은 2차원 배열/인접 리스트
   // node: 현재 방문한 노드 번호
   // visited: 방문 여부를 체크하는 불리언 배열 [false, false, ...]
   function graphDFS(node, graph, visited) {
       // 1. 현재 노드를 방문 처리
       visited[node] = true;
       
       // 필요한 비즈니스 로직 수행 (ex. 카운트 증가, 노드 출력 등)
   
       // 2. 현재 노드와 연결된 인접 노드들을 하나씩 확인 (반복문)
       for (let i = 0; i < graph[node].length; i++) {
           const nextNode = graph[node][i];
   
           // 3. 아직 방문하지 않은 인접 노드가 있다면 해당 노드로 더 깊이 탐색 (재귀)
           if (!visited[nextNode]) {
               graphDFS(nextNode, graph, visited);
           }
       }
   }
   

   특징: 탐색하다가 이전에 방문했던 노드로 다시 돌아가는 무한 루프에 빠질 수 있기 때문에 방문 여부를 반드시 확인해야한다. 즉, visited 배열이 필수

꼬리질문

Q1. 만약 N의 개수가 50개 이상으로 커진다면 이 풀이(DFS)를 그대로 사용할 수 있을까요?

• 결론은 불가능하다. 이번 문제의 시간 복잡도를 계산해보면 매 숫자마다 더하기, 빼기 두가지 선택지가 주어진다. 숫자의 총 개수를 N 개라고 했을 때, 총 선택의 가짓수는 2^N이 된다. 따라서 시간 복잡도는 O(2^N)이 된다. 이 문제에서는 N의 최대값이 20이기 때문에 2^20 = 약 100만번의 연산이 수행되어 DFS로 충분히 통과가 가능하다.
• 하지만 N의 개수가 50개 이상으로 커진다면, 2^50은 대략 10^15를 넘어서기 때문에 시간 초과가 발생하게 된다.

---

💬 마무리하며

저번 문제에 이어 DFS 문제에 마주했는데 스스로 힘으로 해결하진 못했고 AI에게 약간의 힌트를 받아서 현재 구조를 생각해내어 구현을 진행했습니다. 이번에 문제를 풀이하고 복습을 진행하면서 DFS 문제를 만났을 때 어떻게 접근하면 좋을지에 대해 생각해볼 수 있었던 것 같습니다. 다음에는 완전 스스로 힘으로 풀이 가능하기를 바라면서! 앞으로도 파이팅입니다!

 

본 게시물은 AI의 도움을 받아 작성되었습니다.