-
약수의 합 (프로그래머스, 레벨1), 양의 약수의 합 공식개발자의 길/Algorithm 2021. 3. 17. 10:32
https://programmers.co.kr/learn/courses/30/lessons/12928
1. 가장 쉬운 풀이는 그냥 n 보다 작은 수를 하나씩 가져와서 조건에 맞으면 합을 구하기
def solution(n): return n + sum([i for i in range(1, n // 2 + 1) if n % i == 0])
2. 소인수 분해 후 양의 약수의 합을 구하는 공식 사용
양의 정수 n을 소인수 분해하여 n = p^i * q^j * r^k 일 때, 양의 약수의 합은
(1 + p + p^2 + ... + p^i)(1 + q + ... + q^j)(1 + r + ... + r^k)
구현 code: github.com/mathncode/solving-algo-daily/blob/main/2021-03-17-othersolve.py
효율은 1번 풀이가 더 좋다. 숫자가 엄청 커지면 2번이 나을 것 같긴 한데...
1번 풀이가 쉽게 떠올랐지만, 다른 방법으로 풀어보고 싶었고 양의 약수합 공식이 생각나서 구현해보았다.
※ 위 문제 오류
약수와 배수의 정의는,
두 정수 a, b에 대해 a=b*c 를 만족하는 정수 c가 존재하면, b는 a의 약수. a는 b의 배수.(여기서 b≠0 이면 나누기가 정의된다)
0 = 1 * 0, 0 = 2 * 0, 0 = 3 * 0 ... 이므로 모든 자연수는 0의 약수이고, 굳이 합을 구하면 무한이다.
그러나 위 문제에서는 n = 0일 때 0을 return 해야 답이다.
위 문제의 '질문하기'에 가보면 0에 대해 제외해달라고 게시물을 올려달라고 한 사람들이 몇 명 있는데 문제 관리를 안 하는 것 같다. 뿐만 아니라 얼마 전에 프로그래머스에 다른 문제 관련해서 '개인 문의하기'를 한 적이 있는데 '연습문제에 관한 질문은 받지 않습니다.'라고 답변이 왔다. 무료 연습문제라고 그런 건가 보다.
한때 수학 문제를 출제해본 사람으로서 이해할 수 없다. 모든 문제는 오류가 있을 수 있고, 치밀하게 검토해서 출제해야 하며 오류를 발견하면 빠르게 수정하는 게 기본이다.
'개발자의 길 > Algorithm' 카테고리의 다른 글
약수의 개수, 약수의 합 공식 (0) 2021.03.27 소수 만들기 (프로그래머스, 레벨1) (0) 2021.03.27 큰 수 만들기 (프로그래머스, 레벨2) (0) 2021.03.12 무엇이 추구해야 할 방향인가? (0) 2021.03.10 '하나씩 세는 것이 강력한 방법이다' (0) 2021.03.04