콜라츠 추측이란?
콜라츠 추측(Collatz Conjecture)은 수학에서 가장 유명한 미해결 문제 중 하나로, 임의의 자연수에 특정 규칙을 반복해서 적용하면 항상 1에 도달한다는 가설입니다. 이 튜토리얼에서는 C++을 사용해 콜라츠 추측을 구현하고, 주어진 숫자가 1에 도달할 수 있는지 확인하는 프로그램을 만들어 보겠습니다.
주어진 자연수 n에 대해 다음 두 가지 연산 중 하나를 반복적으로 적용합니다.
- n이 짝수이면, n을 n/2로 변환합니다.
- n이 홀수이면, n을 3*n + 1로 변환합니다.
콜라츠 추측에 따르면 어떤 자연수든 이 과정을 거치면 결국 1에 도달하게 됩니다. 프로그램은 주어진 숫자가 실제로 1에 도달하는지 검사하고 그 결과를 출력합니다.
구현 아이디어
재귀 함수를 사용해 숫자가 1에 도달하는지 확인합니다. 이때 무한 루프나 사이클 발생 여부를 감지하기 위해 unordered_set(해시 셋)에 이미 등장했던 숫자를 기록합니다. 동일한 숫자가 다시 나타나면 사이클에 빠진 것으로 판단하여 false를 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
// n이 1에 도달하는지 확인하는 재귀 함수
bool check1(int n, unordered_set<int> &s){
if (n == 1)
return true;
if (s.find(n) != s.end())
return false;
return (n % 2) ? check1(3*n + 1, s) :
check1(n/2, s);
}
bool if_one(int n){
unordered_set<int> s;
return check1(n, s);
}
int main(){
int n = 234;
if_one(n) ? cout << "Yes" : cout << "No";
return 0;
}
출력 결과
Yes
코드 설명
- check1(): 재귀적으로 호출되며, n이 1이면 true를 반환합니다. 이미 방문한 숫자가 해시 셋에 존재하면 사이클이 발생한 것이므로 false를 반환합니다. n이 홀수면 3n+1을, 짝수면 n/2를 인자로 재귀 호출을 진행합니다.
- if_one(): 빈 해시 셋을 생성해 check1()을 호출하는 래퍼(wrapper) 함수입니다.
- main(): 예시 값 234를 검사합니다. 234는 짝수이므로 117 → 352 → 176 → ... 과정을 거쳐 최종적으로 1에 도달하며 "Yes"가 출력됩니다.
마무리
이처럼 재귀와 해시 셋을 조합하면 콜라츠 추측의 수렴 여부를 간단하게 검증할 수 있습니다. 다만 매우 큰 수를 입력할 경우 재귀 깊이가 깊어질 수 있으므로, 필요하다면 반복문 기반 구현이나 메모이제이션(memoization)으로 성능을 개선할 수 있습니다.