[수학 - 제곱근]백준 제곱 수?(34027번) 풀이 (C++/Python)

사칙연산에서 덧셈, 뺄셈, 곱셈, 나눗셈에 대해 간단하게 알아봤습니다.

이 중에 곱셈에 대해 좀 더 깊게 공부할려고 합니다.

 

우선 2를 몇 번 곱하면 값이 각각 어떻게 나올까요?

먼저 1번만 곱하면 값은 2가 나옵니다.(1 * 2 = 2)

그 다음 2번 곱하면 값은 4가 나옵니다.(1 * 2 * 2 = 4)

그러면 2를 n번 곱하면 뭐라고 부를까요? 2^n이라고 부릅니다.

 

만약 2가 아닌 3으로 바꾸면 3^n이 되며 예시로 n=4이면 3^4 = 81이 됩니다.

이것을 일반화하면 다음과 같은 식이 나옵니다.

 

$$y = x^n$$

같은 수를 여러 번 곱하는 것을 거듭제곱이라고 부릅니다.

그리고 여기서 x를 밑(base), n을 지수(exponent)라고 부릅니다.

예시로 x = 5, n = 3이면 y = 125가 됩니다.

보통 주변에서 불리는 제곱은 n이 2일 때의 경우이며 n이 3이면 세제곱, n이 4이면 네제곱으로 부릅니다.

예시로 2^3이면 2의 세제곱이라고 부릅니다.

C++로 x, n을 입력할 때 x^n을 구하는 소스 코드를 구현합니다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long y, x, n;
    cin >> x >> n;

    y = 1;
    while(n--) y *= x;
    cout << y;

    return 0;
}

x = 3, n = 5로 입력하면 출력은 아래와 같이 나옵니다.

이렇게 해서 y = 3^5 = 243로 출력하게 됩니다.

 

그러면 그 반대도 가능할까요?

네 가능합니다. x, n이 주어지는 대신 y, n이 주어질 때 x를 구하는 수학 공식이 있습니다.

이것을 수식으로 표현하면 다음과 같습니다.

$$x = \sqrt[n]{y}$$

n=2인 경우 제곱근, n=3인 경우 세제곱근, n=4인 경우 네제곱근이라고 부릅니다.

예시로 9의 제곱근은 3, 8의 세제곱근은 2, 625의 제곱근은 5라고 부릅니다.

(3^2 = 9, 2^3 = 8, 5^4 = 625)

또한 n=2인 경우 다음과 같이 표현할 수 있습니다.

$$x = \sqrt{y}$$

n=2인 경우 숫자 2를 없애고 표현할 수 있으며 y의 제곱근 대신 루트 y라고 읽기도 합니다.

그리고 오늘 게시글 주제는 루트 값을 구하는 소스 코드를 구현하는 것입니다.

C++ 및 Python으로 구현할 수 있을까요?

결론부터 말하자면 그냥 sqrt() 함수를 호출해서 사용하세요.

왜냐면 실수 기초에서 보면 알겠지만 실수 연산 자체가 원래 많이 복잡합니다.

거기에 제곱근을 구하는 과정은 하드웨어 레벨에서 어셈블리어(SQRTSD)까지 이해해야 하고

소프트웨어 레벨에서도 뉴턴-랩슨 방법 수학 공식을 사용해야 할 정도로 많이 어려운 편입니다.

아래는 sqrt() 없이 루트 529를 구하는 Python 소스 코드입니다.

import sys
from decimal import Decimal, getcontext

input = sys.stdin.readline

getcontext().prec = 50

LIMIT = 100

dp:list = [Decimal('0') for _ in range(LIMIT + 1)]

# 529의 제곱근 구하기 위해 입력값을 529으로 설정합니다.
target:Decimal = Decimal('529')

# 초기값
dp[0] = (1 + target) / 2

# 점화식
for i in range(1, LIMIT + 1, 1) :
    dp[i] = Decimal('0.5') * (dp[i-1] + target / dp[i-1])

print(dp[-1])

이것을 실행하면 다음과 같습니다.

이렇게 이해하기 어려운 소스 코드를 통해 루트 529 = 23이라는 결과를 알게 됩니다.

그러면 부동 소수점 고려하면서 수학 공식까지 사용하면서 직접 제곱근을 구현해야 할까요?

다행히 C++ 및 Python에서 이미 천재 개발자 및 연구원들이 sqrt() 함수로 이미 내부에서 최적화된 코드로 구현해 놓았기 때문에 우리는 sqrt() 함수를 사용하기만 하면 됩니다.

 

먼저 C++로 루트 529 구하는 과정을 구현하면 다음과 같습니다.

#include <cmath>로 불러들어서 std::sqrt() 함수를 사용할 수 있습니다.

그러나 using namespace std;에 의해 sqrt()만 사용해도 됩니다.

이렇게 해서 C++에서는 루트 529를 아주 쉽게 구현할 수 있습니다.

 

Python으로 구현하면 어떻게 될까요?

import math를 통해 sqrt()를 호출할 수 있으며 math.sqrt()로 루트 529를 구할 수 있습니다.

그런데 매번마다 math.sqrt() 붙이기엔 귀찮죠?

그래서 저는 2가지 방법을 알려드립니다.

[1. C++의 #define처럼 사용하기]

import sys
import math

input = sys.stdin.readline
sqrt = math.sqrt

Y:float = float(input().rstrip())
print(sqrt(Y))

sqrt = math.sqrt로 C++의 별칭(alias) 혹은 매크로(macro)처럼 사용해서 더 간단하게 구현할 수 있습니다.

애초에 input = sys.stdin.readline도 같은 원리입니다.

[2. Java의 import static처럼 사용하기]

import sys
from math import sqrt

input = sys.stdin.readline

Y:float = float(input().rstrip())
print(sqrt(Y))

Java로 비유하면 import static java.lang.Math.sqrt;입니다.

from (모듈명) import (객체 목록) 형식으로 해서 특정 도구만 사용합니다.

math.sqrt처럼 모듈명.객체명 형식이면 from math import sqrt가 정석입니다.

하지만 input = sys.stdin.readline는 from sys import stdin까지 가능하나

그 안에 있는 메서드 readline까지는 표현할 수 없어 오히려 input = sys.stdin.readline가 정석입니다.

 

이제 제곱근을 구하는 방법을 알게 되었으니 이제부터 백준 문제를 해결하도록 하겠습니다.

 

 

문제 : 제곱 수?(34027번)(Bronze III)

문제 링크 : https://www.acmicpc.net/problem/34027

출처 : Baekjoon Online Judge

 

각 테스트 케이스마다 해당 자연수가 완전 제곱수인지 확인하면 되는 문제입니다.

완전 제곱수는 어떤 자연수의 제곱이 되는 수입니다.

1, 4, 9, 16, 25, 36, ...이 완전 제곱수입니다.

주어진 자연수가 완전 제곱수인지 확인할려면 그 자연수의 제곱근을 구해서 정수로 나오면 됩니다.

제가 따로 1부터 16까지 제곱근 값을 구하면 다음과 같습니다.

root 1 -> 1.0
root 2 -> 1.4142135623730951
root 3 -> 1.7320508075688772
root 4 -> 2.0
root 5 -> 2.23606797749979
root 6 -> 2.449489742783178
root 7 -> 2.6457513110645907
root 8 -> 2.8284271247461903
root 9 -> 3.0
root 10 -> 3.1622776601683795
root 11 -> 3.3166247903554
root 12 -> 3.4641016151377544
root 13 -> 3.605551275463989
root 14 -> 3.7416573867739413
root 15 -> 3.872983346207417
root 16 -> 4.0

우선 정수 부분만 확인합니다.

예시로 9이면 정수 부분은 3이며 3 * 3 == 9이므로 9는 완전 제곱수입니다.

반면 12는 정수 부분이 3이며 3 * 3 != 12이므로 12는 완전 제곱수가 아닙니다.

이 때 정수 부분을 구하는 방법은 sqrt(n)으로 루트 값을 구한 다음 실수 -> 정수 변환 과정에서 정수 부분 빼고 나머지 데이터가 모두 소실되는데 이 점을 역이용해서 int로 강제 형변환을 합니다.

 

이것을 C++로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        int n, m;
        cin >> n;
        m = (int)(sqrt(n));
        if(m * m == n) cout << 1;
        else cout << 0;
        cout << '\n';
    }

    return 0;
}

여기서 m은 루트 n의 정수 부분이며 m * m == n이면 n은 완전 제곱수입니다.

이 때 마지막에 cout << '\n'; 추가해주세요.

안 그러면 출력이 잘못 나와서 오답 처리 됩니다.

 

Python도 동일하게 구현하면 됩니다.

import sys
from math import sqrt

input = sys.stdin.readline

T:int = int(input().rstrip())

for _ in range(T) :
    N:int = int(input().rstrip())
    M:int = int(sqrt(N))
    
    if M * M == N :
        print(1)
    else :
        print(0)