제곱근

지침

이번 과제는 주어진 수의 제곱근을 계산하는 거예요.

• 사용하는 언어에 이미 있는 수학 라이브러리는 가급적 쓰지 않도록 해요.
• 입력으로는 1, 2, 3, 4… 같은 양의 정수가 주어져요.
• 결과가 양의 정수가 되는 경우만 처리하면 돼요.

몇 가지 가능한 접근 방법이 있어요:

• 제곱했을 때 입력한 수가 되는 수를 선형 탐색이나 이진 탐색으로 찾기.
• 뉴턴 방법이나 헤론의 방법을 이용한 연속 근사.
• 한 자리씩, 또는 한 비트씩 계산하기.

계산 방법을 고르는 데 도움이 되도록 정수 제곱근과 제곱근을 구하는 방법에 대한 위키백과 문서를 확인해 봐도 좋아요.

Python에서 이 연습 문제가 구성되는 방식

Python은 math 모듈과 거듭제곱 연산자 **, pow(), sum() 같은 내장 함수 등 다양한 수학 함수를 풍부하게 제공해요. 그렇지만 이런 내장 함수나 모듈 없이 이 연습 문제를 풀어보는 도전을 해보면 좋겠어요.

어떤 수든 제곱근을 구하는 수학 공식이 있긴 하지만, 여기서는 자연수(양의 정수)만 해로 삼는 방식을 택했어요.
어떤 자연수의 제곱근이든 계산 과정에서 자연수만 사용해서 구할 수 있어요.

---

출처

wolf99