거듭제곱 C^n 을 구하는 가장 쉬운 방법은 C를 n 번 곱하는 것이다.
하지만 너무 '무식한' 방법이다.
거듭제곱의 성질을 활용한 아래의 점화식을 이용하면, Divide & Conquer 를 통해 log 2 n 번의 곱셈 만으로 계산을 마칠 수 있다.
원리는 간단하다.
지수를 계속 1/2 로 분할하여 지수가 0 혹은 1이 될 때까지 나누고, 나뉘어진 문제를 합치면서 곱해 나간다.
지수가 홀수인 경우 1/2로 분할하면 지수가 정수형을 띄지 않게 되므로 1을 빼서 짝수로 만들고 1/2 로 분할한 다음 곱을 따로 한 번 해 준다.
이를 루비로 구현해 보았다.
(링크를 통해 코드 하이라이트가 적용된 코드를 볼 수 있다.)
하지만 너무 '무식한' 방법이다.
거듭제곱의 성질을 활용한 아래의 점화식을 이용하면, Divide & Conquer 를 통해 log 2 n 번의 곱셈 만으로 계산을 마칠 수 있다.
c^n = c^(n/2) * c^(n/2), n is even
c^((n-1)/2) * c^((n-1)/2) * c, n is odd
c, n == 1
1, n == 0
원리는 간단하다.
지수를 계속 1/2 로 분할하여 지수가 0 혹은 1이 될 때까지 나누고, 나뉘어진 문제를 합치면서 곱해 나간다.
지수가 홀수인 경우 1/2로 분할하면 지수가 정수형을 띄지 않게 되므로 1을 빼서 짝수로 만들고 1/2 로 분할한 다음 곱을 따로 한 번 해 준다.
이를 루비로 구현해 보았다.
(링크를 통해 코드 하이라이트가 적용된 코드를 볼 수 있다.)
=begin
거듭제곱 의 점화식
c^n = c^(n/2) * c^(n/2), n is even
c^((n-1)/2) * c^((n-1)/2) * c, n is odd
c, n == 1
1, n == 0
이를 이용하여 divide and conquer 로 c를 n 번 곱하지 않고 c^n 을 구한다
=end
def power(number, exponent)
return 1 if 0 == exponent
return number if 1 == exponent
(0 == exponent & 1) ?
power(number, exponent / 2) ** 2 :
(power(number, (exponent - 1) / 2) ** 2) * number
end
puts "2^200 = " + power(2, 200).to_s
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| Backtracking : 미로 찾기 (0) | 2009/05/07 |
|---|---|
| Divide & Conquer : n 번째 피보나치 수열의 수를 구하기 (2) | 2009/05/06 |
| Divide & Conquer : 거듭제곱 알고리즘 (0) | 2009/05/06 |
| 해시 검색 - in Ruby (0) | 2009/03/18 |
| 이진 검색 - in Ruby (0) | 2009/03/18 |
| 트리 정렬 - in Ruby (0) | 2009/03/18 |
