양의 정수 n이 주어졌을 때, 해당 숫자의 콜라츠(Collatz) 수열 길이를 구하는 문제입니다. 콜라츠 수열은 다음 규칙에 따라 순차적으로 생성됩니다.
- n이 짝수인 경우: n = n / 2
- n이 홀수인 경우: n = 3n + 1
이 과정을 반복하다가 n이 1이 되면 수열은 종료됩니다.
예를 들어 입력값이 n = 13이라면, 수열은 [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]이 되고, 요소가 총 10개이므로 출력 결과는 10입니다.
해결 방법
이 문제는 다음 단계로 해결할 수 있습니다.
- num이 0과 같다면 0을 반환합니다.
- length 변수를 1로 초기화합니다.
- num이 1이 아닌 동안 다음을 반복합니다.
- num이 짝수면 num / 2, 홀수이면 3 * num + 1로 값을 갱신합니다.
- length 값을 1씩 증가시킵니다.
- 반복이 끝나면 length를 반환합니다.
예제 코드
class Solution:
def solve(self, num):
if num == 0:
return 0
length = 1
while num != 1:
num = (num / 2) if num % 2 == 0 else (3 * num + 1)
length += 1
return length
ob = Solution()
print(ob.solve(13))입력
13
출력
10
동작 원리 살펴보기
n = 13일 때 코드의 실행 흐름을 단계별로 확인하면 다음과 같습니다.
- 13 → 40 (홀수이므로 3×13+1)
- 40 → 20 (짝수이므로 나누기 2)
- 20 → 10
- 10 → 5
- 5 → 16 (홀수이므로 3×5+1)
- 16 → 8
- 8 → 4
- 4 → 2
- 2 → 1 (종료)
시작 값인 13까지 포함하여 총 10개의 숫자가 생성되었으므로 결과는 10이 됩니다. 이 알고리즘은 수열이 1에 도달할 때까지 반복하는 단순한 시뮬레이션 방식으로, 시간 복잡도는 입력 크기에 따라 달라지지만 일반적으로 매우 빠르게 수렴하는 것으로 알려져 있습니다. 참고로 콜라츠 추측(Collatz Conjecture)은 "모든 양의 정수가 결국 1에 도달한다"는 아직 증명되지 않은 유명한 난제이기도 합니다.