새싹프로그래머의 이야기

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

프로그래머스 '타겟넘버' 문제를 풀며, 제목과 같은 에러를 만났었습니다.

이에, 해당 문제를 해결할 수 있는 방법인 nonlocal과 global 변수 범위 지정 키워드에 대해서 정리하고자 합니다.

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

    def dfs(i, val):
        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer

처음에는 위와 같이 코드를 작성하였습니다. 

저는 solution 함수 내에 answer 변수가 선언 되어 있으므로, dfs 함수 내에서도 사용할 수 있을 것이라 생각하였습니다.

에러 코드를 보면 '할당되지 않아서' 에러가 발생함을 알 수 있습니다.

파이썬 컴파일러는 dfs 내의 answer 변수를 solution 함수 내의 answer 변수와 동일한 변수로 보지 않고, dfs 함수 내의 '로컬 변수'로 인식하여 발생하는 에러였습니다.

def solution(numbers, target):
    answer = 0
    length = len(numbers)
    visited = [False] * length

    def dfs(i, val):
        nonlocal answer
        
        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer

첫번째 해결 방법은 dfs 함수 내에 answer라는 변수에 nonlocal 이라는 keyword를 지정해주는 것입니다.

해당 키워드를 지정하게 되면, answer이라는 변수를 dfs 함수 내의 로컬 변수로 취급하지 않고 solution 함수 내의 answer 변수를 의미한다고 설정해주는 것입니다.

def solution(numbers, target):
    global answer
    answer = 0
    length = len(numbers)
    visited = [False] * length

    def dfs(i, val):
        global answer

        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer

두번째 해결 방법은 global이라는 keyword를 지정해주는 것입니다. 

global 변수는 해당 변수를 전역 변수로 사용하겠다는 것을 의미합니다.

따라서 위와 같이 각 함수 내에 global이라는 keyword를 사용하여 answer이라는 변수를 로컬 변수가 아닌 전역 변수로 설정해주는 방법이 있습니다.

안녕하세요.

오늘은 백준 알고리즘을 풀며 만났던 TypeError: cannot unpack non-iterable int object 에 대해 글을 써보려 합니다.

먼저, 해당 에러를 접한 상황은 다음과 같습니다. (백준 알고리즘 1916번, 18352번)

저는 deque에 (distance,node)의 값을 넣고, pop() 할 때마다 두 값을 한번에 얻고 싶었습니다. 다음과 같이 말이죠.

q = deque((distance,node))
newDistance , newNode = q.pop()

하지만, TypeError가 발생하여서 문제는 풀어야해서 항상 다음과 같이 풀었습니다.

q = deque()
q.append((distance,node))
newDistance , newNode = q.pop()
print(newDistance,newNode)

문제를 풀고 나서, 왜 그렇지 하고 여러가지 테스트를 해보았는데 역시나.. deque를 잘못사용하고 있었습니다.

테스트를 위해 아래와 같이 코드를 돌려보았습니다.

q = deque((0,99))
print(q)
q = deque([0,99])
print(q)
q = deque([(0,99)])
print(q)

그랬더니 위와 같은 결과 값이 나왔습니다. 여기서 아뿔사 했습니다..(역시 기본이 제일 중요하다는 것을 뼈저리게 느끼며...)

파이썬의 deque() 함수는 선언할 때 들어왔던 인자를 자동으로 deque화 시켜서 저장한다는 것을 놓쳤던 것입니다.

다음과 같이 사용하면, q[0]에 0이 q[1]에 99가 들어가는 것이죠.

print를 통해 출력해보면 이런 결과값이 나옵니다.

q = deque((0,99))
print(q[0],q[1])

q = deque([0,99])
print(q[0],q[1])

q = deque()
q.append((distance,node))
newDistance , newNode = q.pop()

***

(3번째줄) 이렇게 사용한다면, 입력받고자 하는 변수 갯수와 입력하고자 하는 변수 갯수가 맞지 않기 때문에 Error가 발생하는 것이었습니다.

'TypeError: cannot unpack non-iterable int object' -> ' iterable 하지 않은 int형 객체를 unpack 할 수 없다' Error 내용은

입력하고하 하는 변수 갯수는 1개인데, 입력받고자 하는 변수 갯수가 2개 여서 값을 할당할 수 없다라는 것입니다.

그렇다면 제가 의도한 방식대로 하려면 어떻게 했어야 할까요?

정답은 다음과 같이 [] 안에 다시 tuple형태로 감싸서 값을 담는 것입니다.

q = deque([(0,99)])

한번 값을 확인해보면 다음과 같이 나옴을 알 수 있습니다.

q = deque([(0,99)])

print(q)

distance , node = q.pop()
print('distance:',distance,'node:',node)

오늘은 deque를 사용하며, 발생했던 TypeError에 대해서 정리해보았습니다.

진짜 오늘도 기본이 중요함을 뼈저리게 깨달으면서 포스팅을 마치겠습니다.

읽어주셔서 감사합니다.

문제를 푸시다보면 다양한 에러를 만나실텐데요. 

오늘은 백준알고리즘 1697번을 풀면서 발생한 메모리 초과에 대해서 글을 써보려고 합니다.

메모리 초과가 발생하는 이유를 간단히 말씀드리자면 '스택 오버플로우'가 발생하기 때문입니다.

문제를 푸시면서 가장 많이 접할 수 있는 경우는 다음 두 경우라고 생각합니다.

1.  너무 많은 변수들을 배열 등에 저장할 경우.

2. DFS 등에서 재귀적 호출을 통해 너무 많은 함수들을 호출할 경우.

저 같은 경우에는, 백준 알고리즘 1697번에서 1번에 의한 메모리 초과가 발생하였는데요.

시작점으로부터 도착점까지 도달할 때 까지, (시작점-1, 시작점+1, 시작점*2)에 해당하는 값들을 탐색하는 과정에서 실수를 했습니다.

시작점 = 5, 도착점 =17을 기준으로 처음 들어간 (5-1,5+1,5*2)에 대해서 다음 싸이클 값들이 어떻게 저장되는지 출력한 것인데요.

아래 스크린샷을 보시면, 하나의 경우의 수에 대하여 계속해서 3가지의 새로운 경우의 수가 들어가고 있습니다.

해당 문제의 시작점과 도착점이 될 수 있는 정수의 범위가 0~100,000 이었으니, 시작점이 1이고 도착점이 100,000일 경우 엄청나게 많은 값들이 큐에 저장되었겠죠?

이로 인해, 계속해서 메모리 초과가 발생하였습니다.

메모리 초과에 대한 해결 방안은 다음과 같습니다.

1. 배열에 너무 많은 값들이 들어가는 경우에는 값이 들어갈 수 있는 범위 제한 및 들어가는 데이터 수를 제한 하는 조건 등을 통해서 해결하실 수 있습니다.

1697번을 예시로 들자면,

Max = 10 ** 5
visitedCnt = [0]*(Max+1)

배열을 선언할 때, 적당한 크기로 배열의 사이즈를 할당합니다.

for i in pos:
    if 0 <= i <= Max and not visitedCnt[i]:
        visitedCnt[i] = visitedCnt[idx] + 1
        queue.append([i,visitedCnt[i]])

두번째로는 들어갈 수 있는 값들의 범위를 지정하여 무한 루프를 방지해주고, 해당 값을 처리한 적이 있는지 확인하여 중복된 데이터가 처리되지 않도록 하였습니다.

위, 두가지 방법을 통해 메모리 초과를 해결 할 수 있었습니다.

2. 재귀 등으로 인한 너무 많은 함수 호출로 인한 메모리 초과의 경우에는 다음과 같습니다.

첫번째로는 재귀가 너무 많은 횟수가 반복되지 않도록 적절한 조건 설정 해주어 메모리 초과가 발생하지 않도록 하는 방법이 있고,

두번째로는 재귀함수를 반복문으로 푸는 것입니다.

재귀함수를 통해 호출된 함수는 메모리 영역의 스택에 저장되는데, 동일한 함수여도 호출 될 때마다 스택영역에 계속해서 메모리가 할당되게 됩니다. 너무 많은 함수가 호출이 된다면 스택 영역의 메모리를 초과하게 되는 '스택 오버플로우'가 발생합니다.

즉, 핵심은 스택 영역의 메모리를 초과하지 않게 사용하는 것이죠.

첫번째 방법은 스택 영역을 활용하되 사용하는 메모리 영역을 초과하지 않게 하는 방법이고, 두번째 방법은 아예 스택 영역을 사용하지 않는 방법입니다.

메모리 초과라는 문제에 대해 조금이나마 도움이 되었으면 좋겠습니다. 

읽어주셔서 감사합니다.

백준 알고리즘 10026번을 풀던 와중, 채점 과정에서 런타임 에서(RecursionError)가 발생했습니다.

발생한 이유를 알아보니 다음과 같습니다.

-파이썬에서 정한 최대 재귀 깊이보다 재귀가 너무 많이 발생할 경우.

즉, 설정된 값보다 재귀가 많이 발생할 경우 RecursionError가 발생함을 알게되었습니다.

해결 방법은 다음과 같습니다.

- 재귀를 사용하지 않는 방식으로 코드 구현하기. (재귀를 활용한 코드를 반복문을 통한 코드로 변경)

- 파이썬 sys 모듈에 있는 sys.setrecursionlimit()을 이용하여 최대 재귀 깊이를 변경해주기

sys.setrecursionlimit(10000)

해당 문제에서 나올 수 있는 최대 깊이인 10000으로 값을 설정해주어 문제를 해결하였습니다.

*재귀함수의 경우 코드를 효율적으로 짤 수 있다는 장점이 있지만 반대로 함수에서 함수를 호출하는(자신을 재참조) 방식이기 때문에 메모리를 많이 잡아먹고 함수가 return 될 경우 메모리상에서 이전 함수 위치로 이동하기 때문에 반복문보다 시간이 오래걸릴 수 있습니다.

장점과 단점이 공존하는 만큼, 무조건적인 재귀의 활용보다는 재귀의 특성을 바탕으로 상황에 맞춰 적절히 활용하면 더욱 좋은 코드가 나오지 않을까 생각합니다.

읽어주셔서 감사합니다.