시간을 줄이는 테크닉 - 파이썬에서 함수형 코드를 적극적으로 활용해야하는 이유(+ if __name__ == "__main__"의 활용?)

알고리즘 문제를 풀다보면, 함수형 코드로 작성하는데 시간안에 통과하지만,

 

그렇지 않았을때 시간 초과나는 경우가 있다

 

기분탓인줄 알았는데

 

17467번: N! mod P (2) (acmicpc.net)

17467번: N! mod P (2)

 

이렇게 쓰면 통과를 못하는데

 

n,p = map(int,input().split())

if n == p-1:
    
    answer = p-1

elif n > p - n:

    answer = 1
    
    for i in range(n+1,p-1):
        
        result *= i
        result %= p
    
    answer = pow(answer,p-2,p)

else:
    
    answer = 1
    
    for i in range(1,n+1):
        
        answer *= i
        answer %= p

print(answer)

 

중간에 팩토리얼을 계산하는 부분을 def 함수로 정의하고, 함수 호출하는걸로 바꿨더니 통과하더라고

 

def factorial(a,b):
    
    result = 1
    
    for i in range(a,b):
        
        result *= i
        result %= p
    
    return result

n,p = map(int,input().split())

if n == p-1:
    
    answer = p-1

elif n > p - n:
    
    answer = factorial(n+1,p-1)
    
    answer = pow(answer,p-2,p)

else:
    
    answer = factorial(1,n+1)

print(answer)

 

 

우연이라고 생각할 수 있지만 다음 문제도 보면

 

 

16958번: 텔레포트 (acmicpc.net)

16958번: 텔레포트

 

플로이드 워셜로 최단거리를 찾을때 다음과 같이 작성하면 통과하지 못하고

 

from sys import stdin

INF = 1e9

n,t = map(int,stdin.readline().split())

graph = [[INF]*(n+1) for _ in range(n+1)]

city = [0]

for _ in range(n):
    
    s,x,y = map(int,stdin.readline().split())

    city.append((s,x,y))

for a in range(1,n+1):
    
    for b in range(1,n+1):
        
        if a != b:
            
            x = abs(city[a][1] - city[b][1]) + abs(city[a][2] - city[b][2])
            
            if x > t and city[a][0] == 1 and city[b][0] == 1:
                
                graph[a][b] = t
            
            else:
                
                graph[a][b] = x
                
for k in range(1,n+1):

    for a in range(1,n+1):

        if k == a:
            continue

        for b in range(1,n+1):

            if a == b:
                continue

            if graph[a][b] > graph[a][k] + graph[k][b]:

                graph[a][b] = graph[a][k] + graph[k][b]
    

m = int(stdin.readline())

for _ in range(m):
    
    a,b = map(int,stdin.readline().split())

    print(graph[a][b])

 

플로이드 워셜을 하는 부분을 함수형 def floyd()로 정의하고 제출하면 통과함

 

from sys import stdin

INF = 1e9

def floyd(graph,city):

    for k in range(1,n+1):
    
        for a in range(1,n+1):
            
            if k == a:
                continue

            for b in range(1,n+1):
                
                if a == b:
                    continue

                if graph[a][b] > graph[a][k] + graph[k][b]:

                    graph[a][b] = graph[a][k] + graph[k][b]
    
    return graph

n,t = map(int,stdin.readline().split())

graph = [[INF]*(n+1) for _ in range(n+1)]

city = [0]

for _ in range(n):
    
    s,x,y = map(int,stdin.readline().split())

    city.append((s,x,y))

for a in range(1,n+1):
    
    for b in range(1,n+1):
        
        if a != b:
            
            x = abs(city[a][1] - city[b][1]) + abs(city[a][2] - city[b][2])
            
            if x > t and city[a][0] == 1 and city[b][0] == 1:
                
                graph[a][b] = t
            
            else:
                
                graph[a][b] = x
                
graph = floyd(graph,city)

m = int(stdin.readline())

for _ in range(m):
    
    a,b = map(int,stdin.readline().split())

    print(graph[a][b])

 

인터넷에 찾아보니 어떤 사람도 이 현상을 관찰했더라고

 

https://8iggy.tistory.com/155

Python 함수 코드가 일반 코드보다 빠른 이유

 

다음을 보면 $O(10^{8})$을 도는데 2배차이가 난다..

 

이 정도면 꽤 유의미하다

 

 

 

무슨 말인지 어렵지만..

 

대충 변수를 저장하는 방식에 차이가 있다고 한다

 

함수 내부에서 수행하면 STORE_FAST에 저장되어 사용되니 더 빠르나본데??

 

함수 밖 global에 사용되면 STORE_NAME에 저장되어 사용되니 과정이 많아서 오래걸리나봐

 

이름부터 속도차이가 느껴지긴하지

 

실제로 함수 내부에 global 변수를 사용하면 속도 차이가 없어진다

 

 

 

다른 알고리즘 고수들이 python으로 작성한 코드를 보면 main()함수를 만들고,

 

그 안에 핵심코드를 집어넣은 다음 

 

if __name__=="__main__":
    main()

 

으로 제출하는 사람들이 있는데 아마 위와 같은 함수형 코드로 작성해서 시간복잡도에서 이득을 얻고자 하기 위함같다

 

https://hyoje420.tistory.com/45

[Python]if __name__ == "__main__"

 

1) 파이썬은 main()함수가 없고..(c++이나 java는 있었지)

 

2) 직접 실행시킨 모듈은 __name__이라는 변수에 __main__이 들어가고 import 시킨 모듈을 실행하면 해당 모듈 이름이 들어간다.

 

3) if __name__ == "__main__":으로 직접 실행시켰을때 실행되길 원하는 문장만 사용하여 효율적인 프로그래밍을 가능하게 한다.

 

만약에 if __name__ == "__main__":을 사용할 경우에 주의해야할 점은..

 

함수의 parameter를 명확하게 줘야한다는 것인데

 

예를 들어 다음 코드는 nameerror가 난다.. 왜 그럴까?

 

def sum(a,b):
    
    result = 0

    for i in range(n):
        
        result += (a+b)

    return result

def main():
    
    a = int(input())
    b = int(input())
    n = int(input())

    c = sum(a,b)

    print(c)

if __name__ == "__main__":
    
    main()

 

다음과 같이 sum()함수에서 n을 찾지 못하기 때문이다

 

 

 

이건 n이 global이 아닌 main() 내부에서 정의된 local variable이라 그렇다.

 

if __name__=="__main__": 안에 n을 정의해놓으면 n이 global이라 parameter로 안줘도 접근 가능하다

 

def sum(a,b):
    
    result = 0

    for i in range(n):
        
        result += (a+b)

    return result

def main():
    
    a = int(input())
    b = int(input())

    c = sum(a,b)

    print(c)

if __name__ == "__main__":
  
    n = int(input())
    main()

 

물론 이 경우에는 n = int(input())이 먼저 실행되고 main()이 실행되기 때문에

 

n,a,b 순서로 입력받는다

 

if __name__ == "__main__": 내부가 아닌 아예 전체 외부에 n을 정의해도 실행되긴 한다.

 

n = int(input())을 sum()함수 위에 쓰거나..

 

n = int(input())

def sum(a,b):
    
    result = 0

    for i in range(n):
        
        result += (a+b)

    return result

def main():
    
    a = int(input())
    b = int(input())

    c = sum(a,b)

    print(c)

if __name__ == "__main__":

    main()

 

n = int(input())을 main()함수 다음, if __name__ == "__main__": 전에 실행하거나

 

def sum(a,b):
    
    result = 0

    for i in range(n):
        
        result += (a+b)

    return result

def main():
    
    a = int(input())
    b = int(input())

    c = sum(a,b)

    print(c)

n = int(input())

if __name__ == "__main__":

    main()

 

그러면 위에서부터 아래로 코드가 실행되기 때문에 n,a,b 순서로 입력받는건 동일하다

 

a,b,n 순서로 입력받고 싶다면 a,b,n을 main에서 정의하고 sum 함수의 parameter로 a,b,n 3개를 주자.

 

def sum(a,b,n):
    
    result = 0

    for i in range(n):
        
        result += (a+b)

    return result

def main():
    
    a = int(input())
    b = int(input())
    n = int(input())

    c = sum(a,b,n)

    print(c)

if __name__ == "__main__":

    main()