Lv 2. 타겟넘버

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/43165

1. 상태 트리(State Tree) 생각하기

각 숫자를 만날 때마다 우리는 두 가지 갈림길에 서게 됩니다.

• 현재 숫자를 더한다 (+)
• 현재 숫자를 뺀다 (-)

예를 들어 숫자가 [1, 1, 1]이고 타겟이 3이라면, 첫 번째 1에서 +1과 -1로 나뉘고, 그 각각에서 다시 두 번째 1을 더하거나 빼는 식으로 뻗어나갑니다.

2. DFS (재귀) 접근법

가장 직관적인 방법은 재귀 함수를 사용하는 것입니다.

• 함수의 인자: (현재까지의 합, 다음에 처리할 숫자의 인덱스)
• 종료 조건: 인덱스가 숫자 배열의 끝에 도달했을 때.
  • 이때 현재까지의 합 == 타겟 넘버라면 방법의 수를 1 증가시킵니다.
• 재귀 호출:
  1. dfs(합 + 현재 숫자, 인덱스 + 1)
  2. dfs(합 - 현재 숫자, 인덱스 + 1)

3. BFS (큐/반복문) 접근법

큐(Queue)나 리스트를 사용해 현재 단계에서 만들 수 있는 모든 합을 저장하며 나아가는 방식입니다.

1. 처음에는 [0]으로 시작합니다.
2. 배열의 첫 번째 숫자를 꺼내서 이전 합들에 더하고 뺀 값들을 새로 저장합니다. (예: [1, -1])
3. 그다음 숫자를 꺼내서 위에서 만든 값들에 각각 더하고 뺍니다. (예: [2, 0, 0, -2])
4. 모든 숫자를 처리했을 때, 리스트 안에 target과 일치하는 값이 몇 개인지 세면 됩니다.

---

💡 힌트 요약

• 완전 탐색: 숫자의 개수가 최대 20개이므로, 가능한 모든 경우의 수는 $2^{20}$ (약 100만 건)입니다. 이는 컴퓨터가 1초 안에 충분히 계산할 수 있는 양이므로, 모든 경우를 다 확인하는 전략이 유효합니다.
• 추천: 처음 공부하시는 단계라면 DFS 재귀 방식이 코드가 훨씬 간결하고 로직을 이해하기 좋습니다.

가장 이해하기 쉬운 DFS(재귀) 방식으로 코드를 작성해 드릴게요.

이 코드는 모든 숫자를 끝까지 방문했을 때(재귀의 끝), 그 결과가 target과 같은지 확인하는 로직입니다.

---

Python 코드 정답

Python

 

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    
    def dfs(idx, current_sum):
        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])
        
    dfs(0, 0) # 0번째 인덱스부터, 합계 0으로 시작
    return answer

코드 풀이 (작동 원리)

1. dfs(idx, current_sum): 현재 몇 번째 숫자(idx)를 보고 있는지와 지금까지의 계산 결과(current_sum)를 들고 계속 깊게 들어갑니다.
2. 두 갈래의 재귀:
   • dfs(idx + 1, current_sum + numbers[idx]): "이번 숫자는 더할게!" 하고 다음 숫자로 넘어갑니다.
   • dfs(idx + 1, current_sum - numbers[idx]): "이번 숫자는 뺄게!" 하고 다음 숫자로 넘어갑니다.
3. 정답 카운트: 리프 노드(배열의 끝)에 도달했을 때 딱 한 번 target 값과 비교하여 일치하면 answer를 올립니다.

다른 풀이 (Pythonic 한 방식)

파이썬의 itertools.product를 사용하면 재귀 없이도 아주 짧게 풀 수 있습니다. 모든 +, - 조합을 생성하는 방식입니다.

Python

 

from itertools import product

def solution(numbers, target):
    # [(1, -1), (2, -2), (3, -3) ...] 이런 식의 쌍을 만듭니다.
    l = [(x, -x) for x in numbers]
    
    # 모든 조합의 합을 구해서 target과 같은 것만 남깁니다.
    s = list(map(sum, product(*l)))
    
    return s.count(target)

[나의 풀이]

 

[다른 사람 풀이]

 

[배운 스킬]