파이썬 코딩테스트 강좌, ‘좋은 수’ 구하기

문제 설명

주어진 숫자 n이 ‘좋은 수’라면, 그 수를 구하는 문제입니다.
‘좋은 수’의 조건은 다음과 같습니다.

• ‘좋은 수’는 두 자리 이상의 자연수이다.
• 각 자리의 합이 홀수인 수를 ‘좋은 수’로 정의한다.
• 주어진 n 이하의 모든 ‘좋은 수’를 찾아내어 리스트로 반환하라.

예를 들어, n이 30일 경우 ‘좋은 수’는 11, 13, 15, 17, 19, 21, 23, 25, 27, 29이다.
이 문제를 해결하기 위한 알고리즘을 설계하고 코드를 구현해보겠습니다.

문제 해결 접근법

문제를 단계별로 접근해보겠습니다.
첫째로, n이 두 자리 이상의 자연수인 경우들만 고려해야 하므로, 10부터 n까지 반복문을 사용하여 각각의 숫자에 대해 자리의 합을 계산하겠습니다.

숫자의 각 자리의 합을 구하기 위해, 주어진 숫자를 문자열로 변환한 후 각 자리의 숫자를 정수로 변환하여 합계에 더하는 방법을 사용할 수 있습니다.
다음으로, 그 합이 홀수인지 판별한 후, 조건을 만족하는 숫자를 리스트에 추가하겠습니다.

코드 구현

이제 위에서 설명한 알고리즘을 파이썬으로 구현해보겠습니다.

def is_good_number(num):
    # 자리의 합을 계산하여 홀수인지 판단
    digit_sum = sum(int(digit) for digit in str(num))
    return digit_sum % 2 == 1

def find_good_numbers(n):
    good_numbers = []
    for i in range(10, n + 1):  # 두 자리 이상의 숫자
        if is_good_number(i):
            good_numbers.append(i)
    return good_numbers

# 테스트
n = 30
print(find_good_numbers(n))
            

위 코드는 is_good_number라는 함수를 사용하여 주어진 수의 각 자리의 합을 계산하고,
해당 합이 홀수인지를 검사합니다.

find_good_numbers 함수는 10부터 n까지의 모든 수를 반복하면서,
‘좋은 수’를 찾고 리스트에 추가하여 반환합니다.

실행 결과

주어진 n = 30에 대해 함수를 실행한 결과는 다음과 같습니다:

[11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
            

위와 같이 11, 13, 15, 17, 19, 21, 23, 25, 27, 29의 ‘좋은 수’가 반환되었습니다.
이 결과는 “각 자리의 합이 홀수인 두 자리 이상의 자연수”라는 조건을 만족합니다.

복잡도 분석

위 알고리즘의 시간 복잡도를 살펴보면,
주어진 n까지의 숫자를 모두 반복해야 하므로 시간 복잡도는 O(n)입니다.
각 숫자에 대해 최대 2자리 수에 대해 자리의 합을 계산해야 하므로 추가적인 상수 시간이 필요하므로
종합적으로 O(n)으로 확인할 수 있습니다.

공간 복잡도는 반환할 ‘좋은 수’를 저장하기 위한 리스트를 사용하므로 O(k)
(k는 ‘좋은 수’의 개수)로 볼 수 있습니다.
실제로는 n이 작을수록 저장될 ‘좋은 수’가 적어지므로 효율적인 공간 사용이 가능합니다.

결론

이번 문제를 통해 반례를 고려하고 자리의 합을 계산하는 과정을 통해
‘좋은 수’를 효과적으로 찾아내는 방법을 학습하였습니다.
문제 해결을 위한 단계별 접근과 파이썬 코드를 통한 구현,
그리고 복잡도 분석을 통해 효율성을 높이기 위한 다양한 방법을 모색할 수 있었습니다.

앞으로 더 많은 알고리즘 문제를 통해 다양한 사고 방식과 해결 방법을 연습해 보세요.
코딩 테스트에서는 문제를 이해하고 접근하는 과정이 매우 중요합니다.