DFS, memoization - 타겟 넘버 (프로그래머스)

 

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

프로그래머스

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [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
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2

어렵지 않게 풀수 있었는데 numbers가 1이 25개쯤 있으면 코랩에서 11초 걸렸다

def solution(numbers, target):
    answer = 0
    def dfs(idx, result):
        if idx == len(numbers) and result == target:
            nonlocal answer
            answer += 1
            return
        if idx == len(numbers):
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    result = 0
    dfs(0, result)
    return answer
numbers = [1 for i in range(25)]
target = 3
solution(numbers, target)

위 동일한 (idx, result) 상태가 여러 경로를 통해 반복될 수 있기 때문에. 이런 중복 계산을 피하면 효율이 향상됩니다.

메모이제이션 기법을 사용하면 501개의 조합도 순식간에 풀었다.

def solution(numbers, target):
    memo = {}

    def dfs(idx, result):
        if (idx, result) in memo:
            return memo[(idx, result)]
        
        if idx == len(numbers):
            return 1 if result == target else 0

        # 현재 상태에서 가능한 경우의 수 계산
        plus = dfs(idx + 1, result + numbers[idx])
        minus = dfs(idx + 1, result - numbers[idx])
        memo[(idx, result)] = plus + minus
        return memo[(idx, result)]

    return dfs(0, 0)
numbers = [1 for i in range(501)]
target = 3
solution(numbers, target)

위 코드를 보면 plus, minus변수를 더한걸 메모이제이션 하고 있다.

현 분기에서 +,-연산의 경우의 수가 있기 때문에 현분기에서 만들수있는 경우의 수는 +,-를 순회한 경우의 수를 더하면 된다.

 

**(idx, result)**라는 상태에서 만들 수 있는 모든 경우의 수의 합이기 때문입니다.

---

🔍 자세히 설명하면:

• dfs(idx, result)는 idx번째 숫자부터 시작해서, 현재까지의 합이 result일 때,
  남은 숫자들로 target을 만들 수 있는 경우의 수를 반환합니다.
• 여기서 두 가지 선택을 하죠:
  • +numbers[idx] → 다음 상태: (idx+1, result + numbers[idx])
  • -numbers[idx] → 다음 상태: (idx+1, result - numbers[idx])
• 따라서 이 상태에서 가능한 총 경우의 수는
  plus = dfs(idx+1, result + numbers[idx])
  minus = dfs(idx+1, result - numbers[idx])
  → 이 둘의 합: plus + minus

---

📦 그래서 memo[(idx, result)]에 저장하는 이유는:

나중에 같은 상태 (idx, result)가 다시 등장할 때,
이미 계산한 값을 재사용해서 중복 호출을 피하기 위해서입니다.
메모이제이션은 **값 자체(여기선 경우의 수)**를 저장해야 의미가 있습니다.