파이썬으로 처음 N개 홀수의 합 구하기 — O(1) 수학 공식 풀이

문제 개요

숫자 n이 주어졌을 때, 처음 n개의 양의 홀수 정수의 합을 구하는 프로그램을 작성해야 합니다.

예를 들어 입력이 n = 10이라면 출력은 100이 됩니다. 처음 10개의 홀수는 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]이며, 이들의 합은 100입니다.

핵심 아이디어: 수학적 성질 활용

이 문제는 반복문 없이도 매우 간단하게 해결할 수 있습니다. 열쇠가 되는 것은 다음과 같은 수학적 성질입니다.

• 처음 n개의 홀수(1, 3, 5, ..., 2n−1)의 합은 항상 n의 제곱(n²)과 같습니다.
• 실제로 1 = 1², 1+3 = 4 = 2², 1+3+5 = 9 = 3²처럼 이 패턴은 어떤 n에서도 유지됩니다.
• 따라서 항목을 하나씩 더할 필요 없이 그냥 n × n을 반환하면 답이 됩니다.

이 접근 방식의 가장 큰 장점은 시간 복잡도가 O(1)이라는 점입니다. n이 아무리 커져도 곱셈 한 번으로 즉시 결과를 얻을 수 있습니다.

구현 예제

아래 구현을 통해 더 쉽게 이해해 보겠습니다.

def solve(n):
   return n*n

n = 10
print(solve(n))

입력

10

출력

100

대안: 반복문으로 풀기

만약 위의 수학적 공식을 떠올리지 못했다면, 반복문을 사용해 홀수를 차례대로 더하는 방법도 있습니다.

def solve(n):
   total = 0
   for i in range(n):
      total += 2*i + 1
   return total

n = 10
print(solve(n))

이 방식은 O(n)의 시간이 걸리지만 동일하게 100을 출력합니다. 다만 성능 면에서는 n²을 반환하는 공식 기반 풀이가 훨씬 효율적이므로, 실전에서는 수학적 성질을 활용한 첫 번째 방법을 권장합니다.