이 튜토리얼에서는 n + nn + nnn + ... + n(m번 반복) 형태의 수열 합을 구하는 코드를 작성해 보겠습니다. Python에서는 아주 간단하게 구현할 수 있습니다. 먼저 예시를 살펴보겠습니다.
입력:
n = 1
m = 5
수열:
1 + 11 + 111 + 1111 + 11111
출력:
12345
알고리즘
다음 단계를 따라 문제를 해결할 수 있습니다.
1. n과 m을 초기화한다.
2. total(합계) 변수를 0으로 초기화한다.
3. 다음 수열 항을 생성하기 위해 n의 복사본(copy_n)을 만든다.
4. m번 반복문을 실행한다.
4.1. 현재 n 값을 total에 더한다.
4.2. n을 n * 10 + copy_n으로 갱신하여 다음 항을 만든다.
5. total을 출력한다.
핵심 아이디어
이 수열의 규칙은 매우 간단합니다. 이전 항에 10을 곱한 뒤 처음 값 n을 더하면 다음 항이 됩니다. 예를 들어 n이 1일 때, 1 → 1×10+1=11 → 11×10+1=111처럼 수열이 이어집니다. 따라서 문자열 변환이나 제곱 연산 없이 정수 연산만으로 효율적으로 합을 구할 수 있습니다.
예제 코드
아래 코드를 확인해 보세요.
# n과 m 초기화
n = 1
m = 5
# 합계를 0으로 초기화
total = 0
# 다음 수열 항 생성을 위해 n의 복사본 저장
copy_n = n
# m번 반복
for i in range(m):
# 현재 n 값을 합계에 더함
total += n
# n을 갱신하여 다음 수열 항 생성
n = n * 10 + copy_n
# 결과 출력
print(total)
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
12345
시간 복잡도
이 알고리즘은 반복문을 m번 실행하므로 시간 복잡도는 O(m)입니다. 추가로 사용하는 메모리는 상수 개수의 변수뿐이므로 공간 복잡도는 O(1)로 매우 효율적입니다.
마무리
지금까지 Python으로 n + nn + nnn + ... 형태의 수열 합을 구하는 방법을 알아보았습니다. 반복문과 간단한 점화식만으로 손쉽게 구현할 수 있으니, 다양한 n과 m 값으로 직접 테스트해 보시기 바랍니다. 글에 대해 궁금한 점이 있다면 댓글로 남겨주세요.