C++로 1부터 N까지의 로그 값 계산에 필요한 최소 로그 연산 횟수 구하기

로그에는 log(x × y) = log(x) + log(y)라는 중요한 성질이 있습니다. 이 성질을 활용하면 1부터 N까지의 모든 로그 값을 구하는 데 실제로 필요한 최소 로그 연산 횟수를 계산할 수 있습니다.

문제 이해하기

예를 들어 N이 6이라면 정답은 3입니다. 그 이유를 단계별로 살펴보겠습니다.

• log(1): 항상 0이므로 계산할 필요가 없어 무시합니다.
• log(2), log(3): 소수이므로 각각 직접 계산해야 합니다. (현재까지 2회)
• log(4): log(2) + log(2)로 표현할 수 있으므로, 이미 알고 있는 log(2)를 재사용해 추가 계산 없이 구합니다.
• log(5): 소수이므로 직접 계산해야 합니다. (현재까지 3회)
• log(6): log(3) + log(2)로 표현되므로 이미 알고 있는 값들만으로 해결됩니다.

접근 방법: 소수 찾기로 환원

이 문제는 결국 1부터 N 사이의 소수 개수를 세는 문제로 환원됩니다. 소수는 더 이상 인수분해할 수 없기 때문에 로그 값을 반드시 독립적으로 계산해야 하지만, 합성수는 소인수분해를 통해 이미 계산된 로그 값들의 합으로 표현할 수 있기 때문입니다.

따라서 에라토스테네스의 체(Sieve of Eratosthenes)를 사용해 1부터 N까지의 소수를 찾고, 그 개수를 세면 원하는 답을 얻을 수 있습니다.

C++ 구현 예제

#include<iostream>
#include<vector>
#define MAX 1000005
using namespace std;
vector<int> prime(MAX, 1);
void seive(int N) {
    prime[0] = prime[1] = 0;
    for (int i = 2; i <= N; i++) {
        if (prime[i] == 1) {
            for (int j = 2; i * j <= N; j++)
            prime[i * j] = 0;
        }
    }
}
int numberOfLogs(int N) {
    int log_count = 0;
    seive(N);
    for (int i = 1; i <= N; i++) {
        if (prime[i] == 1)
        log_count++;
    }
    return log_count;
}
int main() {
    int N = 8;
    cout<<"Minimum number of log counts required: " << numberOfLogs(N)<<endl;
}

실행 결과

Minimum number of log counts required: 4

결과 분석

N = 8일 때, 1부터 8 사이의 소수는 2, 3, 5, 7로 총 4개입니다. 따라서 직접 계산해야 하는 로그 값도 4개이며, 나머지 수인 log(1), log(4), log(6), log(8)은 이미 계산된 값들의 조합으로 추가 연산 없이 구할 수 있습니다.

시간 및 공간 복잡도

에라토스테네스의 체의 시간 복잡도는 O(N log log N), 공간 복잡도는 O(N)입니다. 덕분에 N이 매우 큰 경우에도 효율적으로 최소 로그 연산 횟수를 구할 수 있습니다.