주니어 개발자 성장기

거듭 제곱을 구할 때 우리는 보통 $$a^n = a*a*a* \cdots *a$$ 를 떠올린다. 즉, a를 n번 무식하게 곱하는 것이다. 하지만 이것을 컴퓨터가 연산한다면, 시간복잡도가 어떻게 될까? int main(void) { int a, n; cin >> a >> n; //a^n을 선형 시간 복잡도로 곱한다. long long result = 1; for (int i = 0; i a >> n; ll result = 1; while (n > 0) { //n이 홀수일 경우 즉, 이진수의 가장 아래 자리수가 1인 경우 if (n % 2 == 1) result = (a * result); a = (a * a); //이 비트 연산은 수슬 이진수 자릿수를 1..