문제 링크 : 타겟 넘버
문제 접근: 모든 경우의 수 탐색
주어진 숫자 배열의 모든 요소를 더하거나 빼서 특정 target 숫자를 만드는 경우의 수를 구해야 합니다. 이는 각 숫자를 사용할 때마다 +를 할지 -를 할지 결정해야 하는 갈림길과 같습니다.
만약 숫자가 5개라면 1번 숫자에서 2갈래, 2번 숫자에서 또 2갈래로 나뉘며 총 2^5 = 32개의 최종 결과가 만들어집니다. 우리는 이 나무의 맨 끝(Leaf Node)까지 한 길로 쭉 내려가 결과를 확인한 뒤, 다시 부모 노드로 돌아와 다른 길을 탐색하는 깊이 우선 탐색(DFS) 방식을 통해 모든 경우의 수를 빠짐없이 확인할 수 있습니다.
초기 구현 : 전역 변수 방식
성공할 때마다 미리 선언해둔 answer 변수를 1씩 증가시키는 방식입니다.
class Solution {
int answer;
public int solution(int[] numbers, int target) {
answer = 0;
dfs(numbers, target, 0, 0);
return answer;
}
void dfs(int[]numbers, int target, int depth, int sum){
if(depth==numbers.length){
if(sum==target) answer++; // 결과가 맞으면 전역 변수에 기록
}else{
dfs(numbers, target, depth+1, sum+numbers[depth]);
dfs(numbers, target, depth+1, sum-numbers[depth]);
}
}
}- 장점
이해하기 쉽고 직관적입니다. - 단점
answer라는 전역 변수에 의존하므로 함수가 외부 환경과 엮여 있습니다. 따라서 메서드를 재사용하거나 테스트할 때 매번answer를 초기화해야 하는 번거로움이 발생합니다.
개선된 구현: 값 반환 방식
전역 변수를 사용하는 대신 각 재귀 함수가 탐색을 마친 뒤 내가 찾은 성공 횟수를 부모에게 반환하는 방식입니다.
class Solution {
public int solution(int[] numbers, int target) {
return dfs(numbers, target, 0, 0);
}
int dfs(int[] numbers, int target, int depth, int sum) {
// 모든 숫자를 다 사용했다면 성공 여부(1 또는 0)를 반환
if (depth == numbers.length) {
return (sum == target) ? 1 : 0;
}
// 왼쪽 길(더하기)과 오른쪽 길(빼기)에서 올라온 결과값을 더해서 부모에게 전달
return dfs(numbers, target, depth + 1, sum + numbers[depth]) +
dfs(numbers, target, depth + 1, sum - numbers[depth]);
}
}이 방식의 작동 원리는 다음과 같습니다. 가장 끝에 도달한 함수들이 자신의 성공 여부(1 혹은 0)를 부모에게 던져주면 부모 노드는 자식들이 보낸 두 값을 더해 자기 부모에게 다시 전달합니다. 이 연쇄적인 보고 과정이 반복되어 결국 루트 노드(depth 0)에는 모든 경로의 성공 횟수가 합쳐진 최종 결과가 반환됩니다.
배운 점
재귀 함수를 다룰 때 가장 어려웠던 부분은 return dfs(...) + dfs(...) 구문이 어떻게 결과를 누적하는지였습니다. 처음에는 전역 변수 없이 어떻게 값이 합쳐지는지 이해가 가지 않았는데 재귀를 '계층적인 보고 체계'로 비유해보니 명확해졌습니다.
각 재귀 함수를 하나의 '조사원'이라고 생각하면 쉽습니다. 조사원은 자신이 맡은 끝까지 가서 성공 여부(1 혹은 0)를 확인하고 돌아오면서 그 결과를 자신의 상관(부모 함수)에게 전달합니다. 부모 함수는 왼쪽 조사원과 오른쪽 조사원이 가져온 결과를 더해서 또 그 위의 상사에게 보고합니다. 이렇게 밑바닥부터 쌓아 올린 결과들이 최종적으로 모여 하나의 숫자가 되는 것이죠.
이 방식은 전역 변수를 쓰지 않기 때문에 함수가 외부 상황과 독립적으로 움직일 수 있고 그 자체로 완벽한 논리 단위를 이룹니다. 재귀가 단순히 복잡한 반복을 처리하는 기술을 넘어 문제를 작은 조각으로 나누어 해결하고 결과를 취합해 나가는 논리적 구조라는 것을 깊이 깨달았습니다.
