코드업(codeup.co.kr) 1550 : 함수의 양의 제곱근의 정수 부분만 리턴하기 해설 (C언어)

문제설명

양의 정수를 입력 받아 제곱근의 정수 부분만 출력하시오.

어떤 수 n의 제곱근은 제곱하여 n이 되는 수를 말한다. 
예를 들어, 4는 (-2)*(-2) 또는 (2)*(2) 로 만들 수 있고 4의 양의 제곱근은 2를 의미한다.

3의 양의 제곱근은 1.7..... 이다.

단, 함수형 문제이므로 함수 sqrt()만 작성해 제출하시오.

 

입력

음이 아닌 long long int type 정수 n 이 입력된다.

출력

입력된 정수의 양의 제곱근의 정수부분만 출력한다.

입력 예시

16

출력 예시

4

 

해설

#include <stdio.h>

long long int n;


long long sqrt(long long a)
{
    long long int tmp = 0;
    for(long long i=0; i<=a;++i)
    {
        if(i*i > a) break; // 중단 끊기 
        else
        {
            tmp = i;
        }
    }
    return tmp;
}
int main()
{
  scanf("%lld", &n);
  printf("%d\n", sqrt(n));
  return 0;
}

 

O(n)의 time complex 를 가지지만 , 대부분의 테스트 케이스가 21억보다 현저히 작다.

if break 를 이용해 중간 지점에 끊어서 답을 내는 방식이다.

i 는 선형으로 x축을 따라 1씩 증가한다.

i*i 으로 중단을 잡았다.

빨간 점마다 if 로 검사하는 것이다.

 

결국 반복문이 표현식으론 O(n) 로 해결하는 것 같아 보이지만

중단점이 제곱으로 상승하기 때문에

실제로는 O(root(n))이다.

 

실제 큰 수를 다룰 때는 더 효율적인 알고리즘을 사용해야 한다.