C# 코딩테스트 강좌, 제곱이 아닌 수 찾기

제곱이 아닌 수 찾기

이 강좌에서는 제곱이 아닌 수를 찾는 알고리즘 문제를 다루어 보겠습니다. 문제를 해결하기 위한 다양한 접근법을 익히고, 이를 통해 코딩테스트에서의 문제 해결 능력을 향상시키는 것을 목표로 합니다.

문제 설명

주어진 정수 N에 대하여, 1부터 N까지의 수 중에서 제곱 수가 아닌 수의 개수를 구하는 문제입니다. 예를 들어, N이 10 이라면 1, 4, 9가 제곱 수이므로 제곱 수가 아닌 수는 1, 2, 3, 5, 6, 7, 8, 10으로 총 8개입니다.

문제 입력

정수 N (1 ≤ N ≤ 10^6)

문제 출력

제곱 수가 아닌 숫자의 개수를 출력

예제

    입력 예시:
    10

    출력 예시:
    8

문제 접근법

이 문제를 해결하기 위한 여러 가지 방법이 있을 수 있습니다. 하지만 최적의 방법을 찾기 위해서는 제곱 수를 생성하고 이를 기반으로 제곱 수가 아닌 수의 개수를 유추해야 합니다. 제곱 수는 다음과 같이 정의됩니다:

X는 정수이며, Y = X * X 형태

이렇게 볼 때 1부터 N까지의 제곱 수를 찾기 위해서는 다음과 같은 로직이 필요합니다.

1. 제곱수 리스트 생성

1부터 N까지의 수에 대한 제곱수를 구하는 것은 O(√N) 복잡도를 가지므로, 제곱수를 미리 계산하여 리스트에 저장합니다.

2. 정수 N에 대한 제곱수와 비교

그 다음, 1부터 N까지의 수 중에서 제곱수 리스트에 포함된 수의 개수를 셉니다.

3. 최종 결과 도출

N에서 제곱수의 개수를 빼면 제곱이 아닌 수의 개수를 얻을 수 있습니다. 이 프로세스는 O(N)이라는 시간 복잡도를 가집니다.

코드 구현

이제 위의 논리를 바탕으로 C#으로 코드를 작성해 보겠습니다.


using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        HashSet squareNumbers = new HashSet();

        // 제곱수를 HashSet에 추가
        for (int i = 1; i * i <= N; i++)
        {
            squareNumbers.Add(i * i);
        }

        int nonSquareCount = N - squareNumbers.Count; // 제곱수가 아닌 수의 개수

        Console.WriteLine(nonSquareCount);
    }
}

코드 설명

HashSet squareNumbers: 제곱 수를 저장할 HashSet입니다. 빠른 검색을 위해 HashSet을 사용합니다.
for (int i = 1; i * i <= N; i++): 1부터 시작하여 제곱 수를 생성합니다.
squareNumbers.Add(i * i): 생성된 제곱 수를 HashSet에 추가합니다.
nonSquareCount = N - squareNumbers.Count: N에서 제곱 수의 개수를 빼서 제곱이 아닌 수의 개수를 구합니다.
Console.WriteLine(nonSquareCount): 최종 결과를 출력합니다.

복잡도 분석

이 알고리즘의 시간 복잡도를 분석해보면:

제곱수를 생성하는 부분: O(√N) (최대 √N개의 제곱수 생성)
제곱수가 아닌 수의 개수를 구하는 부분: O(1) (HashSet의 크기를 가져오기 때문에 상수 시간 소요)

따라서, 전체 시간 복잡도는 O(√N)입니다. 이 알고리즘은 주어진 제약 조건 내에서 매우 효율적으로 작동합니다.

결론

이번 강좌에서는 제곱이 아닌 수를 찾는 알고리즘 문제를 해결하는 방법을 알아보았습니다. 문제를 해결하기 위한 사고 과정을 통해 문제 해결 능력을 향상시키길 바랍니다. 앞으로도 다양한 알고리즘 문제를 통해 지속적인 연습이 필요합니다.