3/31(일) 오늘의 코테 1 - 콜라츠 추측

코딩테스트 연습 - 콜라츠 추측 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

0. 반복문을 사용하는 방식

 

def solution(num):
    count = 0
    
    while num != 1:
        if num % 2 == 0:
            num = num // 2
        else:
            num = num * 3 + 1
        count += 1
    
    if count >= 500: return -1
    return count

# 반복 개수를 저장할 변수 count
# 입력된 수가 1이 될 때까지 반복 -> while num != 1
# 입력된 수가 짝수라면 2로 나눔 -> if num % 2 == 0: num // 2
# 입력된 수가 홀수라면 3 곱하고 1 더함 -> else: num * 3 + 1
# 반복 개수 count를 return -> 만약 500개 이상이면 -1 return
출처: https://gomburger.tistory.com/26 [가끔 생각을 해요 ʕتʔ:티스토리]

 

- 가독성: 반복문은 이 문제를 해결하기 위한 절차를 명확하게 설명합니다. 로컬 변수 count의 사용은 상태 관리를 단순화하고 함수의 독립성을 높입니다.
- 효율성: 반복문은 호출 스택에 대한 부담 없이 동일한 작업을 수행합니다. 큰 입력 값에 대해서도 안정적으로 작동할 가능성이 높습니다.
- 오류 처리: 코드 마지막에 명시된 if count >= 500: return -1은 500번의 반복 후에도 문제가 해결되지 않을 경우를 명확히 처리합니다. 이는 재귀 코드에 비해 더 직관적인 오류 처리 방식을 제공합니다.

 

- 전역 변수에 의존하지 않고 로컬 변수를 사용하여 함수의 독립성과 재사용성을 증가시킵니다.
- 반복문은 재귀 호출에 비해 스택 오버플로우의 위험이 없으며, 큰 입력 값에 대해 더 효율적으로 작동할 수 있습니다.
- 500번 반복 후의 오류 처리가 명확하게 구현되어 있어, 가독성과 오류 처리 능력이 뛰어납니다.

 

따라서, 이 코드가 밑의 코드들보다 더 잘 짠 코드라고 할 수 있습니다.

 

1. 전역 변수를 사용하는 방식

 

 전역변수를 사용할 때는 함수 내부에서 전역 변수의 값을 변경하려면 global키워드를 사용해 변수가 전역 범위에서 정의 된 것임을 명시해야 합니다.

 단, 이 접근 방법은 코드의 가독성과 유지보수성을 저하시킬 수 있으므로, 일반적으로는 권장되지 않습니다.

cnt = 0  # 전역 변수로 cnt 선언

def solution(num):
    global cnt
    
    if num == 1:
        result = cnt  # 현재 cnt 값을 저장
        cnt = 0  # 다음 호출을 위해 cnt 초기화
        return result  # 저장된 cnt 값 반환
        
    elif cnt >= 500:  # 500번 반복했는데도 1이 되지 않는 경우
        cnt = 0  # 다음 호출을 위해 cnt 초기화
        return -1  # -1 반환
        
    else:
        cnt += 1  # 연산 횟수 증가
        if num % 2 == 0:
            return solution(num // 2)
        else:
            return solution(num * 3 + 1)

 

 

전역 변수 cnt의 값을 함수 호출마다 초기화해야 하는 경우는 함수를 재사용할 때 발생합니다. 즉, 같은 전역 cnt를 사용하여 여러 번 solution 함수를 호출하고자 할 때, 각 호출 전에 cnt를 0으로 초기화해야 이전 호출의 결과가 다음 호출에 영향을 미치지 않습니다. 하지만 이 초기화는 함수 외부에서, 함수를 호출하기 전에 수행되어야 합니다.

 

- 이 코드는 다음과 같이 작동합니다:

* 함수가 호출되면, num이 1인지 확인합니다. 1이라면 현재까지의 연산 횟수를 저장한 result를 반환하고, cnt를 초기화합니다.
* cnt가 500 이상인 경우, 즉 500번의 연산을 수행했음에도 num이 1이 되지 않았다면, -1을 반환하고 cnt를 초기화합니다.
* 위의 두 경우가 아니라면, num이 짝수인지 홀수인지에 따라 해당하는 연산을 수행하고 cnt를 1 증가시킵니다.
* 만약 500번의 연산 내에 num이 1이 되어 함수가 성공적으로 종료된다면, 그 때의 연산 횟수가 반환됩니다.
* 500번의 연산 후에도 num이 1이 되지 않는다면, -1이 반환됩니다.

 

 

 

2. 재귀 함수 호출의 결과를 직접 반환하도록 하는 방식

 

def solution(num):
    if num == 1:
        return 0
    
    if num % 2 == 0:
        return 1 + solution(num // 2)
    else:
        return 1 + solution((num * 3) + 1)

 

cnt 변수를 직접 사용하지 않고, 재귀 함수 호출의 결과를 직접 반환하도록 코드를 단순화했습니다. 재귀 함수의 호출 과정에서 각 단계마다 1을 더함으로써, 필요한 연산의 횟수를 직접 누적하는 방식으로 변경한 것이죠. 이렇게 하면 각 재귀 호출에서 반환되는 값이 바로 그 단계까지의 연산 횟수를 나타내게 되므로, 별도의 카운터 변수(cnt)를 관리할 필요가 없어집니다.

즉, 재귀 함수의 각 호출이 해당 단계에서의 연산 횟수 1을 반환 값에 포함시키고, 이전 단계의 반환 값을 현재 반환 값에 더함으로써, 전체 연산 횟수를 계산합니다. 따라서, 함수는 각 단계에서 1 + solution(새로운 num)의 형태로 작동하며, 이는 "현재 단계에서의 연산 1회 + 나머지 연산에서 발생하는 연산 횟수"를 의미합니다.

간단히 요약하자면, 코드는 이제 각 단계에서의 연산 횟수를 바로 반환하고, 이를 모든 재귀 호출에서 누적하는 방식으로 작동합니다. 따라서, cnt 변수는 더 이상 필요하지 않게 되었습니다.

 

 

예를 들어, solution(6)이 호출되었다고 가정해 보겠습니다. 이 함수는 다음과 같은 과정을 거칩니다:

- 첫 번째 호출: solution(6)

num은 6이며, 짝수입니다.
재귀 호출: 1 + solution(6 // 2) → 1 + solution(3)
이 시점에서 함수는 결과를 기다리며 일시 중단됩니다.

 

 

- 두 번째 호출: solution(3)

num은 3이며, 홀수입니다.
재귀 호출: 1 + solution((3 * 3) + 1) → 1 + solution(10)
이 시점에서 다시 함수는 결과를 기다리며 일시 중단됩니다.

 

 

- 세 번째 호출: solution(10)

num은 10이며, 짝수입니다.
재귀 호출: 1 + solution(10 // 2) → 1 + solution(5)
함수가 다시 중단됩니다.

 

 

- 네 번째 호출: solution(5)

num은 5이며, 홀수입니다.
재귀 호출: 1 + solution((5 * 3) + 1) → 1 + solution(16)
함수가 다시 중단됩니다.

 

 

- 다섯 번째 호출부터 최종적으로 num이 1이 될 때까지 계속됩니다.

 

각 단계에서 solution 함수는 num이 1이 될 때까지 연산을 수행하고, 각 단계에서 1을 더해 나갑니다.
각 재귀 호출마다, 함수는 연산을 한 번 수행하고(1을 더함), 그 결과를 다음 호출로 넘기며, 마지막으로 num이 1이 되었을 때 0을 반환합니다. 이후 모든 재귀 호출이 반환되며, 각 단계에서 더해진 1들이 최종 연산 횟수를 형성합니다.

예시의 핵심 포인트는:

각 단계의 재귀 호출은 '현재 단계에서 필요한 연산 1회 + 나머지 단계에서 필요한 연산 횟수'를 계산합니다.
모든 호출이 종료되고 반환되는 과정에서, 각 단계의 연산 횟수가 누적되어 최종 결과가 형성됩니다.
이 방식으로 solution 함수는 콜라츠 추측에 따라 주어진 수를 1로 만드는 데 필요한 최소 연산 횟수를 계산합니다.