C++로 N 미만의 완전제곱수와 비제곱수 개수 구하기

하나의 정수 N이 주어졌을 때, 목표는 1부터 N 사이(또는 N 미만)의 수 중 완전제곱수(perfect square)의 개수와 비제곱수(non-square)의 개수를 각각 구하는 것입니다.

예를 들어 N=20이라면, 완전제곱수는 1, 4, 9, 16으로 총 4개이고, 나머지 16개는 모두 비제곱수입니다.

단순 접근 방식(Naive Approach)

가장 직관적인 방법은 1부터 N까지의 모든 수를 하나씩 탐색하면서 해당 수가 완전제곱수인지 확인하는 것입니다.

어떤 수 i가 완전제곱수인지 판별하는 기준은 다음과 같습니다.

floor(sqrt(i)) == ceil(sqrt(i))

즉, i의 제곱근에 대해 내림(floor)과 올림(ceil)한 값이 같다면 그 수는 완전제곱수입니다. 예를 들어 sqrt(16)=4.0이므로 floor와 ceil이 모두 4로 같지만, sqrt(17)≈4.12이므로 floor는 4, ceil은 5가 되어 서로 다릅니다.

효율적인 접근 방식(Efficient Approach)

N 미만의 완전제곱수는 별도의 반복문 없이 아래 공식 한 줄로 바로 구할 수 있습니다.

floor(sqrt(N))

N 이하의 완전제곱수는 1², 2², 3², … 형태로 존재하므로, √N의 정수 부분이 곧 완전제곱수의 개수가 됩니다. 따라서 비제곱수의 개수는 전체 개수에서 이 값을 빼면 됩니다.

입력 및 출력 예시

입력

N = 20

출력

완전제곱수 개수: 4
비제곱수 개수: 16

설명

20 미만의 완전제곱수는 1, 4, 9, 16이며, 나머지 수는 모두 비제곱수입니다.

입력

N = 40

출력

완전제곱수 개수: 6
비제곱수 개수: 34

설명

40 미만의 완전제곱수는 1, 4, 9, 16, 25, 36이며, 나머지 수는 모두 비제곱수입니다.

방법 1: 단순 접근 방식 구현

프로그램의 동작 원리

정수 N을 입력받습니다.
함수 squareNums(int n)은 n 이하의 수 중 완전제곱수의 개수를 반환합니다.
카운트 변수 count를 0으로 초기화합니다.
for 반복문으로 i=1부터 i<=n까지 순회합니다.
floor(sqrt(i)) == ceil(sqrt(i))라면 i는 완전제곱수이므로 count를 증가시킵니다.
모든 반복이 끝나면 count에는 완전제곱수의 총 개수가 저장됩니다.
N - count 값이 곧 비제곱수의 개수입니다.

코드 예제

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int squareNums(int n){
    int count = 0;
    for (int i = 1; i <= n; i++){
       if(floor(sqrt(i)) == ceil(sqrt(i)))
          { count++; }
   }
   return count;
}

int main(){
   int N = 40;
   int squares = squareNums(N);
   cout << endl << "완전제곱수 개수: " << squares;
   cout << endl << "비제곱수 개수: " << N - squares;
   return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

완전제곱수 개수: 6
비제곱수 개수: 34

이 방식은 시간 복잡도가 O(N)으로, N이 매우 커지면 실행 속도가 느려질 수 있다는 단점이 있습니다.

방법 2: 효율적인 접근 방식 구현

프로그램의 동작 원리

정수 N을 입력받습니다.
squares = floor(sqrt(N))로 설정합니다.
squares 변수에는 N 이하의 완전제곱수 개수가 저장됩니다.
N - squares 값이 곧 N 이하의 비제곱수 개수입니다.

코드 예제

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int main(){
   int N = 40;
   int squares = floor(sqrt(N));
   cout << endl << "완전제곱수 개수: " << squares;
   cout << endl << "비제곱수 개수: " << N - squares;
   return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

완전제곱수 개수: 6
비제곱수 개수: 34

마무리

효율적인 접근 방식은 반복문 없이 단 한 번의 sqrt 연산만으로 답을 구하므로 시간 복잡도가 O(1)입니다. N의 크기와 무관하게 일정한 성능을 보장하기 때문에, 실제 코딩 테스트나 대용량 데이터 처리 환경에서는 두 번째 방식을 사용하는 것이 바람직합니다. 다만 부동소수점 오차를 고려해야 하는 경우에는 sqrt 결과를 long long으로 변환한 뒤 근처 값을 검증하는 추가 안전장치를 넣어주는 것이 좋습니다.