제곱, 제곱근 구현하기

---

우선은 제곱근은 바빌론방법을 사용하였고,

제곱은 dp를 사용했습니다.

 

사실 제곱을 일반적으로 구현하면, 시간복잡도가 O(n)이 되는데,

저가 사용한 방법은 dp입니다. 시간복잡도는

 

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

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

 

 

먼저 바빌론방법을 이용한 제곱근을 구하는 함수입니다.

#include <bits/stdc++.h>

double squareRoot(double n){
	double x = n;
	double y = 1;
	double e = 0.000001;
	
	while(x - y > e){
		x = (x + y) / 2;
		y = n / x;
	}
	
	return x;
}

int main() {
	std::cout.precision(14);
	std::cout << squareRoot(2) << '\n';
}

 

 

그다음은 dp를 이용한 제곱함수입니다.

#include <bits/stdc++.h>

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

int Power(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);
	
	std::cout << Power(2, 4) << '\n';
	std::cout << Power(2, 2) << '\n';
	std::cout << Power(3, 3) << '\n';
	std::cout << Power(3, 2) << '\n';
	std::cout << Power(3, 4) << '\n';
}

 

 

궁금한 부분있으시면 질문부탁드립니다.

---