[프로그래머스 풀이]: Lv.1 / 약수의 합

작성: Corn/sec, ChatGPT, 편집: Corn/sec

문제 링크 🔗  프로그래머스 - 약수의 합

1. 문제 소개

약수의 합을 구하는 문제입니다.

 

 

---

2. 문제 풀이

1️⃣ 기본적인 for문을 사용한 코드

가장 먼저, 일반적인 for문을 이용해 약수의 합을 구하는 코드를 살펴보겠습니다.

def solution(n):
    answer = 0
    for i in range(1, n+1):  # 1부터 n까지 반복
        if n % i == 0:  # i가 n의 약수라면
            answer += i  # 합산
    return answer

🔹 실행 예제

print(solution(12))  # 28 (1 + 2 + 3 + 4 + 6 + 12)
print(solution(5))   # 6 (1 + 5)

✅ 문제점

• 1부터 n까지 모든 숫자를 순회하므로 시간 복잡도 O(n) 입니다.
• 큰 수일 경우 불필요한 반복이 많아 비효율적입니다.

---

2️⃣ 제너레이터 표현식을 사용하여 간결화

위 코드를 제너레이터 표현식을 사용하면 한 줄로 간단하게 바꿀 수 있습니다.

def solution(n):
    return sum(i for i in range(1, n+1) if n % i == 0)

🔹 실행 예제

print(solution(12))  # 28
print(solution(5))   # 6

✅ 개선된 점

• 불필요한 변수(answer) 제거하여 가독성을 높임.
• sum()을 활용하여 제너레이터 표현식을 사용, 리스트를 만들지 않고 바로 값을 더하도록 최적화.

✅ 제너레이터 표현식의 장점

• 메모리 절약 → 리스트를 생성하지 않고 sum()에서 바로 계산
• 코드 가독성 향상 → 한 줄로 표현 가능
• 성능 향상 → 리스트 컴프리헨션보다 빠름 (큰 데이터에서 차이 발생)

# 제너레이터 표현식이 익숙하지 않으시다면? 아래의 링크에서 예제로 연습해 보세요! #

 

[Python] 제너레이터 표현식(generator expressions) 연습 예제

---

3️⃣ 성능을 최적화한 코드 (O(√n)로 개선)

위 방식은 O(n)의 시간 복잡도를 가집니다.
하지만 제곱근(√n)까지만 탐색하는 방식을 활용하면 O(√n)으로 최적화할 수 있습니다.

def optimized_solution(n):
    result = 0
    for i in range(1, int(n ** 0.5) + 1):  # 1부터 √n까지만 탐색
        if n % i == 0:  # i가 약수라면
            result += i
            if i != n // i:  # 중복 방지 (제곱수가 아닐 경우)
                result += n // i
    return result

🔹 실행 예제

print(optimized_solution(12))  # 28
print(optimized_solution(5))   # 6
print(optimized_solution(36))  # 91 (1+2+3+4+6+9+12+18+36)

✅ 개선된 코드의 원리

1. 제곱근(√n)까지만 반복하여 불필요한 연산을 줄임.
2. n % i == 0이면 (i, n // i) 두 개의 약수를 한 번에 처리하여 반복 횟수를 절반으로 줄임.
3. **제곱수(n=36일 때, 6×6)**의 경우 중복을 방지하기 위해 i != n // i 조건을 추가.

✅ 성능 비교

방식	시간 복잡도	실행 속도 (n=1,000,000 기준)
기본 for문	O(n)	느림
제너레이터 표현식	O(n)	중간
제곱근 최적화	O(√n)	가장 빠름 🚀

 

 

---

3. 결론

방식	코드 길이	성능	메모리 효율성	추천 대상
for문 사용	길다	느림 (O(n))	낮음	초보자, 직관적 이해
제너레이터 표현식	짧다	보통 (O(n))	높음	간결한 코드 작성
제곱근 최적화	중간	빠름 (O(√n))	높음	성능 최적화 필요 시

📌 실제 프로젝트에서 어떤 방식을 사용할까?

• 간단한 경우: 제너레이터 표현식 (sum(i for i in range(1, n+1) if n % i == 0))
• 성능이 중요한 경우: O(√n) 최적화 코드 (optimized_solution)

 

---

 

4. 마무리

이번 포스팅에서는 약수의 합을 구하는 방법을 기본적인 for문 → 제너레이터 표현식 → 성능 최적화(O(√n)) 순서로 차근차근 살펴보았습니다.

제너레이터 표현식을 활용하면 더 간결하고 효율적인 코드를 작성할 수 있으며,
시간 복잡도를 고려한 최적화(O(√n))를 적용하면 성능을 획기적으로 향상시킬 수 있습니다.

 

🎯 여러분도 다양한 방식으로 연습하면서 최적화된 코드를 작성해 보세요!