알고리즘 문제에서 자주 등장하는 못생긴 수(Ugly Number)란 소인수가 오직 2, 3, 5로만 구성된 양의 정수를 의미합니다. 이번 글에서는 파이썬을 활용해 주어진 수 n이 못생긴 수인지 판별하는 프로그램을 작성해 보겠습니다.
예를 들어 n = 18이라고 가정해 봅시다. 18을 소인수분해하면 2 × 3 × 3이 되므로 소인수가 2와 3뿐입니다. 따라서 이 경우 결과는 True가 됩니다.
문제 해결 접근 방식
못생긴 수를 판별하는 핵심 아이디어는 다음과 같습니다.
- n이 음수라면 즉시
False를 반환합니다. - 허용되는 소인수 목록 [2, 3, 5]를 준비합니다.
- 각 인수에 대해 n이 해당 인수로 나누어 떨어지는 동안 계속 나눕니다.
- 모든 나눗셈이 끝난 후 n이 1이면
True, 그렇지 않으면False를 반환합니다.
이 방법이 작동하는 이유는 간단합니다. n의 소인수 중 2, 3, 5 외에 다른 수(예: 7, 11 등)가 포함되어 있다면, 2·3·5로 나눌 수 있는 부분을 모두 제거한 뒤에도 남는 값이 1이 아니기 때문입니다.
파이썬 구현 예제
class Solution:
def solve(self, n):
if n < 0:
return False
factor = [2, 3, 5]
for i in factor:
while n % i == 0:
n /= i
return n == 1
ob = Solution()
print(ob.solve(18))입력
18
출력
True
코드 동작 원리 상세 분석
위 코드를 단계별로 살펴보겠습니다.
- 음수 검사: n이 0보다 작으면 소인수 판별 대상이 아니므로 바로
False를 반환합니다. - 인수 목록 초기화: [2, 3, 5] 리스트로 허용되는 소인수를 정의합니다.
- 나눗셈 반복: 각 인수 i에 대해 n이 i로 나누어 떨어지는 한 계속해서 n을 i로 나눕니다.
- 최종 판별: 모든 처리가 끝난 후 n이 1이면
True, 아니면False를 반환합니다.
n = 18일 때의 실제 실행 과정은 다음과 같습니다.
- i = 2: 18 % 2 == 0이므로 n = 9
- i = 3: 9 % 3 == 0이므로 n = 3, 다시 3 % 3 == 0이므로 n = 1
- i = 5: 1 % 5 ≠ 0이므로 변화 없음
- 최종적으로 n == 1이므로
True반환
참고: 정수 나눗셈 사용하기
파이썬 3에서 / 연산자는 실수(float) 나눗셈을 수행하므로, n이 부동소수점 타입으로 변환될 수 있습니다. 더 안전한 코드를 원한다면 정수 나눗셈 연산자 //=를 사용하는 것이 좋습니다.
while n % i == 0:
n //= i시간 복잡도
이 알고리즘은 나눗셈이 진행될 때마다 n이 최소 절반 이상 감소하므로, 시간 복잡도는 O(log n)으로 매우 효율적입니다. 큰 수에 대해서도 빠르게 판별할 수 있습니다.
마무리
못생긴 수 판별은 소인수분해의 기본 개념을 활용한 대표적인 알고리즘 문제입니다. 위에서 소개한 반복 나눗셈 방식만 익혀두면 코딩 테스트나 알고리즘 연습에서 손쉽게 활용할 수 있습니다.