Programmers(DFS)_타겟넘버 | Bong5's Tech Blog

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

-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 하도록 구현하세요.

제한사항

문제 해결의 실마리는 상당히 간단하다. 위 문제는 + 또는 - 로 분기 되기 때문에 단순한 for 루프 로는 해결하기 쉽지 않다.

문제 유형이 명시적으로 BFS/DFS 라 주어졌다. 보통 2차원 배열에서 길 찾기와 같은 문제가 전형적인 탐색 문제인데 이 문제는 1차원 배열을 가지고 분기하는 방향으로 접근해야 한다.

나는 재귀적으로 문제 해결하는 방법을 더 선호하기 떄문에 DFS 로 접근하였다.

먼저 재귀의 기본인 수학적 귀납법 // Base Case(탈출 조건) // 명시적 매개변수 지정 측면에서 접근해보자.

귀납적 접근 수학적 귀납법에 대한 정의를 일일히 읊을순 없으므로 간단하게 하나만 생각하자 (n-1) 까지 성립함을 가정한다(믿는다). 즉, 앞선 재귀 호출로 연산된 결과가 성립함을 믿고 현재 시점에 알맞는 연산을 수행한다. 이 문제에서는 앞선 재귀호출에서 numbers 의 요소들이 (n-1) 까지 적절히 계산되었다고 가정하고 각 분기 계산 결과(target number의 개수)를 더하여 반환해준다.
Base Case 재귀함수는 반드시 탈출 조건이 하나 이상 존재해야 한다. (무한 루프에 빠지면 안된다.) 이 역시 수학적 귀납법에서 n = 0일 때 성립 과 같은 문맥이다. 위 문제에서는 numbers 에서 더이상 계산할 요소가 존재하지 않은 경우 Base Case 가 된다.
명시적 매개변수 지정 일반적인 for 루프 와 달리 재귀함수는 호출시 명시적인 매개변수를 지정하는게 좋다. 최초 호출할 때의 상황만 생각하지 않고 재귀적으로 호출할 때 함수 내부에서는 외부에서 어떤 조건을 가지고 있는지, 어떤 변수들을 활용하고 있는지 알 수 없기 때문이다. 위 문제에서는 (n-1) 까지 계산된 값, 현재 계산해야 하는 요소의 index, 계산할 요소들을 저장하고 있는 numbers 를 명시적인 매개변수로 사용한다.

명시적인 매개변수를 지정한 재귀함수를 (n-1) 까지 적절히 계산되었다고 가정하여 Base Case에 수렴할 때 까지 재귀호출 한다.