[TIL #10] 자릿수 더하기 / 약수의 합

1. 자릿수 더하기

A. 단순한 방법

그냥 모듈러로 때려 박는 방식이다.

가장 단순하고 이해가 빠르다.

 

int sumOfDigitsUsingModular(long long num) {
    int sum = 0;

    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }

    return sum;
}

모듈러로 나머지를 구하고 그걸 10으로 나누는 것을 반복하게 된다.

 

B. 문자 활용

ASCII를 활용해 계산하는 방법도 있다.

 

int sumOfDigitsUsingString(long long num) {
    int sum = 0;
    std::string s = std::to_string(num);

    for (char c : s) {
        if (c >= '0' && c <= '9') {
            sum += (c - '0');
        }
    }

    return sum;
}

0을 빼는 이유는 실제 값을 얻기 위함이다.

1은 49, 2는 50이다.

0은 48이므로 이를 빼줘야 실제 값을 얻을 수 있다.

 

하지만 이런 방법이 있다 정도로 알고 넘어가자.

이를 다음의 코드를 이용해 비교해 보자.

 

#include <iostream>
#include <chrono>
#include <cmath>
#include <string>

// 문자열 변환 방법
int sumOfDigitsUsingString(long long num) {
    int sum = 0;
    std::string s = std::to_string(num);

    for (char c : s) {
        if (c >= '0' && c <= '9') {
            sum += (c - '0');
        }
    }

    return sum;
}

// 모듈러 연산 방법
int sumOfDigitsUsingModular(long long num) {
    int sum = 0;

    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }

    return sum;
}

int main() {
    long long number = 1234567891234567891; // 예시로 큰 수 사용

    auto start = std::chrono::high_resolution_clock::now();
    int result1 = sumOfDigitsUsingString(number);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration1 = end - start;
    std::cout << "Sum of digits (String method): " << result1 << " in " << duration1.count() << " seconds\n";

    start = std::chrono::high_resolution_clock::now();
    int result2 = sumOfDigitsUsingModular(number);
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration2 = end - start;
    std::cout << "Sum of digits (Modular method): " << result2 << " in " << duration2.count() << " seconds\n";

    return 0;
}


/*
* Result
* Sum of digits (String method): 91 in 1.0194e-05 seconds
* Sum of digits (Modular method): 91 in 2.09e-07 seconds
*/

모듈러로 계산하는 것이 일반적으로 더 빠른 속도를 보여주기 때문이다.

문자열로 연산하게 되면 길이만큼 문자열을 저장하기 위한 공간도 필요하게 된다.

하지만 문자를 통해 이런 것이 가능하다는 것은 알아두는 것이 좋을 것이다.

 

 

2. 약수의 합

A. 무식한 방법

또 모듈러로 때려박는 방식이다.

 

int getDiv(int n) {
    int answer = 0;
    
    if (n <= 0)
        return 0;
    
    for (int i = 1; i <= n; i++) {
        if (a % i == 0)
            answer += i;
    }
    
    return answer;
}

큰 수를 넣으면 시간이 오래 걸리리라는 것은 쉽게 예상할 수 있다.

 

 

B. 약수의 성질 활용

먼저 약수의 성질에 대해 알아보자.

 

약수는 대칭성을 보인다.

36을 생각해 보자.

 

• 1 × 36 = 36
• 2 × 18 = 36
• 3 × 12 = 36
• 4 × 9 = 36
• 6 × 6 = 36

작은 약수와 큰 약수가 곱해져서 N이 되는 형태를 보인다.

여기서 약수 쌍이 다음과 같은 대칭성을 보이는 것을 알 수 있다.

 

• 1과 36
• 2와 18
• 3과 12
• 4와 9
• 6은 자신과 대칭성을 가짐

이 대칭성은 약수를 찾을 때 유용하다. 예를 들어, $n$의 약수를 찾을 때 $\sqrt{n}$까지만 확인하면 된다.

$\sqrt{n}$ 이후의 약수는 이미 앞에서 확인한 약수의 쌍이기 때문이다.

36의 약수를 찾을 때 $\sqrt{36}=6$이므로 1부터 6까지의 수만 확인하면 된다.

 

N이 1,000,000이라고 해도 백만 번 반복하는 대신 1,000번으로 끝나게 되기 때문에

효율적인 연산이 가능하다.

 

이걸 코드로 표현하면 다음과 같다.

int solution(int n) {
    int answer = 0;

    for (int i = 1; i <= std::sqrt(n); ++i) {
        if (n % i == 0) {
            answer += i;
            if (i != n / i) {
                answer += (n / i);
            }
        }
    }
          
    return answer;
}

그럼 이 방법과 무식한 방법을 비교해 보자.

 

#include <iostream>
#include <chrono>
#include <cmath>

// 제곱근을 사용한 약수 합 계산 방법
long long sqrtWay(long long n) {
    long long answer = 0;

    for (int i = 1; i <= std::sqrt(n); ++i) {
        if (n % i == 0) {
            answer += i;
            if (i != n / i) {
                answer += (n / i);
            }
        }
    }

    return answer;
}

// 단순 모듈러 반복을 사용한 약수 합 계산 방법
long long modWay(long long n) {
    long long sum = 0;

    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            sum += i;
        }
    }

    return sum;
}

int main() {
    long long number = 123456789;

    // 제곱근을 사용한 방법 테스트
    auto start = std::chrono::high_resolution_clock::now();
    long long result1 = sqrtWay(number);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration1 = end - start;
    std::cout << "Sum of divisors (sqrt method): " << result1 << " in " << duration1.count() << " seconds\n";

    // 단순 모듈러 반복 방법 테스트
    start = std::chrono::high_resolution_clock::now();
    long long result2 = modWay(number);
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration2 = end - start;
    std::cout << "Sum of divisors (simple method): " << result2 << " in " << duration2.count() << " seconds\n";

    return 0;
}


/*
* Result
* Sum of divisors (sqrt method): 178422816 in 0.000191696 seconds
* Sum of divisors (simple method): 178422816 in 1.05876 seconds
*/

엄청난 차이가 나는 것이 보이는가?

단위가 백만이 아니라 천만, 억, 조로 가면 어떨까?

시간을 낭비하지 말도록 하자.