양수 n과 정밀도 p가 주어졌다고 가정해 보겠습니다. 이진 탐색(binary search) 기법을 활용하면 숫자 n의 제곱근을 소수점 p자리까지 구할 수 있습니다. 예를 들어 n = 50, p = 3이라면 결과는 7.071이 됩니다.
문제 해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 범위 초기화: 시작값(start)은 0으로, 끝값(end)은 n으로 설정합니다.
- 정수 부분 탐색: 중간값(mid)의 제곱과 목표 숫자를 비교합니다. 두 값이 일치하면 정수 부분을 찾은 것이고, 일치하지 않으면 조건에 따라 왼쪽 또는 오른쪽 범위를 계속 탐색합니다.
- 소수 부분 계산: 정수 부분을 구한 뒤에는 소수 부분에 대한 계산으로 넘어갑니다.
- 증분 값 조절: 증분(increment) 변수를 0.1로 초기화하고, p자리까지 소수 부분을 계산합니다. 매 반복마다 증분 값은 이전 값의 1/10로 줄어듭니다.
- 결과 반환: 최종적으로 계산된 제곱근 값을 반환합니다.
예제 코드
#include<iostream>
using namespace std;
float sqrtBinarySearch(int num, int p) {
int left = 0, right = num;
int mid;
float res;
while (left <= right) {
mid = (left + right) / 2;
if (mid * mid == num) {
res = mid;
break;
}
if (mid * mid < num) {
left = mid + 1;
res = mid;
} else {
right = mid - 1;
}
}
float incr = 0.1;
for (int i = 0; i < p; i++) {
while (res * res <= num) {
res += incr;
}
res -= incr;
incr /= 10;
}
return res;
}
int main() {
int n = 50, p = 3;
cout << "Square root of " << n << " up to precision " << p << " is: " << sqrtBinarySearch(50, 3) << endl;
}실행 결과
Square root of 50 up to precision 3 is: 7.071