프로그래머스 등급2 - 타겟 넘버

타겟 넘버 문제 바로 가기

풀이 날짜: 2026-04-30

baekjoon 알고리즘 문제 풀이

풀이 코드


def solution(numbers, target):
    answer = 0
    
    def dfs(index,sum_num):
        nonlocal answer
        
        if index == len(numbers):
            if sum_num == target:
                answer += 1
            return
        
        dfs(index+1,sum_num + numbers[index])
        dfs(index+1,sum_num - numbers[index])
        
    dfs(0,0)
    
    return answer

문제 핵심

타겟 넘버 문제는 각 숫자 앞에 + 또는 -를 붙여서 목표값을 만드는 경우의 수를 구하는 문제이다. 처음에는 그래프 문제처럼 보이지 않지만, 실제로는 각 숫자마다 두 가지 선택(+ 또는 -)이 존재한다. 따라서 모든 경우의 수를 탐색해야 하며, 이는 자연스럽게 완전탐색 문제로 이어진다. 각 선택을 트리 형태로 펼쳐보면 매 단계마다 두 갈래로 나뉘는 이진 트리 구조가 되기 때문에, DFS를 활용하여 모든 경우를 탐색하는 방식으로 접근할 수 있다.

DFS 상태 정의 (index와 sum의 의미)

DFS 함수는 dfs(index, sum) 형태로 정의하며, 여기서 index는 현재 몇 번째 숫자를 처리 중인지, sum은 지금까지 계산된 합을 의미한다. 초기 상태는 아무 숫자도 선택하지 않은 상태이므로 dfs(0, 0)으로 시작한다. DFS를 진행하면서 index는 하나씩 증가하고, sum은 현재 숫자를 더하거나 빼면서 갱신된다. —

종료 조건 (재귀 탈출 조건)

DFS에서 가장 중요한 부분 중 하나는 종료 조건이다. index == len(numbers)가 되면 모든 숫자를 한 번씩 사용한 상태이므로 더 이상 탐색할 필요가 없다. 이 시점에서 현재까지 계산된 sum이 target과 같다면 하나의 경우의 수를 찾은 것이므로 카운트를 증가시킨다. 이 과정을 통해 모든 경우를 탐색하면서 정답을 누적할 수 있다.

재귀 호출 로직 (핵심 아이디어)

각 단계에서는 현재 숫자에 대해 두 가지 선택을 수행한다. 하나는 현재 숫자를 더하는 경우, 다른 하나는 빼는 경우이다. 이를 코드로 표현하면 다음과 같다.

dfs(index + 1, sum + numbers[index])
dfs(index + 1, sum - numbers[index])

nonlocal을 사용하는 이유

DFS 내부에서 경우의 수를 세기 위해 answer 변수를 사용하게 되는데, 이 변수는 바깥 함수인 solution에 선언되어 있다. 파이썬에서는 내부 함수에서 바깥 함수의 변수를 수정하려면 nonlocal 키워드를 사용해야 한다.

global과 nonlocal의 차이

global과 nonlocal은 모두 외부 변수를 참조하기 위한 키워드이지만, 사용 범위가 다르다. global은 전역 변수(파일 전체에서 사용하는 변수)를 의미하고, nonlocal은 바로 바깥 함수의 변수를 의미한다. 이 문제에서는 answer가 전역 변수가 아니라 solution 함수 내부에 선언된 변수이기 때문에 global이 아닌 nonlocal을 사용해야 한다.

핵심 정리

이 문제는 그래프 문제라기보다는 모든 경우의 수를 탐색하는 완전탐색 문제이다. 각 숫자마다 + 또는 -를 선택하는 과정을 트리 구조로 생각하면 DFS로 자연스럽게 해결할 수 있다. 구현 시에는 index와 sum을 상태로 관리하고, 모든 숫자를 사용했을 때 target과 비교하는 방식으로 접근하면 된다. 또한, 내부 함수에서 외부 변수를 수정할 때는 nonlocal을 사용해야 한다는 점도 함께 기억해야 한다.

Vienna sausage