[SW 정글 10일차] 전역 변수와 지역 변수 참조

오늘은 백준에서 문제를 풀면서 처음 경험하는 현상을 발견하여 그 현상과 원인을 정리해보려고 한다.

현상에 대한 원인을 알려주신 분은 코발트에서 개발자로 일하고 계신 이선협님이다.

 

 

내가 겪은 현상은?

먼저, 내가 푼 문제는 백준 알로리즘 저지에 있는 외판원 순환 2라는 문제이다.

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

완전탐색으로 모든 경우의 수를 구해 접근하려 했고 처음에는 시간초과가 났다.

시간복잡도를 줄이기 위해 반복문을 끝까지 안돌려도 되거나 반복문을 접근하지 않아도 되는 경우를 생각하여 if문으로 예외처리를 했다.

이러한 노력 끝에도 결국에 돌아오는 것은 시간초과였다.

내가 제출한 코드는 아래와 같다.

import sys
from itertools import permutations


N = int(sys.stdin.readline())
arr = []

for _ in range(N):
    arr.append(list(map(int, sys.stdin.readline().split())))


order_nums = permutations(range(N))
final_cost = 1000000 * N

for order_num in order_nums:
    if arr[order_num[-1]][order_num[0]] == 0:
        continue
    check = False
    cost = 0

    for idx in range(len(order_num) - 1):
        if arr[order_num[idx]][order_num[idx + 1]] == 0:
            check = True
            break

        cost += arr[order_num[idx]][order_num[idx + 1]]

        if cost >= final_cost:
            check = True
            break

    if check:
        continue

    cost += arr[order_num[-1]][order_num[0]]
    final_cost = min(final_cost, cost)

print(final_cost)

 

DFS로 접근하려고 했으나 코드를 구현하기 쉽지 않았고 결국에는 인터넷에서 답을 찾아보았다.

그러던 중, 나와 같은 접근방식을 가지고 완전탐색으로 푼 코드를 발견하였다.

하나 다른 점은 위 코드를 함수로 선언해주고 그 함수를 불러오는 형식이였다.

즉, 바꾼 코드를 보면 아래와 같다.

import sys
from itertools import permutations

def main():
    N = int(sys.stdin.readline())
    arr = []

    for _ in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))


    order_nums = permutations(range(N))
    final_cost = 1000000 * N

    for order_num in order_nums:
        if arr[order_num[-1]][order_num[0]] == 0:
            continue
        check = False
        cost = 0

        for idx in range(len(order_num) - 1):
            if arr[order_num[idx]][order_num[idx + 1]] == 0:
                check = True
                break

            cost += arr[order_num[idx]][order_num[idx + 1]]

            if cost >= final_cost:
                check = True
                break

        if check:
            continue

        cost += arr[order_num[-1]][order_num[0]]
        final_cost = min(final_cost, cost)

    print(final_cost)

main()

 

위 코드를 제출해보니 정답처리를 받게 되었고 어떠한 원인으로 이러한 현상이 나타나는지 궁금해지기 시작했다.

하지만, 원인을 알아보기 위한 나의 질문으로 인터넷을 통해 알 수 없었고 이전부터 참여 중인 코딩테스트 스터디에서 리더를 맡고 계신 현업 개발자분에게 질문을 드렸고 원인을 알게 되었다.

 

 

 

원인은 뭘까?

해당 현상의 원인은 전역 변수는 지역 변수보다 참조하는 것이 조금 더 느리다는 것이다.

위 코드에서 통과한 코드는 함수 안에 코드를 선언해서 그 함수를 불러온 것으로 전역 변수가 아닌 지역 변수를 참조한 것이다.

하지만 시간초과를 받은 코드는 코드 자체를 실행시키는 것이기 때문에 전역 변수를 참조하게 된다.

전역 변수를 참조하는 코드와 지역 변수를 참조하는 코드 실행 시간을 비교하고 실행 시간 차이가 나는 이유를 알 수 있는 좋은 글이 있어 공유하려고 한다.

https://folivora.tistory.com/66

[Python] 전역 변수(Global variable)는 얼마나 느릴까?

 

위 블로그를 보면 바이트 코드를 비교했을 때,

전역 변수에서 사용된 바이트 코드에서 LOAD_NAME은 table lookup을 하기 때문에 기본적으로 loop variable을 스택에 배치하는 LOAD_FAST에 비해서 느릴 수 밖에 없다는 말이 있다.

지역 변수를 스택에 배치하여 참조한다는 말은 메모리 접근 방식을 말하는 것으로 이해가능한데

table lookup이 무엇인지 궁금하여 찾아보았다.

아래 웹 페이지를 접근할 수 있었고 간단히 말하면 table lookup은 데이터베이스에 key, value 형태로 접근한다는 뜻인 것같다.

혹시 이 부분에 대한 설명이 틀리다면 댓글 부탁드립니다.

https://www.pythonpool.com/python-lookup-table/

Learning About the Python Lookup Table

 

 

이렇게 함수를 정의해서 함수를 불러오는 답안 제출 형식이 잘못된 접근인지는 모르겠지만 앞으로 시간초과가 나면 한번 쯤은 사용할 것같다.

나와 같은 현상을 겪어 원인을 궁금하던 사람들이 조금이나마 궁금증을 해소했으면 좋겠다.

 

 

 

---

오늘은 이번 주차 마지막 날로 제공된 문제들을 다시 한번 보며 문제 해결방법과 알고리즘 기초를 다지려고 했다.

이번 주차에 본 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편이라는 책 이외에 SW 사관학교 정글에서 교재로 삼은 책이 있다.

Introduction to Algorithms라는 책인데 알고리즘을 공부하는 사람들에게는 꽤 유명한 책인 것같다.

정렬 알고리즘에 대한 챕터가 꽤 잘 잡혀있는 것같아 읽어보려고 했으나 접근장벽이 높아 어려움을 느꼈다...

하지만, 이 책은 나의 알고리즘 지식 향상에 도움이 된다는 생각이 들었고 이번주 일요일에 정렬 파트를 반드시 읽을 것이다.

물론, 한 번에 모든 것을 이해하기는 어렵겠지만 반복학습을 통해 최대한 이해해보려고 노력할 것이다.

 

 

---

<참고 자료>

https://folivora.tistory.com/66

https://www.pythonpool.com/python-lookup-table/