[프로그래머스]43165: 타겟 넘버 | DFS

 

[프로그래머스]43165번 타겟 넘버 - DFS

 

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

프로그래머스

 

 

---

[python]문제 풀이

DFS + 재귀함

 

1. 배열 numbers와 목표 값 target을 인자로 받기 , 여기서 주어진 숫자들을 더하거나 빼서 target 값을 만들 수 있는 방법을 찾는 것!!!

 

2. idx와 현재까지의 합(result)을 매개변수로 받고 , idx위치의 숫자를 더하거나 빼는 방법을 둘다 탐색

 

 

3. idx == len(numbers) -> 인덱스가 numbers의 길이에 도달했을 때  = 모두 탐색했을 때 

 result과 target이 같으면 1(성공)을 반환 / 아니면 0(실패)를 반환

 

4. 재귀 호출 : 현재 숫자를 더한 경우 (result+numbers[idx]) / 현재 숫자를 뺀 경우 (result-numbers[idx])

 

 

def solution(numbers, target):
    answer = 0
    def dfs(idx, result):
        if idx == len(numbers) :  # 인덱스가 numbers의 길이에 도달했을 때  = 모두 탐색했을 때 
            if result == target:  # 현재 합계가 타겟과 같으면 1을 반환
                nonlocal answer
                answer += 1
            return
        else:  # 현재 숫자를 더한 경우와 뺀 경우를 각각 탐색
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)      # 처음 재귀 호출 (0번째 인덱스부터 시작, 초기 합은 0)
    return answer

 

 

** nonlocal 키워드는 Python에서 중첩된 함수에서 사용. 특정 변수에 대해 외부 함수(또는 상위 함수)의 변수를 참조하거나 수정할 때 사용

 

** nonlocal answer는 중첩 함수인 dfs가 상위 함수 solution에 선언된 answer 변수를 수정할 수 있도록 하는 역할

 

-> nonlocal을 사용하지 않고 answer += 1을 수행하려고 하면, dfs 내부에서 새로운 지역 변수가 만들어지기 때문에 상위 함수의 answer 값에 영향을 미치지 않게 됨........

 

즉, nonlocal은 dfs 함수 내에서 상위 함수의 answer 변수에 접근하여, 그 값을 업데이트할수있음