[c++] 1. 코드 작성 요령 1 - 문제 3

문제 3

* N이 제곱수이면 1을 반환하고 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라.
* N은 10억 이하의 자연수이다.
* 
* 출력 예시
* func3(9) = 1,
* func3(693953651) = 0,
* func3(756580036) = 1

 

풀이

제곱수인지 판단하는 문제이므로, 제곱근의 존재 유무를 파악한다.

1. math.h의 sqrt() 함수 이용

2. sqrt()함수를 직접 구현

  - 바빌로니아 법 알고리즘(https://s-realstory.tistory.com/17)

   └ 임의의 수의 제곱근에 빠르게 수렴하는 수열을 만들어 근사값을 구하는 방법.

   └ 수학적으로 이차방정식의 근을 근사하는 것과 같다고 함.

          where, x_n = 추정된 근사값, a = 제곱근을 구하고자 하는 수, 초기 x_n은 a//2로 설정하면 됨. 

3. 1~N까지 제곱해서 N이 나오는 수가 있는지 판단함. 

  - 매우 느리다. 1,2번에 비해 500배 정도 느림.

 

코드

바빌로니아법 구현

 

알게 된 점

1. cout 할시에 문자열은 쌍 따움표(“”) 써야함

2. 배열의 길이(length, 원소 수)를 구하기 위해서 = 배열 전체의 사이즈/배열 원소 하나의 사이즈 해줘야함.

    int arr[] = { 9, 693953651, 756580036 };

    int length_arr = sizeof arr / sizeof arr[0];

3. 문제 3에서 sqrt()함수를 사용하면, 강의에서 얘기한 반복만을 사용한 것보다 560배 빠르게 동작 가능하다.

4. sqrt()함수를 custom으로 구현해보면서(구글서치), 바빌로니아 법 알고리즘을 알게 됨.

5. time.h를 이용해서 현재시각을 구하는 clock()과 time을 구하는 time()에 대해서 다루어 보았다. time은 시간단위가 (초)이고, clock()의 시간단위는 (ms)이다.

 

github 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/1.%20%EA%B8%B0%EC%B4%88%20%EC%BD%94%EB%93%9C%20%EC%9E%91%EC%84%B1%20%EC%9A%94%EB%9F%89%20I/%EB%AC%B8%EC%A0%9C3.cpp