[Algorithm] 콜라츠 추측

mori·2024년 9월 5일

알고리즘 공부 시작! 콜라츠 추측 반으로 뽀개기 🐻‍❄️

콜라츠 추측, 콜라츠 수열

🟨 1. 콜라츠 추측이란?

💁‍♀️ 콜라츠 추측
1937년 Collatz란 사람에 의해 제기된 이 추측은,
주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측이다.
콜라츠 추측은 특정 수를 가지고 어떤 과정을 반복했을 때 항상 1에 도달한다는 이론적 주장!
콜라츠 수열은 그 과정을 실제로 나타내는 수열!

💁‍♀️ 콜라츠 추측 규칙
1-1. 입력된 수가 짝수라면 2로 나눈다. n=n/2
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더한다. n=3n+1
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복한다. n=1에 도달할 때까지 반복

🟨 2. 콜라츠 추측 in 코테

콜라츠 추측을 구현하는 과정에서 콜라츠 수열을 사용할 때 중요한 포인트는 재귀 함수와 반복문이다!

재귀 함수, 반복문
간단한 규칙에 따라 수를 변환하며 반복하기 때문에 구현 과정에서 재귀 함수, 반복문을 사용한다.
짝수, 홀수 조건
주어진 수가 짝수, 홀수에 따라 다른 계산법이 적용되기 때문에 조건문을 사용한다.

🧡 꼭 기억하기 🧡

n이 1이 되기까지 몇 번이 걸리는지
입력된 수가 2개일 때, 겹치는 숫자 알아내기 (객체로 순서와 숫자 뽑아내기)

🟨 3. 예시

📝 문제
콜라츠 추측에 따르면, 주어진 자연수 n에 대해 다음의 과정을 반복하면 언젠가 1에 도달하게 됩니다.

n이 짝수이면, n을 2로 나눕니다.
n이 홀수이면, n에 3을 곱하고 1을 더합니다.
이 과정을 반복하여 n이 1이 되면 종료합니다.

자연수 6이 주어졌을 때, 콜라츠 추측을 따라 1에 도달하기까지 몇 번의 연산이 필요한지를 계산하는 함수를 작성하세요.

✏️ 풀이

✅ while 반복문

function collatzSteps(n) {
    let steps = 0;
    while (n !== 1) {
        if (n % 2 === 0) {
            n /= 2;  // 짝수일 경우 2로 나눔
        } else {
            n = 3 * n + 1;  // 홀수일 경우 3을 곱하고 1을 더함
        }
        steps++;  // 연산 횟수 증가
    }
    return steps;
}

const n1 = 6;
console.log(collatzSteps(n1));  // 출력: 8

// 추가 설명
//n=6일 때: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (총 8번의 과정)

✅ 재귀 함수

재귀 함수 : 함수가 자기 자신을 호출

기본 사례 : n이 1면 연산 stop
재귀 사례 : n이 1이 아니라면, n이 짝수 또는 홀수일 경우로 나누어 재귀 호출 수행

function collatzSteps(n) {
    if (n === 1) {
        return 0;  // 기본 사례: 1에 도달했으므로 연산 횟수는 0
    }
    if (n % 2 === 0) {
        return 1 + collatzSteps(n / 2);  // 짝수인 경우, 2로 나누고 재귀 호출
      	//1 + 하는 이유 : 
      	//현재 단계에서 수행된 연산을 포함하고 이후 연산 횟수를 누적해 전체 연산 횟수를 계산
    } else {
        return 1 + collatzSteps(3 * n + 1);  // 홀수인 경우, 3을 곱하고 1을 더하고 재귀 호출
    }
}

// 예시 사용
console.log(collatzSteps(6));  // 출력: 8