약수의 합

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

제한 사항
n은 0 이상 3000이하인 정수입니다.

입출력 예
n return
12 28
5 6

입출력 예 설명

입출력 예 #1
12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.

입출력 예 #2
5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.

풀이 과정

아니 이렇게 쓰고 채점했는데

function solution(n) {
    var answer = 0;    
    for(var i=0;i<3001;i++) {
        if(n%i === 0) {answer += i;}
    }    
    return answer;
}

갑자기 틀렸다고 뜸.

어이가 찢어지는 상황. 머임? 다른 사람들 풀이를 봤다.

function solution(num) {
    let answer = 0;
    for (let i = 1; i <= num; i++) {
        if (num % i === 0) answer += i ;
    }
    return answer;
}

아니... 뭐가 다른 거임. i가 0부터 시작해서 틀린 건가 해서 다시 해보니까 그게 아님. 알고 보니 문제에 속아 n을 자연스럽게 3000이하의 정수로 가정하고 풀어서 틀린 거였음. 그래서

function solution(n) {
    var answer = 0;    
    for(var i=0;i<=n;i++) {
        if(n%i === 0) {answer += i;}
    }    
    return answer;
}

걍 이렇게 했더니 됐다.
그런데 한 칸 하단에 유저들의 반응이 뜨거운 풀이가 있어서 확인했다.

function solution(n, a=0, b=0) {
    return n<=a/2?b:solution(n,a+1,b+=n%a?0:a);
}

풀이의 우수성을 떠나 그냥 솔직히 딱 보고 한 번에 이해 못 했다. (남들은 가독성 얘기했지만 난 걍 잘 몰라서)

어진씨...

function solution(n, a=0, b=0) {
    return n <= a/2? b : solution (n, a+1, b+=n%a? 0 : a)
}

어진씨 꺼 말고 약간 띄어쓰기 한 버전 보니까 읽을 수는 있게 됨. 그런데 이게 재귀함수라는 걸 알긴 알았는데 자세히 몰라서 검색했다.

https://triplexlab.tistory.com/163

재귀적으로 문제를 풀기 위해서는, 문제를 같은 형태의 더 작은 문제로 쪼개야 하기 때문에 패턴을 찾아야 합니다.
재귀함수를 쓸 때는 항상 두 경우가 있어야 합니다.

base case: 더 이상 문제를 쪼갤 필요가 없는 종료된 경우
recursive case: 문제를 쪼개서 풀어가는 경우

다시 문제를 풀어보자.
위 풀이를 한 번 더 해체해서 가독을 높였다.

function solution(n, a=0, b=0) {    
    if(n <= a/2) {
        return b;
    } else {
        return solution (n, a+1, b += n%a ? 0 : a);
    }
}

(한 번 더 해체해보려고 했으나 일단 잘 안 되길래 관두었다.) 일단 배운 걸 바탕으로 위의 풀이를 분석하면

이렇게 됨을 확인할 수 있다. 그럼 하나하나 recursive base에서부터 확장해가며 함수 solution 전체를 해석하면 아래와 같게 된다.

b += n%a ? 0 : a
"solution 함수에 들어온 인자 a로 인자 n을 나눠서 똑 떨어지면 a를, 아니면 0을 b에 더하라."

return solution (n, a+1, b += n%a ? 0 : a);
"solution 함수에 각 n, a+1, b 혹은 b+a를 인자로 넣어 실행해라."

if (n <= a/2) {return b;} else {return solution (n, a+1, b += n%a ? 0 : a);}
"solution 함수에 들어온 인자 a를 2로 나눈 값이 인자 n 이상이면 인자 b 반환, 이상이 아니면 solution 함수에 각 n, a+1, b 혹은 b+a를 인자로 넣어 실행해라."

---> 그러니까 내 처음 풀이법으로 치환하면 b가 변수 answer고 a가 i++의 역할을 하는 것으로 이해됐다.

참고로, n <= a/2에서 왜 a/2를 base case로 걸어놨는가 생각해보았는데 결국
n <= a/2은 다른 거 없고 그저 n 자기 자신을 맨 마지막에 b에 더하기 위한 장치.

if(n <= a) { //base case
return b + n; 이라고 써도 결과가 같다.