프로그래머스 Lv 2 타겟 넘버

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

프로그래머스

해결 방법 : 사실 DFS와 BFS 개념인 걸 알고 들어가서 그런 지 몰라도 조금 더 수월했다 그냥 봤으면 DFS/BFS 생각을 했을 진 의문이다... 더 익숙해질 필요가 있겠단 생각이 들었다. 그럼에도 DFS와 BFS 중 어떤 방식으로 접근해야 할 지는 아직 잘 모르겠다. 자료구조 시간 때 했던 DFS 방식으로 미로찾기를 구현했던 경험을 토대로 DFS로 해결하고자 했다. 
아이디어 

1) 처음엔 Stack을 이용해서 풀어보려고 생각해봤으나 실패 했다..! 

stack으로 시도 결과 실패..

2) DFS로 풀어보고자 했다. 

DFS 시도

dfs를 재귀함수로 설정해서 dfs(0번째 , 0번째 값) 에서 dfs(1번째 , 0번째에서 +1 값) / dfs(1번째 , 0번째 -1 값) 이런 식으로 분기되는 점을 인지했다. numbers에는 입력 배열과 result에는 값 그리고 카운트를 셀 answer을 만들었다. 그 후 answer을 nonlocal 이라는 새로 배운 개념을 통해 전역변수화 시켜줬다

전역변수화 시켜주는 이유 : 지역변수로 설정된다면 재귀 함수 한 번을 호출 할 때마다 스택에 변수를 생성해줘야 한다. 그래서 전역변수로 설정해주어 이러한 메모리 공간 낭비를 줄일 수 있기 때문이다. 

3) 나의 풀이 

def solution(numbers, target):
    answer = 0 
    n = len(numbers)

    def dfs(index,result):
        if index == n :
            if result == target:
                nonlocal answer
                answer +=1
            return 
        else: 
            dfs(index + 1 , result + numbers[index])
            dfs(index + 1 , result - numbers[index])
    dfs(0,0)
    return answer

4) 개념 및 피드백

• DFS : 깊이 우선 탐색으로 루트 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완전하게 탐색하는 방법
• BFS : 너비 우선 탐색으로 루트 노드에서 인접한 노드를 먼저 탐색하는 방법 
• 재귀함수 : 함수에서 자기 자신을 다시 호출해 수행하는 방식
• nonlocal : 로컬 변수가 아님을 선언하는 것, 전역변수와 조금 다르게 상위 함수에 바인딩 되는 것이 특징이다. 즉 전역변수는 아님. 위 문제에서는 dfs 함수 상위 함수가 solution이기 때문에 사용 가능했던 점, global로 따로 표시해주는게 더 나았을 듯 싶다.