lv2. 타겟넘버

프로그래머스의 '타겟 넘버' 문제는 완전 탐색(Brute Force)의 대표적인 문제로, DFS(깊이 우선 탐색) 또는 **BFS(너비 우선 탐색)**를 공부하기에 아주 좋은 문제입니다.

핵심 아이디어와 구현 방법을 정리해 드릴게요.

---

1. 핵심 아이디어: 상태 트리(State Tree)

각 숫자에 대해 우리가 선택할 수 있는 선택지는 딱 두 가지입니다.

1. 해당 숫자를 더한다 (+)
2. 해당 숫자를 뺀다 (-)

모든 숫자에 대해 이 두 가지 경우를 전부 따져보며 끝까지 내려갔을 때, 합계가 target과 일치하는지 확인하면 됩니다.

---

2. 해결 방법 1: DFS (재귀 이용)

가장 직관적인 방법입니다. 숫자를 하나씩 선택해 내려가면서 마지막 숫자까지 도달했을 때 타겟 넘버인지 확인합니다.

• 진행 방식:
  1. 현재 인덱스가 마지막 숫자인지 확인합니다.
  2. 마지막이라면, 지금까지의 합이 target과 같은지 확인하고 1 또는 0을 반환합니다.
  3. 마지막이 아니라면, 현재 합 + 다음 숫자와 현재 합 - 다음 숫자 두 갈래로 재귀 호출을 합니다.

Python

 

def solution(numbers, target):
    def dfs(index, current_sum):
        # 모든 숫자를 다 사용했을 때
        if index == len(numbers):
            return 1 if current_sum == target else 0
        
        # 현재 숫자를 더하는 경우 + 빼는 경우의 합을 반환
        return dfs(index + 1, current_sum + numbers[index]) + \
               dfs(index + 1, current_sum - numbers[index])
    
    return dfs(0, 0)

---

3. 해결 방법 2: BFS (Queue 또는 List 이용)

너비 우선 탐색은 "현재까지 만들 수 있는 모든 합의 결과"를 계속 업데이트하며 나아가는 방식입니다.

• 진행 방식:
  1. 초기 리스트를 [0]으로 시작합니다.
  2. numbers의 숫자를 하나씩 꺼내며, 현재 리스트에 있는 모든 값에 대해 +한 값과 -한 값을 새로운 리스트에 담습니다.
  3. 모든 숫자를 순회한 후, 최종 리스트에서 target의 개수를 셉니다.

Python

 

def solution(numbers, target):
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    return leaves.count(target)

---

어떤 방법을 쓸까요?

• DFS는 코드 구성이 깔끔하고 '모든 경우의 수'를 깊게 파고들 때 유리합니다.
• BFS는 이 문제의 경우 구현이 매우 단순해지고, 각 단계에서 만들어지는 중간 합계를 직관적으로 볼 수 있습니다.

먼저 DFS 재귀 방식으로 직접 코드를 짜보시는 걸 추천드려요! 혹시 코드를 작성하다가 막히는 부분이 생기면 말씀해 주세요.

다음 단계로 이 두 방식 중 하나를 직접 구현해 보시겠어요, 아니면 Python의 itertools.product를 이용한 더 짧은 풀이법을 알려드릴까요?

 

좋은 선택입니다! **DFS(깊이 우선 탐색)**는 재귀를 이용해 상태 트리의 바닥까지 갔다가 돌아오는 방식으로, 이 문제의 논리를 이해하는 데 가장 적합합니다.

1. DFS 설계하기

DFS 함수를 만들 때 가장 중요한 두 가지는 **'종료 조건'**과 **'재귀 호출'**입니다.

• 종료 조건: 모든 숫자(numbers)를 다 사용했을 때 (즉, index == len(numbers))
• 재귀 호출: 1. 현재까지의 합에 다음 숫자를 더하는 경우 2. 현재까지의 합에서 다음 숫자를 빼는 경우

---

2. 트리 구조 시각화

예를 들어 numbers = [1, 1, 1], target = 1이라면 아래와 같은 흐름으로 탐색이 진행됩니다.

---

3. 직접 코드를 작성해 보세요

아래 가이드에 맞춰 빈칸을 채우듯 코드를 완성해 보세요.

Python

 

def solution(numbers, target):
    # n은 사용할 수 있는 숫자의 총 개수입니다.
    n = len(numbers)
    answer = 0

    def dfs(idx, current_sum):
        # 외부 변수 answer를 사용하기 위해 선언 (또는 return 방식 사용)
        nonlocal answer
        
        # 1. 종료 조건: 모든 숫자를 다 확인했다면?
        if idx == n:
            # 만약 현재 합이 타겟과 같다면 정답 카운트 증가
            if current_sum == target:
                answer += 1
            return

        # 2. 재귀 호출: 다음 인덱스의 숫자를 더하거나 뺀다
        dfs(idx + 1, current_sum + numbers[idx])
        dfs(idx + 1, current_sum - numbers[idx])

    # 처음 0번째 인덱스부터, 합계 0으로 시작합니다.
    dfs(0, 0)
    
    return answer

💡 팁

• nonlocal 키워드: 중첩 함수 내에서 바깥 함수에 있는 변수(answer)를 수정할 때 사용합니다. 만약 이게 헷갈린다면, 이전 답변의 예시처럼 dfs가 값을 직접 return하게 하여 그 합을 구하는 방식을 써도 좋습니다.
• 재귀 깊이: 이 문제는 numbers의 길이가 최대 20개이므로, 재귀의 깊이가 깊지 않아 별도의 설정 없이도 충분히 해결 가능합니다.

직접 코드를 타이핑해서 테스트 케이스를 통과하는지 확인해 보시겠어요? 혹시 통과하지 못한다면 어떤 에러가 나는지 알려주세요!

 

네, 고생하셨습니다! 직접 고민해 보신 내용을 바탕으로 DFS를 이용한 최종 정답 코드를 깔끔하게 정리해 드릴게요.

가장 정석적이고 가독성이 좋은 재귀(Recursion) 방식입니다.

Python

 

def solution(numbers, target):
    # n: 숫자의 개수
    n = len(numbers)
    
    def dfs(idx, current_sum):
        # 1. 종료 조건: 모든 숫자를 다 사용했을 때
        if idx == n:
            # 최종 합계가 target과 일치하면 1, 아니면 0 반환
            return 1 if current_sum == target else 0
        
        # 2. 하위 단계로 재귀 호출
        # 현재 숫자를 더하는 경우의 수 + 현재 숫자를 빼는 경우의 수
        res_plus = dfs(idx + 1, current_sum + numbers[idx])
        res_minus = dfs(idx + 1, current_sum - numbers[idx])
        
        return res_plus + res_minus

    # 0번째 인덱스부터, 합계 0으로 시작
    return dfs(0, 0)

---

📝 코드 포인트 요약

1. 재귀의 흐름: numbers의 각 원소마다 +를 선택할지 -를 선택할지 두 갈래로 뻗어 나갑니다.
2. 반환값 처리: 바닥(Leaf node)에 닿았을 때 조건에 맞으면 1을 반환하고, 이 값들이 위로 전달되며 합쳐져 최종 정답이 됩니다.
3. 시간 복잡도: $O(2^n)$입니다. numbers의 최대 길이가 20이므로 $2^{20} = 1,048,576$ 정도로, 1초 안에 충분히 계산 가능한 범위입니다.

타겟 넘버 문제는 이 코드로 완벽히 해결됩니다!

 

성공적으로 코드를 작성해 보셨나요? DFS를 마스터하셨다면, 이제 조금 더 Pythonic(파이썬답게) 혹은 효율적으로 풀 수 있는 두 가지 다음 단계를 제안해 드립니다.

원하시는 방향을 골라보세요!

---

옵션 1: itertools를 이용한 한 줄 풀이 (Python 최강자)

파이썬의 표준 라이브러리를 사용하면 재귀 없이도 아주 간결하게 풀 수 있습니다. product 함수는 모든 조합(데카르트 곱)을 생성해 줍니다.

• 아이디어: 각 숫자 앞에 +가 붙는 경우와 -가 붙는 경우의 모든 조합을 구한 뒤 합계를 계산합니다.
• 코드 예시:이 방식은 코드가 매우 짧지만, numbers가 길어지면 메모리를 많이 사용한다는 특징이 있습니다.
• Python

   

  from itertools import product
  def solution(numbers, target):
      l = [(x, -x) for x in numbers]
      s = list(map(sum, product(*l)))
      return s.count(target)
  

---

옵션 2: 시간 복잡도와 공간 복잡도 분석

면접이나 코딩 테스트 대비용으로 이 문제의 효율성을 따져보는 단계입니다.

• 시간 복잡도: 각 숫자마다 +, - 두 가지 선택지가 있으므로 $2^n$입니다. (여기서 $n$은 numbers의 길이)
• 공간 복잡도:
  • DFS: 재귀 스택의 깊이가 $n$이므로 $O(n)$입니다.
  • BFS/itertools: 모든 가능한 합을 저장해야 하므로 최대 $O(2^n)$의 공간이 필요할 수 있습니다.
• 결론: $n$이 작을 때는 BFS나 itertools가 편하지만, $n$이 커질수록 메모리 효율 면에서는 DFS가 유리합니다.

---

옵션 3: 다른 DFS/BFS 문제 도전하기

'타겟 넘버'와 비슷한 논리를 사용하는 다른 문제로 넘어가 실력을 굳히는 단계입니다. 프로그래머스 내에서 아래 문제들을 추천합니다.

1. 네트워크 (Level 3): DFS/BFS의 기본 중의 기본입니다.
2. 게임 맵 최단거리 (Level 2): BFS를 이용한 최단거리 찾기 연습에 좋습니다.
3. 피로도 (Level 2): 완전 탐색과 DFS를 조합하여 푸는 좋은 문제입니다.

---

어떤 방향으로 진행해 볼까요? 1. itertools 방식에 대해 더 자세히 알고 싶다.

2. 비슷한 유형의 다른 문제를 추천받아 같이 풀어보고 싶다.

3. 방금 짠 DFS 코드에서 궁금한 점이 더 있다.