0보다 큰 수가 주어졌을 때, 그 수가 2의 거듭제곱인지 판별하는 문제를 살펴보겠습니다.
예를 들어 입력값이 1024라면, 1024는 2^10이므로 출력 결과는 True가 됩니다.
문제 해결 접근 방식
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- n이 1보다 클 동안 반복합니다.
- 반복할 때마다 n을 2로 나눕니다.
- 반복이 끝난 후 n이 1이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
2의 거듭제곱(예: 1, 2, 4, 8, 16...)을 계속 2로 나누면 결국 정확히 1에 도달하기 때문입니다. 반면 2의 거듭제곱이 아닌 수는 나누는 과정에서 1이 되지 못한 채 소수 값이 됩니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, n):
while n > 1:
n /= 2
return n == 1
ob = Solution()
print(ob.solve(1024))
입력
1024
출력
True
더 효율적인 대안: 비트 연산 활용
위 방법은 시간 복잡도가 O(log n)입니다. 하지만 비트 연산을 사용하면 O(1)로 더 빠르게 판별할 수 있습니다.
2의 거듭제곱은 이진수로 표현했을 때 단 하나의 비트만 1입니다. 예를 들어 8은 1000, 16은 10000입니다. 따라서 n & (n - 1)의 결과가 0이면 n은 2의 거듭제곱입니다.
class Solution:
def solve(self, n):
return n > 0 and (n & (n - 1)) == 0
ob = Solution()
print(ob.solve(1024)) # True
print(ob.solve(1000)) # False
두 가지 방법 모두 올바른 결과를 제공하지만, 성능이 중요한 상황이라면 비트 연산 방식을 사용하는 것이 좋습니다.