[Lv1] 소수 찾기 - 복잡도

해당 문제와 풀이를 보시기 전에 시간 복잡도에 대해 더 자세히 알고 싶으신 분은 아래 글을 참고하시면 됩니다.

시간 복잡도 & 공간 복잡도 | Big-O 표기법 설명

시간복잡도는 “입력 크기 n이 커질 때 실행 시간이 얼마나 늘어나는가”, 공간복잡도는 “추가 메모리를 얼마나 쓰는가”를 점근적으로 평가한다. 상수/하드웨어/캐시의 영향은 실무에서 크지만, 알고리즘 비교의 1차 기준은 여전히 Big-O다.

Gibeom KimGibeom Kim

문제

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

풀이1: 브루트 포스 약수 검사 - O(n^2)

#include <iostream>

bool isPrimeNum(int n)
{
    if (n < 2)
    {
        return false;
    }
    else if (n == 2)
    {
        return true;
    }
    else if (n % 2 == 0)
    {
        return false;
    }

    for (auto d = 3; d < n; d += 2)
    {
        if (n % d == 0)
        {
            return false;
        }
    }

    return true;
}

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

    for (int i = 2; i <= n; ++i)
    {
        if (isPrimeNum(i))
        {
            std::cout << i << std::endl;
            ++answer;
        }
    }

    return answer;
}

가장 쉽고 직관적으로 구현할 수 있는 코드인데, 위는 당연히 문제 취지 상 시간 초과로 테스트 실패한다.

그렇다면, 여기서 시간 복잡도를 줄여 보아야 하는데 두 가지 방법이 있다.

풀이 2: √n까지만 검사 - O(n^1.5)

위 코드에서 조금 더 최적화 할 수 있는 방법은, 약수 검사를 √n까지만 시도하는 것이다. 한 정수 x가 합성수라면 x=ab인 약수 쌍 (a, b)가 존재하는데, 이 때 두 수 중 하나는 반드시 √x 이하가 된다. 따라서 소수 판정 시 2와 홀수 약수만, (d * d <= n) 범위 까지만 검사하면 충분하다.

#include <iostream>
#include <string>

bool isPrimeNum(int n)
{
    if (n < 2)
    {
        return false;
    }

    if (n == 2)
    {
        return true;
    }

    if (n % 2 == 0)
    {
        return false;
    }

    for (int d = 3; d * d <= n; d += 2)
    {
        if (n % d == 0)
        {
            return false;
        }
    }

    return true;
}

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

    for (int i = 2; i <= n; ++i)
    {
        if (isPrimeNum(i))
        {
            ++answer;
        }
    }

    return answer;
}

심화: 에라토스테네스의 체 풀이

다른 사람의 풀이를 보던 중, 재미있는 풀이법을 확인했는데 알고보니 이 방식이 가장 정석의 풀이법이었다. 이 방법이 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른방법이라고 한다. 결론부터 말하자면, 해당 방식의 시간 복잡도는 다음과 같다.

알고리즘 아이디어

1. 불리언 테이블 준비
   크기 n+1짜리 배열을 만들고, 처음엔 전부 “소수(true)”라고 가정한다.
   단, 0과 1은 소수가 아니므로 false로 처리한다.
2. 가장 작은 소수부터 배수 제거
   • 2부터 시작해서, 현재 수가 소수라면
   • 그 수의 배수들을 모두 지운다(false).
   • 배수 제거는 p^2부터 시작하면 된다. (그 이전 배수는 이미 더 작은 소수에서 지워졌기 때문)
3. √n까지만 반복
   • 소수 후보 p는 √n ​까지만 검사한다.
   • 그 이후의 합성수는 이미 작은 소수들에 의해 모두 제거된다.
4. 남은 수는 전부 소수
   테이블에 true로 남은 수들의 개수가 곧 소수의 개수다.

구현 예시

#include <vector>

int solution(int n)
{
    if (n < 2)
    {
        return 0;
    }

    std::vector<bool> is_prime(n + 1, true);

    is_prime[0] = false;
    is_prime[1] = false;

    for (auto p = 2; p * p <= n; ++p)
    {
        if (is_prime[p])
        {
            for (int i = p * p; i <= n; i += p)
            {
                is_prime[i] = false;
            }
        }
    }

    int answer = 0;

    for (const auto p : is_prime)
    {
        if (p)
        {
            ++answer;
        }
    }

    return answer;
}

체점 결과 비교