[내일배움캠프] 데일리 루틴(iOS_3회차) - 콜라츠 추측

이미지를 클릭하면 코딩테스트 페이지로 이동합니다

 

내 풀이

func solution(_ num:Int) -> Int {
    if num == 1 { return 0}
    
    var x = num
    var count = 0
    while x != 1{
        if x % 2 == 0{
            x = x / 2
        }else{
            x = x * 3 + 1
        }
        count += 1
        
        if count >= 500{
            return -1
        }
    }
    return count
}

 

Collatz 추측을 따르는 작업을 수행하여 입력된 수가 1이 될 때까지 몇 번의 작업을 반복해야 하는지 반환하도록 코드를 작성했다.

1. 만약 주어진 수 num이 1이라면, 바로 0을 반환하여 작업을 종료
2. 그렇지 않은 경우, 변수 x에 주어진 수 num을 저장하고, 반복 횟수를 세는 변수 count를 0으로 초기화
3. while 반복문을 사용하여 x가 1이 될 때까지 다음 작업을 반복
   • x가 짝수인 경우, x를 2로 나누기
   • x가 홀수인 경우, x를 3을 곱하고 1을 더하기
   • 각 작업이 수행될 때마다 count를 1 증가
4. 만약 count가 500 이상인 경우, 무한 루프를 방지하기 위해 -1을 반환하고 작업을 종료
5. 작업이 종료되면 count를 반환하여 몇 번의 작업을 수행했는지를 나타냄

따라서 예를 들어 주어진 수가 6인 경우, 작업을 8번 수행하여 1이 됨, 그러므로 이 함수는 8을 반환

 

 

 

Collatz 추측이란?

- 1937년에 독일 수학자 로이트바르트 콜라츠(Lötzsch Collatz)가 제안한 수학적 추측.

- Collatz 추측은 컴퓨터 과학에서도 중요한 역할

    왜냐하면 이 추측을 검증하는 데 사용되는 알고리즘이 다양한 컴퓨터 과학 문제에서 유용하기 때문

- 이 추측은 다음과 같은 규칙에 따라 수를 반복적으로 변환하면 결국 모든 양의 정수는 1이 될 것이라는 주장

- 아래와 같은 작업을 반복하면 어떤 양의 정수든 결국 1로 수렴한다는 것이 Collatz 추측

 

규칙

1. 주어진 양의 정수 n이 짝수인 경우, n을 2로 나누기
2. 주어진 양의 정수 n이 홀수인 경우, n에 3을 곱하고 1을 더하기
3. 위 두 과정을 1이 될 때까지 반복