[240311] 알고리즘 리부트 29일차 - 백준 2417 자바

[Part1-Chapter07-Clip06]

매개변수 탐색은 이분 탐색을 이용해 최적값을 탐색하는 기법이다. 연속적인거나 이산적인 값의 집합에서 최적값을 X를 찾고자 할 때 X를 경계로 조건을 만족하는 집합과 답이 될 수 없는 집합을 판정할 수 있을 때 추정 값 A에 대한 판정을 반복해 X를 찾는 방법이다. 이때 판정의 대상이 되는 추정값을 구할 때 이분 탐색을 이용하면 O(logX)의 복잡도의 로직을 짤 수 있다. 보통 ~ 조건을 만족하는 최솟값과 최댓값을 구하라는 문제가 해당된다. 이전에 lowerBound와 upperBound를 찾았던 백준 10816 숫자 카드 2 문제에서 적용했던 것도 이 매개변수 탐색의 일종이라 할 수 있다. 

- 백준 2417 정수 제곱근

long의 범위에 있는 숫자를 찾으려면 범위가 너무 넓어서 어떻게 l와 r을 설정할지 막막했다. 그래도 달리 방도가 없으니 시작 값을 0으로 두고 끝 값을 주어진 n으로 설정해 이분탐색을 진행했다. 참고로 n의 최대값이 2의 63이니 이 수의 제곱근인 1<<32로 끝 값을 두어도 가능하다. 이분 탐색 시에는 upperBound를 구하는 방식을 사용했다. 여기서 틀렸던 부분은 long인 m을 이용한 제곱값을 구하는 방식이었다. 1) m*m으로 구할 경우 long의 범위를 넘어버림에 따라 예상하는 값이 나오지 않을 수 있다 대신 2) Math.pow(m,2)를 이용한다면 double 범위 내에서 처리하므로 연산 후 안전하게 비교가 가능하다. 사실 직관적으로 이해가 되지는 않지만  코테 때는 둘다 써보고.. 답인 걸로 제출하자.. ^^;;

import java.util.Scanner;

public class Main {
    // 이분 탐색 + yes/no problem
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long q = 0L;

        if (n == 0) q = 0;

        else {

            long l = 0;
            long r = n;
            // 여기 r 값을 지정하기가 어려웠는데 n의 최대값이 2의 63승이기 때문에
            // 제곱근의 값이 될 최대값을 1<<32 비트 연산자로도 나타낼 수도 있다.

            while (l <= r) {

                long m = (l + r) / 2;

                if (Math.pow(m, 2) < n) {
                    l = m + 1;
                } else {
                    r = m - 1;
                    q = m;
                }
            }
        }
        System.out.println(q);
    }
}