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

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 조건

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1,1,1,1,1]	3	5
[4,1,2,1]	4	2

 

 

이 문제는 DFS (깊이우선탐색) 알고리즘을 이용하여 풀 수 있다. DFS를 대학교 2학년 때 이후로... 해본 적이 없어서 다시 정리하면서 풀어보고자 한다...!

 

DFS (깊이 우선 탐색) 알고리즘이란?

깊이 우선 탐색은 시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문한다.

최대 깊이 노드까지 방문한 다음에는 이전에 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 최대 깊이까지 차례대로 방문한다. 해당 형제 노드에서도 자식 노드를 탐색하고, 더이상 자식 노드가 없을 경우 다시 인접한 상위 형제의 노드를 방문하는 알고리즘이다.

 

위의 그림에서 A에서 쭉 E까지 순회하였다가, I를 가장 마지막에 방문하게된다!

 

DFS를 구현하는 방법에는 2가지 방법이 있는데 첫번째는 재귀를 이용하는 것이고 두번째는 스택을 이용하는 것이다. 

여기에서는 재귀를 사용해서 문제를 풀어보았다.

 

재귀 함수를 호출할 때마다 호출한 함수는 콜 스택에 쌓이므로 깊이 우선 탐색에 활용할 수 있다.

깊이 우선 탐색은 가장 깊은 곳을 우선하여 탐색하고, 더이상 탐색할 수 없으면 백트래킹하여 최근 방문 노드부터 다시 탐색을 진행한다는 특징이 있어서 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우에 활용할 수 있다.

최단 경로를 찾는 문제가 아니라면 깊이 우선 탐색을 우선 고려해보는 것이 낫다. 

 

 

문제 풀이

function solution(numbers, target) {
    var answer = 0;
    
    dfs(0,0)
    
    function dfs(index,sum){
        if(index===numbers.length){
            if(sum===target){
                answer++;
            }
               return;
        }
     
        dfs(index+1, sum+numbers[index]);
        dfs(index+1,sum-numbers[index]);
        
    }
    
    
    return answer;
}

 

• dfs(0,0)에서 시작해서, 매 단계마다 +와 - 두 갈래로 뻗어 나간다.
• 배열의 마지막 요소까지 모두 순회했을 때, 합이 타겟과 같다면 answer을 올려주고, 다르면 그냥 종료한다.
• 아직 배열의 끝이 아니라면, index를 1 올리고 더하는 경우와, 빼는 경우를 탐색한다.
• 이 과정을 재귀로 끝까지 반복하며 모든 +/- 조합을 다 시도한다.