누군가 x의 y승은 얼마인가? 라고 물었다. 그에 대한 대답은?
그냥 x ** y를 리턴하면 되긴 하지만(Python 기준), 그거 말고.
일반적으로는 다음과 같이 구할 수 있다.
def pow(x, y):
answer = 1
for i in range(y):
answer *= x
return answer이 방법의 시간복잡도는 O(y)이다.
근데 더 빠르게 구할 순 없을까?
첨에는 단순하게, 저 방법은 루프를 y번 돌면서 하는거니까 루프횟수를 줄이면 된다고 생각했다.
만약 x의 y승을 구할 때 y가 짝수라면
x의 y승 = (x의 y/2승) * (x의 y/2승)
이고, y가 홀수라면
x의 y승 = (x의 y/2승) * (x의 y/2승) * (x)
이므로, 루프를 y번까지 돌 필요없이 y의 반 정도까지만 돌면 된다!고 생각해서 다음과 같이 코드를 짰었다.
def pow(x, y):
answer = 1
for i in range(y//2):
answer *= i
if y%2 == 0: # y가 짝수
return answer * answer
else: # y가 홀수
return answer * answer * 1그러나 이것의 시간복잡도도 O(y)이다. y가 커질수록 y의 반까지만 루프를 돈다는 건 의미가 없어지기 때문..
그러나 이것의 시간복잡도를 O(lg y)로 줄일 수 있는 방법이 있다.
우선 거듭제곱을 구할 때 루프가 아니라 재귀로도 구할 수 있다는 점에 힌트가 있다.
다음과 같이 코드를 짜면 재귀의 방법으로 거듭제곱을 구할 수 있다.
def pow(x, y):
if y == 0:
return 1
return x * pow(x, y - 1)물론 저것의 시간복잡도 역시 아직은 O(y)임.
그러나 예를 들어서, 2의 8승은 다음과 같은 과정으로 구할 수 있다는 점에 주목하자.
2의 8승 = (2의 4승) * (2의 4승)
2의 8승 = ((2의 2승) * (2의 2승)) * ((2의 2승) * (2의 2승))
.....
즉 다음과 같이 가능하다는 말.
def pow(x, y):
if y == 1:
return 1
return pow(x, y//2) * pow(x, y//2) # 물론 y가 짝수일 때만 가능근데 같은 내용에 대해 재귀를 두 번 호출할 필요는 없으니, 다음과 같이 하는게 더 빠르다.
def pow(x, y):
if y == 1:
return 1
sub_answer = pow(x, y//2)
return sub_answer * sub_answer # 물론 y가 짝수일 때만 가능아까 x의 y승을 구할 때 y가 홀수라면 x의 y승 = x의 y/2승 * x의 y/2승 * x라고 했었으니, y가 홀수일 때도 포함해 다음과 같이 완성 가능하다.
def pow(x, y):
if y == 1:
return 1
sub_answer = pow(x, y//2)
if y%2 == 0:
return sub_answer * sub_answer
else:
return sub_answer * sub_answer * x이렇게 하면 O(lg y)의 시간복잡도로 거듭제곱을 더 빠르게 계산할 수 있다.
내가 한 거랑 뭐가 달랐던 걸까?
우선 기본적인 접근법은 같았던 것 같다. y가 짝수인지 아닌지에 따라, 2/y까지만 곱한 걸 다루는 면에서.
그러나 y가 만약 16으로 주어졌을 때, x의 16승은 x의 8승 * x의 8승이 맞긴 하지만 x의 8승을 구하는 것도 다시 반으로 쪼개서 할 수 있다는 점을 간과했다.
'ALGORITHM > 알고리즘이론' 카테고리의 다른 글
| 크루스칼 알고리즘 - 최소 신장 트리 찾기 without codes (0) | 2023.02.03 |
|---|---|
| [알고리즘] 무식하게 풀기, 브루트포스(Brute Force) 그리고 어림짐작 (0) | 2021.11.15 |
| [알고리즘] 분리집합(Disjoint Set), a.k.a Union-Find알고리즘에 대해 (0) | 2021.10.02 |
| [알고리즘] 너비우선탐색, BFS를 파이썬으로 차근차근 구현해보자 (0) | 2021.09.19 |