🔪소개및 개요

💎개요

이번에는 제곱수를 O(1)로 구하는 방법에 대해서 써보겠습니다.

예를들어서, 처음 2의 2제곱을 하면 O(n)이고, 그다음은 2의 e제곱을 하면 시간복잡도는 O(n-e)가 됩니다.

그리고, 이미 제곱했었던 수라면 시간복잡도는 O(1)입니다.

🔪구현

💎소스코드

일반적인 제곱수 구하기

// 일반적인 제곱수 구하기
#include <bits/stdc++.h>

int Power_Common(int n, int e) {
	int result = 1;
	for (int i = 0; i < e; ++i) {
		result = result * n;
	}
	return result;
}

int main() {
	for (int i = 0; i < 1e9; ++i) Power_Common(5, 5);
}

DP를 사용한 제곱수 구하기

// DP를 사용한 제곱수 구하기
#include <bits/stdc++.h>

constexpr int MAX = 1001;
int arr[MAX][MAX], num[MAX];

int Power_DP(int n, int e) {
	if (arr[n][e] != 0) return arr[n][e];
	arr[n][0] = 1;

	for (int i = num[n]; i <= e; ++i) {
		arr[n][i] = std::max(arr[n][i - 1] * n, arr[n][i]);
	}

	num[n] = std::max(num[n], e);
	return arr[n][e];
}

int main() {
	std::fill(num, num + MAX, 1);
	for(int i=0;i<1e9;++i) Power_DP(5, 5);
}

💎실행

일반적인 제곱수 구하기

DP를 사용한 제곱수 구하기

와우...ㄷㄷ... 속도가 대략 4배정도 더빨랐습니다.
dp를 사용한 제곱수구하기는 제곱수를 많이 사용해야할때, 사용하면 효율적이겠군요!

💎설명

시간복잡도를 최소화하기위해서 dp를 썼습니다.
dp같은경우는 시간을 가져오고, 메모리를 내주는 알고리즘이죠.

사실 소스코드는 즉석으로 만들어서 올린거라서, 그냥 감각적으로 만들었습니다.

num[n] : n제곱의 현재 구한 최대 지수량을 의미합니다.
arr[n][i] : n의 i번째 제곱수를 의미합니다.

1. dp배열에 0이아닌수면 바로 그 수 반환
2. 우선 제곱수에 무엇을 곱하든간에 모두 0제곱은 1이므로, 1로 채워줍니다.
3. num[n]부터 e까지 순회하면서 dp돌려줍니다.
   이때, arr[n][i]의 값은 arr[n][i - 1] * n와 arr[n][i]중 더 큰수가 됩니다.
4. 그다음 num[n]의 최댓값을 갱신해줍니다.
5. arr[n][e]을 반환해줍니다.

🔪마치며...

궁금한 부분있으시면 댓글로 질문주세요!