백준 1629 - 곱셈

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

1629번: 곱셈

 

 

이 문제는 단순히 거듭제곱의 결과를 나누어 나머지를 출력하는 문제이다.

하지만, 일반적으로 사용하는 반복문을 사용하여 거듭제곱을 구할 경우, 시간초과가 난다.

 

왜냐하면 반복문을 이용한 거듭제곱은 N번 곱해줘야하므로 시간복잡도가 O(N)이 나오기 때문이다.

시간 복잡도를 줄이기 위해서는 분할 정복 이라는 알고리즘을 사용해야된다.

분할 정복 알고리즘을 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다.

 

따라서 분할정복 알고리즘에 대해 간단히 살펴보고 분할정복 알고리즘을 이용한 문제 풀이 코드 리뷰를 해보려고 한다.

 

 

 

분할정복이란?

여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다.

대표적으로는 퀵소트나 병합정렬이 있다.

 

 

분할 정복을 이용하여 거듭제곱을 계산하는 것은 지수 법칙을 활용한 것이다.

 

 

지수 법칙

이 간단한 지수법칙을 가지고 거듭제곱을 표현해 보려고 한다.

 

 

 

지수가 짝수일 때와 홀수일 때로 나누어 두 거듭제곱의 곱으로 표현할 수 있다.

 

 

---

따라서 이를 코드로 구현하면 다음과 같다.

def square(a, b):
    if b==1: # 지수가 1인 경우
        return a%c # 바로 계산

    tmp = square(a, b//2) # 거듭제곱으로 쪼개기

    if b%2==0: # 지수가 짝수인 경우
        return (tmp*tmp)%c
    else: # 지수가 홀수인 경우
        return (tmp*tmp*a)%c


a, b, c = list(map(int, input().split()))
print(square(a, b))

지수가 짝수일 때와 홀수일 때로 구분하여 구현하였다.

 

짝수일 경우엔, 그저 지수를 2분의 1했을 때의 거듭제곱 두 개를 곱하면 되므로

지수를 2분의 1했을 때의 거듭제곱을 tmp 변수에 넣어 계산하였다.

 

홀수일 경우엔, 밑과 지수를 2분의 1했을 때의 거듭제곱 두 개를 곱하면 되므로

이 또한 지수를 2분의 1했을 때의 거듭제곱을 tmp 변수에 넣어 계산하였다.

 

이제 tmp 변수에 담을 지수를 2분의 1했을 때의 거듭제곱을 어떻게 구하느냐?

반복문과 재귀함수 이렇게 2가지 방법이 있는데 나는 재귀함수를 이용했다.

그냥 그대로 지수를 2로 나누어 다시 재귀함수를 호출했다.

 

사실 이해가 될랑말랑이라서 다른 포스팅을 여러 개 찾아봤는데

그 중에서도 아래 포스팅이 이해가 잘 되었다.

https://velog.io/@grace0st/%EA%B3%B1%EC%85%88-%EB%B0%B1%EC%A4%80-1629%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC  → 문제 풀이 설명

 

https://hbj0209.tistory.com/43   → 원리 설명