[알고리즘] 분할 정복을 이용한 거듭제곱

거듭제곱

식 [a^b * a^c ] 에서 지수를 2로 나눈뒤 두 수를 곱해도 값은 값이 나온다. 아래 예시를 보자.

1. 지수가 짝수) 2의 8제곱 = 2^4 * 2^4로 나타낼 수 있다.
2. 지수가 홀수) 2의 11제곱 = 2^5 * 2^5 * 2로 나타낼 수 있다.

이를 식으로 풀면

n은 짝수) 2^n
: 2^(n/2) * 2^(n/2)

n은 홀수) 2^n
: 2^(n/2) * 2^(n/2) * 2 와 같다.

 

 

이를 재귀 함수로 구현하면

 

num은 밑, exp는 지수

 

이를 이용해서 백준 1629번 '곱셈' 문제를 풀었다.

 

틀린 코드

처음에 위처럼 풀었는데 계속 틀렸다고 했다.

이후 result 변수를 따로 선언해서 tmpNum을 바로 제곱한 후 div로 나눈 나머지 값을 넘겨줬다.

 

정답 코드

 

---

 

알고리즘 개념글은 처음이라 글 수준이 낮은거 같다.

 

손으로 써가면서 공부하는 타입인데 테블릿 같은게 없어서 깔끔하게 정리해서 포스팅하기가 어렵다.

 

공부한 노트를 사진 찍어 올리던가 해야겠다.