2의 거듭제곱 판단하기 "어떤 자연수가 2의 거듭제곱임을 판별하라." 주어진 숫자가 \(2^{63}\)이하의 자연수라고 하면 당연히 2, 4, 8, 16, ... 순차적으로 확인해서 2의 거듭제곱인지 아닌지 판별하려고 할 것이다. (물론 unsigned long long type으로 말이다.) 쿼리가 m개라면 \(O(63m)\) 의 시간복잡도를 가질 것이다. 물론 이것만으로도 충분히 빠른 판단이라 생각되지만 특별한 방법을 찾게 되어서 블로그에 남기기로 하였다. 결론부터 말하면 어떤 자연수 \(n\)에 대해 \[(n\ \&\ (-n)) == n\] 이면 그 수는 2의 거듭제곱이다. 결론을 알았으니 맞는지 잠시 생각해보자. 1) 우리가 찾고자 하는 2의 거듭제곱 수 \(n\)의 비트표현을 살펴보면 한 자리만..
안녕하세요. 오늘은 피보나치 수열에 대해 다루어 보려고 합니다. 출처 : https://www.acmicpc.net/blog/view/28 피보나치 수열은 일반적으로 재귀형태로 구현을 많이 합니다.하지만 이런 방식은 n이 커질수록 시간이 기하급수적으로 오래걸립니다.그래서 좀 더 좋은 방식들에 대해 찾다보니 위의 링크에서 많은 정보를 얻었습니다.위 내용에 추가적으로 살을 붙여서 정리해 보겠습니다. Contents재귀형식재귀 + 저장(메모이제이션)을 이용한 방식for-loop를 이용한 방식피보나치 수의 나머지(피사노 주기)피보나치 관계식의 행렬표현+ 피보나치 수열의 합 재귀형식재귀형식은 모두 다 아시다시피 아래와 같이 구현됩니다.0, 1, 1, 2, 3, 5, 8, ... 이므로 n이 1보다 작으면 n을 아..