글 읽기 - 두 풀이의 차이점이 궁금합니다

leecjs00 2년 전 0

첫 번째 풀이는 맨처음에 직관적으로 생각할법한 풀이고,

두 번째 풀이는 중간에 나머지를 리턴시키는, 잘 알법한 정답코드입니다.

궁금한 것은 첫 번째 풀이는 시간초과를 받았고 두 번째 풀이는 통과되었는데

두 풀이의 계산 횟수가 똑같을 것 같은데 왜 첫 번째 코드만 시간초과가발생하는지 궁금합니다.

정수론에 익숙해서 모듈로 개념을 모르는 것은 아닙니다.

생각하기에는 첫 번째 풀이대로 하면 중간에 숫자가 엄청 커질텐데, 똑같은 곱셈 한 번이어도

큰 숫자끼리 곱할때 작은 숫자끼리 곱하는 것 보다 오래걸리기 때문인가? 하는 궁금증이 듭니다.

(가령 12371298321809132977574412389078029314809234902314*12371298321809132977574412389078029314809234902314가 3*3보다 오래걸리는지 궁금합니다)

혹은 다른 이유로 시간의 차이가 발생하였다면 알려주시면 정말 감사하겠습니다

######################### 첫 번째 코드
A,B,C=map(int,input().split())
def power(a,b):

    if b==1:
        return a
    elif b==2:
        return a*a
    
    else:
        if b%2:
            return (power(a,b//2)**2)*a

        else:
            return (power(a,b//2)**2)

print(power(A,B)%C)


############################ 두 번째 코드
A,B,C=map(int,input().split())
def power(a,b,c):

    if b==1:
        return a%c
    elif b==2:
        return (a*a)%c
    
    else:
        if b%2:
            return ((power(a,b//2,c)**2)*a)%c

        else:
            return ((power(a,b//2,c)**2))%c

print(power(A,B,C))

djm03178 2년 전 5

네, 파이썬에서는 수가 커지면 곱셈에 걸리는 시간도 그만큼 오래 걸립니다.

CPU 레지스터를 사용하여 곱셈을 수행하는 C나 C++의 경우에는 표현 가능 범위 내에서는 일반적으로 곱셈의 시간이 항상 같지만, 파이썬은 큰 수의 곱셈을 계산하기 위해서 그를 2진수 자릿수 단위별로 끊어서 저장하고 빠른 곱셈 알고리즘을 통해 연산을 직접 구현합니다. 그래서 자릿수가 늘어나면 그에 비례하는 것 이상으로 많은 시간이 걸리게 됩니다.

leecjs00 2년 전 0

궁금증이 해결됐습니다 감사합니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 풀이의 차이점이 궁금합니다

leecjs00 2년 전 0

djm03178 2년 전 5

leecjs00 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말