[pgs타겟넘버] nonlocal 변수와 recursive DFS

프로그래머스 타겟 넘버

nonlocal var.

• local var.가 아니다.
• global var.도 아니다.
• 한 단계 바깥의 변수를 가져온다.
• def가 이중이 아닐 경우에는 global을 가져오지는 못한다.

이 문제 풀이 코드 중 일부이다. helper def. 안에 nonlocal ans가 있기 때문에 solution def.의 ans를 가져와서 계속 업데이트를 해줄 수 있다.

def solution(numbers, target):
    ans = 0

    def helper(i, cum):
        nonlocal numbers, target, ans
        if i == len(numbers):
            if cum == target:
                ans += 1
            return

nonlocal을 잘 사용하지 못했을 때는 아래처럼 ans를 계속 인자로 주어서 return 해주는 방식으로 재귀를 진행했었다. helper를 불러올 때마다 ans로 받아줘야 했고, 또한 업데이트할 변수가 2개 이상이라면 코드가 복잡해지는 경우도 있었다.

def solution(numbers, target):
    ans = 0

    def helper(i, cum, ans):
        nonlocal numbers, target
        if i == len(numbers):
            if cum == target:
                ans += 1
            return ans

Depth First Search(DFS)

DFS는 워낙 유명한 문제해결 방식이기 때문에 자세한 설명은 여기에 남기지 않겠다. DFS는 마지막 leaf까지 갔다가 돌아오는 search 방식이고, BFS는 같은 레벨부터 search 한다. (깊이우선, 너비우선) 아래 첫번째가 DFS, 두번째가 BFS이다. DFS는 주로 recursion으로 구현하고, BFS는 queue를 사용하여 togo(다음 목적지)를 뽑아낸다.

출처는 https://developer-mac.tistory.com/64 입니다.

Question

Solution

my solution

numbers list의 끝까지 덧/뺄셈을 해줘야 하기 때문에 BFS보다는 DFS가 먼저 떠올랐다.
PSEUDO

• DFS: go to leaf first
• end condition: if cum == target: ans += 1
• numbers 숫자를 하나씩 계산할 때마다 cum에 덧/뺄셈

def solution(numbers, target):
    ans = 0

    def helper(i, cum):
        nonlocal numbers, target, ans
        if i == len(numbers):
            if cum == target:
                ans += 1
            return
        
        togo = [numbers[i], -1 * numbers[i]]
        helper(i+1, cum+togo[0])
        helper(i+1, cum+togo[-1])

    helper(0, 0)
    return ans

the other solution

Solution2가 아니라 the other라 이름 붙인 이유는 이 코드를 본 후 나중에 비슷한 유형의 문제가 나와도 어차피 내가 직접 적용하기 힘들 것 같다는 느낌이 강하게 들었기 때문이다ㅎㅎ
PSEUDO

• 넘버list가 없고, target==0이면 return 1
• 넘버list만 없다면 return 0 (끝까지 다 온 것)
• else: return solution(넘버[1:], target-number[0]) + solution(넘버[1:], target+넘버[0]) - 첫번째 수가 적용된 상태에서의 numbers와 target을 다시 정의하여 재귀

def sol_2(numbers, target):
    if not numbers and target == 0:
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

github