📜문제 설명

문제 바로가기

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

📍제한 사항

• n은 0 이상 3000이하인 정수입니다.

📍입출력 예시

n	return
12	28
5	6

---

📄문제 해결

📝내가 푼 코드

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

수학적으로 생각해보면 약수의 합은 소인수분해를 통해 구하지만, 그 과정을 코드로 그대로 구현하기보다는 반복문을 통해 약수를 구하는 것이 가장 간편할 것 같다는 생각으로 위와 같이 코드를 작성했다.

📑다른 사람들의 풀이

def sumDivisor(num):
    # num / 2 의 수들만 검사하면 성능 약 2배 향상잼
    return num + sum([i for i in range(1, (num // 2) + 1) if num % i == 0])

이 코드는 반복문을 통해 약수의 합을 구한다. 라는 점에서 나의 코드와 비슷하지만, 시간복잡도와 메모리 면에서 아주 효율적인 코드이다!

n의 약수에는 필수적으로 1과 n이 포함된다. 그 두 숫자를 제외한 약수는 당연하게도 n보다 작게되고, n을 2로 나눈 약수는 n을 2로 나눈 값이다. 따라서, n의 약수 중에서 n보다 작은 수는 n//2이라는 뜻이다.

따라서 우리는 약수를 구할 때 굳이 n까지 반복할 필요 없이 n//2까지만 검사해도 된다는 것이다. 1부터 n//2까지 구한 뒤, 그 결과에 n을 더해주면 되기 때문에 불필요한 반복을 최소화할 수 있어 아주 좋은 코드라고 할 수 있다.

---

🤔느낀점

새삼스럽지만 역시 수학을 잘해야 이런 효율적인 알고리즘도 금방 금방 떠올릴 수 있겠다는 생각이 들었다..