[javascript] 프로그래머스 타겟 넘버

문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

풀이

주어진 모든 숫자에 (+)연산과 (-)연산을 하는 경우를 탐색해 타겟 숫자가 나오는 횟수를 카운트하면 된다. 경우의 수를 고려해 보면 숫자 n개는 각각 (+)와 (-) 가 될 수 있는 두가지 경우의 수를 가지고 있고, 해당 경우의 수는 전체 숫자에 대해 동시에 발생하므로 2 * 2 * 2 * ….. n, 총 2^n번의 탐색이 일어난다.

DFS 알고리즘을 이용하면 전체 숫자가 (+) (-)일 모든 경우의 수를 탐색할 수 있다.

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

그래프에서 다른 노드를 방문하기 전에 하나의 노드를 깊게 파고들며 순회하는 검색 알고리즘이다.

최상위 노트에서 연결된 자식 노드를 모두 탐색한 후, 더 이상 자식 노드가 없을 때 인접한 상위 노드의 형제 노드를 방문한다. 해당 형제 노드에서도 자식 노드를 탐색하고, 더 이상 자식노드가 없을 경우 다시 인접한 상위 형제의 노드를 방문하는 알고리즘이다.

아래 그림을 보면 최상위 루트 노드 (A)에서 (B)를 따라 자식 노드를 탐색한 뒤, (I) 를 가장 마지막에 탐색하게 된다.

자바스크립트에서는 재귀 함수를 이용하여 DFS를 구현할 수 있다. 각각 노드의 자식 노드를 탐색하는 함수를 스택에 추가한 뒤, 더 이상 자식 노드가 없을 때 마지막에 추가된 자식 노드 먼저 실행 후 스택에서 제거하는 후입선출(LIFO) 방식이 이용된다.

위 프로그래머스 문제에서 각 노드 (숫자)는 다음 인덱스의 숫자가 (+)인 경우와 (-)인 경우 두 가지의 자식 노드를 가지고 있으며, DFS 방법에 따라 모든 숫자가 (+)인 경우를 모두 탐색한 뒤 다음 인덱스의 숫자가 (-)인 경우를 탐색한다.

다른 분들의 코드를 참고해서 풀었지만 재귀 과정이 이해가 잘 안 돼 설명을 좀 더 붙여보고자 한다.

프로그래머스의 예시처럼 numbers는 [1,1,1,1,1]이, target이 3인 파라미터가 주어진 경우를 생각해보자. 해당 함수가 실행되면

1. 14번 라인 dfs(index + 1, sum + numbers[index]) 부분이 계속 실행되며 다음 인덱스의 숫자가 (+) 인 자식 노드를 계속 탐색한다.

2. 마지막 인덱스에 다다랐을 경우(index = 5, sum = 5 일 때) 해당 함수를 스택에서 제거한 뒤, index가 4일 때 15번 라인 dfs(index + 1, sum — numbers[index]) 을 실행하여 (-)인 자식 노드를 탐색한다.

3. 마지막 인덱스에 다다랐으니 다시 해당 함수를 스택에서 제거, index가 3일 때 15번 라인 dfs(index + 1, sum — numbers[index]) 을 실행한다.

4. index 4가 (-)일 때 14번 라인을 실행하여 index 5가 (+)인 경우의 자식을 탐색, 탐색을 마치면 해당 함수를 스택에서 제거한 뒤 15번 라인을 실행하여 index 5가 (-)인 경우의 자식을 탐색한다.

5. 다시 index가 2일 때 15번 라인 dfs(index + 1, sum — numbers[index]) 을 실행, index 3이 (-)일 때 14번 라인을 실행하여 index 4가 (+)인 경우의 자식 노드를 모두 탐색 후 15번 라인을 실행하며 index 5가 (-)인 경우의 자식 노드를 탐색한다.

(+)의 자식 노드 탐색 → (-)의 자식 노드 탐색 순서로 위 과정이 진행되며, index 1이 (-)일 때의 자식 노드의 경우의 수 (+), (-) 를 모두 탐색하면 해당 함수가 종료된다.

배열로 위 과정을 살펴보면 아래와 같은 순서로 노드 탐색이 진행된다.

[+1, +1, +1, +1, +1]
[+1, +1, +1, +1, -1]
[+1, +1, +1, -1, +1]
[+1, +1, +1, -1, -1]
[+1, +1, -1, +1, +1]
[+1, +1, -1, +1, -1]
[+1, +1, -1, -1, +1]
[+1, +1, -1, -1, -1]
.
.
.

Reference.
배세민. 자바스크립트로하는 자료 구조와 알고리즘 .에이콘. 2019