[Programmers]타겟 넘버

문제 링크

Level2. 타겟넘버

문제 설명

입력

• 사용할 수 있는 숫자가 담긴 배열 (numbers)
• 연산 결과 (target)

출력

• 연산결과를 내기 위한 방법의 가짓수

문제 풀이

우선 제일 중요한 것! 이게 왜 bfs, dfs를 이용한 탐색문제냐!!!
이 부분이 제일 이해가 안되길래 구글링 해봤다. 처음 본 글에서 바로 이해할 수 있었다.

방법1. 재귀를 이용한 방법

def solution(numbers, target):

    answer = 0
    length = len(numbers)

    def dfs(idx, result):
        if idx == length:
            if result == target:
            	# global과 nonlocal의 차이점 확인해두기
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result-numbers[idx])
            dfs(idx+1, result+numbers[idx])
        return answer
    return dfs(0, 0)

-> 높이를 idx로 두고 계산한 결과를 재귀적으로 구하다가 제일 깊은 곳에서만 target과 비교해 같은 수의 갯수를 출력

방법2. 단순 연산을 이용한 방법

def solution(numbers, target):
    sup = [0]
    for i in numbers:
        sub = []
        for j in sup:
            sub.append(j+i)
            sub.append(j-i)
        sup = sub
    return sup.count(target)

-> 빈 리스트를 이용해 깊이마다 덧셈 결과를 배열에 덮어쓰기해서 최종적으로 나온 결과 리스트 중 target과 같은 수의 갯수를 출력

필요 개념 (global vs nonlocal)

변수의 범위

#outer(), inner()함수의 전역 범위
global_var = "전역 변수"

def outer():
	# outer() 함수의 지역 범위
    # inner() 함수의 비지역 범위
   	nonlocal_var = "비지역 변수"
    
    def inner();
    # inner() 함수의 지역 범위
    local_var = "지역 변수"

변수의 특성 중 서로 다른 범위에서는 변수 이름 충돌이 발생하지 않는다는 것은 바깥쪽 범위에서 선언된 변수와 같은 이름의 변수를 안쪽에서도 생성할 수 있다는 것

global

num = 0	# 전역 변수
def print_num():
    print(num)

print_num()	#0출력
print(num)	#0출력

-> num은 전역변수여서 함수 안에서 접근하거나 밖에서 접근하거나 상관없이 동일한 값을 가짐

num = 0	
def print_num():
	num = 100	# 지역 변수
    print(num)

print_num()	#100출력
print(num)	#0출력

-> 함수 내부에 있는 num은 지역 변수이기 때문에 함수 외부의 num과는 엄연히 다른 변수
그럼 둘이 동일한 값을 갖게 하기 위해서는❓

num = 0	
def print_num():
	global num
	num = 100	# 지역 변수
    print(num)

print_num()	#100출력
print(num)	#100출력

-> gobal 키워드를 이용

nonlocal

def print_num():
	num = 0	# 비지역 변수
    def change_num():
    	num = 100
    	print(num)
    
    change_num()	#100출력
    print(num)	#0출력
    
print_num()

-> 이런 중첩 함수에서 두 함수 내부의 변수가 같은 값을 갖게 하기 위해서는❓

def print_num():
	num = 0	# 비지역 변수
    def change_num():
    	nonlocal num
    	num = 100
    	print(num)
    
    change_num()	#100출력
    print(num)	#100출력
    
print_num()

-> nonlocal 키워드를 이용

global: 일반 함수 내에서 전역 변수를 대상으로 사용
nonlocal: 중첩 함수 내에서 비지역 변수를 대상으로 사용

느낀점

왜 탐색문제인지를 파악하고나서 곧바로 dfs코드를 짜려고 했지만 쉽게되진 않았음
이전의 문제들보다는 수월하게 진행할 수 있었지만 그래도 조금 헤매는 느낌
특히 개념 정리해 둔 nonlocal하고 global구분하는 부분에서 좀 많이 헤맸다.
계속 global로만 처리하려고 해서,,
곧바로 구현할 수 있을 때까지 더 연습하기,,,중요,,⭐️