문제
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 함수를 작성해주세요.
제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
| numbers | target | return |
|---|---|---|
| [1, 1, 1, 1, 1] | 3 | 5 |
| [4, 1, 2, 1] | 4 | 2 |
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4- 총 2가지 방법이 있으므로, 2를 return 합니다.
문제 풀이
첫 번째 풀이
def solution(numbers, target):
cnt=0
def recur(idx,sum_num):
nonlocal cnt
if idx==len(numbers):
if sum_num==target:
cnt+=1
return
recur(idx+1,sum_num+numbers[idx])
recur(idx+1,sum_num-numbers[idx])
recur(0,0)
return cnt두 번째 풀이
def solution(numbers, target):
answer = []
def recur(num,tar,i,hap):
if i>=len(num):
if hap==tar:
answer.append(hap)
return
recur(num,tar,i+1,hap+num[i])
recur(num,tar,i+1,hap-num[i])
recur(numbers,target,0,0)
return len(answer)개인적으로 풀고 알고리즘 스터디를 하면서 또 풀어서 어쩌다 보니 여러 번 풀게 된 문제이다.
첫 번째 코드는 변수를 이용하여 nonlocal 선언하여 지역변수에서도 사용할 수 있게 만들었고,
두 번째 코드는 배열을 이용하여 값을 추가했다.
nonlocal? global?
재귀 함수를 사용하는 방식이라는 것은 바로 알았고 코딩도 금방 했다.
그런데 UnboundLocalError: local variable referenced before assignment 오류가 자꾸 떴다.
찾아보니 전역변수를 지역변수에서 사용하려고 했을 때 발생하는 오류라고 한다. 사용하는 지역(local) 내에서 global 변수를 선언하면 사용할 수 있다고 하는데 global cnt를 선언했더니 NameError : name 'cnt' is not defined
오류가 떴다.
이 오류를 해결하려고 시간을 잡아먹었다. 결론은 중첩된 함수에서는 global이 아닌 nonlocal을 사용해야한다.
지역변수와 전역변수
지역변수는 함수 내에서 선언하고 사용가능한 변수를 말한다. 즉, 다음과 같은 코드를 짜게 되면 func 함수 내에 cnt 변수를 새로 선언했고 지역변수이기 때문에 print(cnt)를 하면 오류가 발생한다.
def func():
cnt=111
print(cnt)
func()
print(cnt)그리고 아래와 같은 코드에서는 cnt는 전역변수이기 때문에 0이 두 번 출력된다.
cnt=0
def func():
print(cnt)
func()
print(cnt)하지만 이러한 코드를 짜면 func이라는 함수 내에 cnt라는 지역 변수가 새로 선언된 것이기 때문에 10과 0이 출력된다.
cnt=0
def func():
cnt=10
print(cnt)
func()
print(cnt)global
이제 global에 대해서 알아보자.
바로 위 코드의 func 함수 내에서 cnt 값을 변경하려면 global을 사용하면 된다.
cnt=0
def func():
global cnt
cnt=10
print(cnt)
func()
print(cnt)이렇게 쓰면 10이 두 번 출력된다.
nonlocal
하지만 중첩된 함수에서는 global 선언이 적용되지 않는다. 일반 함수 내에서 전역 변수를 대상으로 사용하기 때문이다.
중첩된 함수 내에서 비지역 변수를 대상으로 할때에는 nonlocal을 이용한다. 즉, 타겟 넘버 문제에서 사용할 수 있는 것이다.
def sol():
cnt=0
def func():
print(cnt)
func()
print(cnt)
sol()위 코드는 결국 0을 두 번 출력하게 된다.
이때 cnt는 sol 함수 입장에서는 지역 변수, func 함수 입장에서는 비지역 변수이다.
비지역 변수란 함수를 중첩했을 때 외부 함수와 내부 함수 사이에서 선언된 변수를 말한다.
def sol():
cnt=0
def func():
nonlocal cnt
cnt=10
print(cnt)
func()
print(cnt)
sol()즉, 중첩된 함수 내에서 nonlocal cnt을 선언해야 바깥의 cnt 변수를 사용할 수 있게 되는 것이다.
지역변수와 전역변수에 대해서 다시 한 번 생각하게되는 문제였다. 전역변수가 무엇인지 지역변수가 무엇인지에 대해 기초지식 정도만 가지고 있어도 코딩이 가능했기 때문에 안일하게 생각했던 것 같다.
변수의 scope을 좀 더 신경쓸 수 있는 기회가 되었다.
