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

안녕하세요, 여러분! 오늘은 C++을 사용한 코딩테스트 강좌를 통해 “제곱이 아닌 수 찾기”라는 주제로 깊이 있는 문제 풀이를 해보겠습니다. 이 문제는 알고리즘의 기초 개념을 이해하는 데 매우 유용하며, 실제 코딩 면접에서 자주 등장할 수 있습니다.

문제 정의

주어진 정수 배열이 있습니다. 이 배열에서 특정한 범위의 정수를 추출할 때, 해당 범위 내에서 제곱수(2의 제곱, 3의 제곱 등)의 개수가 몇 개인지를 세는 문제입니다. 정확히 말하자면, 배열에서 제곱수가 아닌 수를 찾는 것이죠.

문제 설명

입력:
- 정수 n: 배열의 크기
- 정수 배열 A[n]: n개의 정수로 이루어진 배열
- 정수 m: 범위의 시작 (inclusive)
- 정수 p: 범위의 끝 (inclusive)

출력:
- 제곱수가 아닌 수의 개수

예시:
입력
n = 5
A = [1, 2, 3, 4, 5]
m = 1
p = 5

출력
3  // 2와 3은 제곱수가 아니며, 1과 4는 제곱수입니다.

문제 해결 전략

문제를 해결하기 위해 다음의 절차를 따르겠습니다:

배열 내의 모든 수를 확인하고 제곱수인지 확인하는 함수를 만듭니다.
주어진 범위 [m, p] 내의 수들 중에서 제곱수가 아닌 수를 셉니다.
결과를 출력합니다.

제곱수 판별 함수

제곱수를 판별하기 위해, 각 수의 제곱근을 구하고 이를 정수로 변환한 후, 다시 제곱하여 본래의 수와 같은지 확인하면 됩니다. Python의 경우는 다음의 코드를 사용할 수 있습니다:

bool isPerfectSquare(int x) {
    int s = sqrt(x);
    return (s * s == x);
}

C++에서는 cmath 라이브러리를 사용하여 sqrt() 함수를 사용할 수 있습니다. 제곱수가 아닌 수를 세기 위해, for 루프를 사용하여 해당 범위의 수를 검사하면 됩니다.

C++ 코드 구현

이제 우리가 논의한 내용을 바탕으로 C++ 코드를 구현해보겠습니다.

#include 
#include 
#include 
using namespace std;

bool isPerfectSquare(int x) {
    if (x < 0) return false; // 음수는 제곱수가 아닙니다.
    int s = sqrt(x);
    return (s * s == x);
}

int countNonPerfectSquares(const vector& arr, int m, int p) {
    int count = 0;
    for (int num : arr) {
        if (num >= m && num <= p && !isPerfectSquare(num)) {
            count++;
        }
    }
    return count;
}

int main() {
    int n, m, p;
    cout << "배열의 크기(n)를 입력하세요: ";
    cin >> n;
    vector arr(n);
    
    cout << "배열의 요소를 입력하세요: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "범위의 시작(m)을 입력하세요: ";
    cin >> m;
    cout << "범위의 끝(p)을 입력하세요: ";
    cin >> p;

    int result = countNonPerfectSquares(arr, m, p);
    cout << "제곱이 아닌 수의 개수: " << result << endl;

    return 0;
}

코드 설명

위의 C++ 코드는 다음과 같이 작동합니다:

사용자로부터 배열의 크기와 배열의 요소를 입력받습니다.
범위의 시작과 끝을 입력받습니다.
countNonPerfectSquares() 함수를 호출하여 주어진 범위 내에서 제곱수가 아닌 수의 개수를 계산합니다.
결과를 출력합니다.

테스트 케이스

이제 몇 가지 테스트 케이스를 실행해서 코드가 잘 작동하는지 확인해봅시다.

예시 1:
입력:
5
1 2 3 4 5
1
5

출력:
3 // [2, 3, 5]가 제곱수가 아닙니다.

예시 2:
입력:
6
-1 0 1 2 3 4
0
4

출력:
3 // [0, 2, 3]가 제곱수가 아닙니다.

결론

오늘은 C++ 코딩테스트 강좌를 통해 “제곱이 아닌 수 찾기”라는 주제를 다뤘습니다. 이 문제는 제곱수와 비제곱수의 개념을 이해하고, 배열 내에서 특정 범위의 수를 평가하는 로직을 구현해볼 수 있는 좋은 기회였습니다. 여러분이 이 코드를 통해 알고리즘 문제를 해결하는 방법을 익히고, 실제 코딩 면접에도 대비할 수 있기를 바랍니다.

이 글이 여러분에게 도움이 되었기를 바랍니다. 다음 시간에도 더욱 재미있고 유익한 주제로 찾아뵙겠습니다!