[알고리즘] 분할 정복 & 백준(곱셈, 행렬 제곱)

분할 정복(Divide & Conquer)

분할 정복은 문제를 여러개로 나누어서 푸는 알고리즘이다. 교수님께서 미친듯이 강조해서 "디바이드앤퀀쿼"만 기억이 난다..

 

* 동적 계획법(DP)과의 차이점

1. 동적 계획법은 분할한 문제들이 서로 영향을 미침.

2. 분할 정복은 분할한 문제들이 서로 영향을 미치지 않음.

 

* 분할 정복의 필요조건

1. 문제를 나눌 수 있어야 한다.

2. 부분 문제의 답을 이용하여 원래 문제의 답을 계산하는 방법이 있어야 한다.

 

* 분할 정복의 알고리즘의 접근법

1. 분할: 문제를 작은 문제로 분할하는 과정

2. 정복: 분할한 작은 문제들을 해결

3. 조합: 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합한다.

 

분할 정복을 이용한 거듭제곱

먼저, 거듭제곱이란 주어진 수를 주어진 횟수만큼 곱하는 연산이다.

일반적인 방법으로 거듭제곱을 푼다면 '재귀함수로 구현하는 방법'과 '반복문으로 거듭제곱을 구현하는 방법'이 있다.

 

[재귀함수 거듭제곱]

# 재귀함수 거듭제곱
def pow(a, n):
    if n == 0:
        return 1
    else:
        return a * pow(a, n-1)

[반복문 거듭제곱]

# 반복문 거듭제곱
def pow(a, n):
    result = 1
    for i in range(n):
        result *= a
    return result

위와 같은 방식은 n번만큼의 연산을 요구하기 때문에 n이 클수록 성능이 낮다.

굳이 따지자면 반복문이 재귀함수보다 성능이 좋지만, 결과적으로 시간복잡도가 O(n)이기에, n이 커질수록 성능이 좋지 않다.

시간복잡도를 줄여 개선된 알고리즘을 만들어야 한다. 바로 거듭제곱의 성질을 통해 분할정복을 이용하여 개선할 수 있다.

 

두 거듭제곱 간 밑인 a가 같을 때, a의 n제곱과 a의 m제곱을 곱한 수는 두 지수 n과 m을 더한 값을 지수로 취하는 a^(n+m)으로 표현할 수 있다. 이를 활용하면, a^n은 a^(n/2)*a^(n/2)로 표현할 수 있다. 이러한 접근 방식은 n을 매번 2로 나눠 더 작은 문제로 만들어 해결하는 분할정복 방식이라고 할 수 있다.

def power(a, n):
    if n == 0:
    	# a^0 = 1 이므로 1 리턴
        return 1 
    
    if n == 1:
        return a
    
    if n % 2 == 0: # n이 짝수일 때
        return power(a, n//2) * power2(a, n//2)
    
    else: # n이 홀수일 때
        return power(a, n//2) * power2(a, n//2) * a

효율적이게 보이지만 위 함수도 O(n)의 시간복잡도를 가진다.

이를 줄이기 위해서는 똑같은 값이 나오는 power(a, n//2)를 두 번 곱해주면 호출을 반으로 줄일 수 있다.

 

[분할정복 거듭제곱]

def power(a, n):
    if n == 0:
    	# a^0 = 1 이므로 1 리턴
        return 1 
    
    x = pow(a, n//2, c)
    
    if n % 2 == 0: # n이 짝수일 때
        return x * x    # x를 두 번 곱해줘서 power 함수의 호출을 반으로 줄일 수 있다.
    
    else: # n이 홀수일 때
        return x * x * a

이 방식은 O(logN)의 시간복잡도 안에서 거듭제곱 연산을 수행할 수 있다.

 

결론: 분할정복에서 불필요한 반복(같은 재귀함수 호출)은 시간복잡도의 급격한 상승을 유발한다.

같은게 보이면 묶고 나눠.

---

1. 1629: 곱셈

문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 

=> 10의 11제곱을 12로 나누면 몇인가? 10^11%12

 

[풀이 1]

10의 11제곱을 12로 모듈러 연산(mod)을 한다. 

 

[풀이 2] * (다시 돌아가서) 분할 정복의 알고리즘의 접근법

1. 분할: 문제를 작은 문제로 분할하는 과정

위 문제 10^11%12에서 두 가지 수학 법칙을 적용하면 분할이 된다.

 

1) 지수법칙

지수법칙은 위에서 설명한 분할 정복의 거듭제곱과 동일하다.

지수이 홀수인 경우와 짝수인 경우를 나눌 수 있다.

=> 10^11=(10^5)*(10^5*10)로 분할할 수 있다.

 

2) 나머지 분배 법칙

(AxB) % C = ((A%C) x (B%C)) % C 

나머지 분배 법칙에 의하여

=>  ((10^5 %12)∗(10^5∗10 %12))%12로 분할할 수 있다.

   

즉, 10^11 %12는 10^5 %12와 10^5*10 %12의 연산으로 구할 수 있다.(분할)
*만약 지수가 짝수인 경우 예를 들어 10^12%12는 ((10^5 %12)∗(10^5 %12))%12로 구할 수 있다.

2. 정복: 분할한 작은 문제들을 해결

이 문제의 base_case 는 10^1 %12= 10 (정복)

 

3. 조합: 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합한다.

 10^2 %12 = ((10^1 %12) * (10^1 %12))%12
                  = (10 * 10) %12 = 4 (조합) 

# SW 오빠 코드
a,b,c=map(int,input().split())

def mod_light(a,b):
	if b==1:            # base case          	
    	return a%c      # base case 의 해답 .     
	else:               # recursive case 
		tmp=mod_light(a,b//2)  
		if b%2==0:
			return (tmp*tmp)%c
		else:
			return (tmp*tmp*a)%c

완벽하게 직관적인 함수 mod_light의 흐름...~

---

# 1629: 곱셈
# 자연수 A를 B번 곱한 수를 알고 싶다.
# 단, 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구한다.

import sys
sys.setrecursionlimit(10**6)
sys.stdin = open('input.txt', 'r')
num = list(map(int, sys.stdin.readline().split()))

a, b, c = num[0], num[1], num[2]

def power(a, n, z):
    if n == 0:	# a^0 = 1 이므로 1 리턴
        return 1 
    x = pow(a, n//2, z)
    if n % 2 == 0: # n이 짝수일 때
        return x * x % z   # x를 두 번 곱해줘서 power 함수의 호출을 반으로 줄일 수 있다.
    else: # n이 홀수일 때
        return x * x * a % z

print(power(a, b, c))

JH 오빠 코드를 보고 나니 입력부터 빙빙 돌아간 부분이 있다.

num = list(map(int, sys.stdin.readline().split()))
a, b, c = num[0], num[1], num[2]

로 값들을 받았는데, 굳이 list로 안 받고 a, b, c = map(int, input().split())으로 한 줄로 해결할 수 있다. 

# JH 오빠 코드
a, b, c = map(int, input().split())

def solution(a, b):
    global c
    if b <= 1:
        return 1 if b == 0 else a%c
    if b % 2 == 0:
        return solution((a%c)*(a%c), b//2) % c
    else:
        return ((solution((a%c)*(a%c), b//2) % c) * (a%c))%c

print(solution(a, b))

 

2. 10830: 행렬 제곱

행렬 곱셈부터 다시 이해해야했기에 따로 정리해뒀다. https://bo5mi.tistory.com/137 

[알고리즘] 행렬 곱셈, 행렬 제곱

---

공부 참고 블로그:

About 분할정복: https://puleugo.tistory.com/83

거듭제곱 알고리즘: https://mygumi.tistory.com/319

거듭제곱에 대한 정확하고 깔끔한 설명: https://seongonion.tistory.com/88

From 우리조였던 SW 분할정복을 이용한 백준 곱셈의 직관적 풀이: https://velog.io/@sungwoo/%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5-%EB%B0%B1%EC%A4%80-1629%EB%B2%88-%EA%B3%B1%EC%85%88