[프로그래머스/JavaScript] 타겟 넘버 (Feat. DFS.. 재귀함수.. 너 뭔데)

 

이 문제를 처음 봤을 때에는 어떻게 접근해야 할지 도무지 감이 오지 않았습니다.

DFS, BFS를 제 손으로 구현해본 적이 없었기에 더욱 주춤하게 되는 문제였는데요.

문제를 풀어낸 과정에 대해 블로그 글로 정리하고자 합니다.

 

1. 무지성으로 들이대기

function solution(numbers, target) {
    var answer = 0;
    
    // 1. total (numbers 합계) 구하기    
    const total = numbers.reduce((accVal, curVal) => {
        return accVal + curVal;
    })
    
    // 2. purpose ((total - target) / 2) 구하기
    const purpose = (total - target) / 2;
    
    // 3. numbers 내에서 합이 purpose인 배열의 개수 구하기
    
    
    return answer;
}

 

여기까지가 제가 들이댄 코드입니다.

그러나 마지막 단계인 "numbers 내에서 합이 purpose인 배열의 개수 구하기"에서 막혔는데요.

이 부분에서 바로 DFS가 사용되어야 할 것 같습니다.

 

➕ reduce() 사용 방법

// arr.reduce(callback(accVal, curVal, curIdx, arr), initVal);
// accVal : 누적값

 

2. DFS란 무엇인가?

DFS, 깊이 우선 탐색은 그래프나 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘 중 하나입니다.

이를 이해하기 위해서는 몇 가지 기본 개념을 살펴볼 필요가 있었는데요.

(1) 스택 (Stack) : DFS는 주로 스택을 사용해 구현합니다.
스택은 Last In First Out (LIFO)의 원칙에 따라 동작하며, 새로운 요소가 항상 스택의 가장 위에 쌓입니다.

(2) 재귀 함수 : DFS는 주로 재귀 함수를 통해 구현합니다.
함수가 자기 자신을 호출함으로써 깊이를 우선적으로 탐색합니다.

 

3. 그래서 DFS를 어떻게 사용할건데?

"DFS, 재귀 함수를 사용해서 주어진 numbers 배열에서

부분집합의 합이 목표 합(purpose)과 일치하는 경우의 수를 찾는다."

function solution(numbers, target) {
    let answer = 0;
    
    // 1. total (numbers 합계) 구하기
    const total = numbers.reduce((accVal, curVal) => {
        return accVal + curVal;
    })
    
    // 2. purpose ((total - target) / 2) 구하기
    const purpose = (total - target) / 2;
    
    // 3. numbers 내에서 부분집합의 합이 purpose인 경우의 수 구하기
    const countSubsets = (arr, targetSum, curIdx, curSum) => {
    
        // 현재 인덱스가 배열의 끝에 도달한 경우, 부분집합의 합 확인
        if (curIdx === arr.length) {
            return curSum === targetSum ? 1 : 0;
        }
        
        // 1) 현재 숫자 포함하는 경우
        const include 
        	= countSubsets(arr, targetSum, curIdx + 1, curSum + numbers[curIdx]);
        
        // 2) 현재 숫자 포함하지 않는 경우
        const exclude = countSubsets(arr, targetSum, curIdx + 1, curSum);
        
        return include + exclude;
    }
    
    answer = countSubsets(numbers, purpose, 0, 0);
    
    return answer;
}

 

위 코드에서 당연히 countSubsets를 들여다봐야겠죠.

const countSubsets = (arr, targetSum, curIdx, curSum) => {
    if (curIdx === arr.length) {
        return curSum === targetSum ? 1 : 0;
    }

    const include 
    	= countSubsets(arr, targetSum, curIdx + 1, curSum + numbers[curIdx]);
    const exclude = countSubsets(arr, targetSum, curIdx + 1, curSum);

    return include + exclude;
}

 

(1) 재귀 함수의 기본, Base Case

if (curIdx === arr.length) {
    return curSum === targetSum ? 1 : 0;
}

함수는 재귀 함수를 호출하기 전, 현재 인덱스(curIdx)가 배열의 끝에 도달했는지 확인합니다.

도달했다면, 현재 부분집합의 합을 확인하고, 이 값이 목표합과 일치하면 1을 반환 그렇지 않으면 0을 반환합니다.

이것이 재귀 호출의 종료 조건입니다.

 

(2) 재귀 호출 - 현재 숫자를 포함하는 경우

const include 
	= countSubsets(arr, targetSum, curIdx + 1, curSum + numbers[curIdx]);

현재 숫자를 부분집합에 포함하는 경우를 탐색하기 위해 curIdx + 1로 인덱스를 증가시키고,

현재 숫자를 합에 더한 값을 curSum + arr[curIdx]으로 전달하여 재귀 호출합니다.

 

(3) 재귀 호출 - 현재 숫자를 포함하지 않는 경우

const exclude = countSubsets(arr, targetSum, curIdx + 1, curSum);

현재 숫자를 부분집합에 포함하지 않는 경우를 탐색하기 위해 curIdx + 1로 인덱스를 증가시키고, 

현재 합을 그대로 사용하여 재귀 호출합니다.

 

(4) 결과 반환

return include + exclude;

현재 숫자를 포함하는 경우와 포함하지 않는 경우를 포함하여 결과를 합산 및 반환합니다.

이것이 재귀 호출의 결과가 됩니다.

 

4. 마무리

이 문제를 풀면서 DFS, 재귀 함수의 활용법을 배울 수 있었습니다. ( 아직 부족하지만요..! ㅎㅎ )

코드 한 줄 한 줄을 통해 어떻게 깊이 우선 탐색이 구현되는지,

그리고 재귀 함수가 어떻게 각 부분 문제를 해결하는데 활용되는지 알 수 있었습니다.

 

자세하게 기술한 블로그 글이 여러분에게 도움이 되었기를 바라며, 다음 블로그 글 기대해 주세요. 

모두 성장해 나가시길 바랄게요! 🚀✨