1 - 2. Binary Search 예제 (백준: 정수 제곱근)

백준 2417(정수 제곱근)

이분 탐색 두번째 예제 입니다.

알고리즘 분류는 되어있지 않아서, 저도 우연히 접하게된 문제입니다.

정답율 자체도 크게 낮지 않고, 해결 방법도 여러가지라서 사실 굳이 이렇게 풀지 않으셔도 된다고 말씀드리고 싶네요.

조건 1

정수 n (0 ≤ n < 263)

long 범위내에 들어오는 수 입니다.

조건 2

q2 ≥ n인 가장 작은 음이 아닌 정수 q

1. 루트를 씌워서 딱 떨어지는 어떤 수의 제곱수면 상관이 없고

2. 소수점이 생기면 그냥 정수형으로 올림해서 출력하면 됩니다.

1. 예를들어 n이 15라면, 원래 제곱근은 3.xxxx 겠지만 4를 출력하시면 됩니다.

따라서, 자바의 경우엔 'Math.sqrt()'로 출력하시면 됩니다.

사실 저같은 경우엔 웬만하면 square root 함수를 잘 사용하지 않아서 (소수점이 생기면 괜히 불안하더라구요 ㅎㅎ)

가장 먼저 떠올린 풀이가 이분 탐색 이었습니다.

이분탐색으로 풀기엔 그렇게 적절한 문제라고 생각은 안되니 참고만 하시길 바랍니다.

1. 큰 수 연산?

• n이 어떤 수의 제곱입니다. 

• 다행히 우린 제곱근을 받아서 그 수의 제곱을 뽑는게 아니고 어떤 수(long 범위)를 받아와 그 수의 제곱근을 뽑아주면 됩니다.
• 따라서 매우 큰 수의 연산 이런것이 따로 필요하지 않고 해당 수만 찾으면 됩니다.

2. 정렬 할 것이 존재하는가?

• 이 문제도 이전 게임 문제와 마찬가지로 'long 범위 내의 어떤 수'이므로 이미 정렬된 고정 데이터 내에서 탐색입니다.

우선 우리가 찾으려는 수가 제곱근: q 인데, 저는 'target = 어떤 수 제곱'으로 잡았습니다.

이 문제에선 따로 배열에 담을 필요없이 일정 간격을 가진 값들을 하나씩 찾아보면 됩니다.

따라서 아래에서 말씀드리는 start, end, mid는 수 그 자체라고 이해하시면 될 것 같아요.

즉, 이분탐색을 통해서 1 ~ (Long.MAX_VALUE / 2) 까지 돌립니다.

거기서 나온 값 mid를 제곱하여 target과 같은지 찾아서 반환해주면 됩니다.

결과가 long 범위내에 있으니 long 최댓값의 제곱근을 end로 잡아도 되지만, 발생할 예외를 대비했습니다.

그래서 조금 여유잡아서 (Long.MAX_VALUE / 2)로 잡았습니다.

이제 이분 탐색을 해서 target = mid * mid; 값을 구하고

딱 떨어지는 mid 값을 찾으면 이분탐색을 종료하고 아니면 start <= end 까지 돌린 후 mid 값을 결정합니다.

(1)

주의하실 점으로 최대(end)가 Long.MAX_VALUE / 2의 값이기 때문에 분명 long 범위를 벗어나는 값이 나올 수 있습니다.

따라서 범위가 넘어가면 음수가 발생하는데, 제곱한 값이 음수가 나올 순 없잖아요. (허수의 경우 제외)

그런 값이 나온 경우 원하는 값보다 큰 것으로 판단해 'end = mid - 1' 이렇게 잡아줍니다.

그리고 타겟 값 자체가 우리가 입력 받은 수 N보다 큰 경우도 마찬가지로 값이 넘어간 경우니까 같이 포함해줍시다.

if(target > N || target <= 0) end = mid - 1;

(2)

 target이 작은 경우엔 평소처럼 지정해주세요.

else if(target < N) start = mid + 1;

(3)

찾은 경우엔 그냥 반복문 끝내면 됩니다.

else break;

(4)

아까 조건 2에서 '정수형으로 올림해서 출력해야한다'라고 말씀드렸는데요.

분명히 딱 떨어지는 제곱근이라면 제대로 된 답이 출력 될 겁니다.

하지만 떨어지지 않는다면? -> 오답 

아까 예시를 든 것처럼 15를 넣으면 3이 출력 될겁니다.

그래서 마지막에 mid의 제곱이 N과 같은가 비교를 해보고 다르다면 mid+1을 해주는 작업을 한 후 답을 반환해 줍니다.

if(N > mid * mid) mid++;

2417번 Binary Search 메소드

private static long binarySearch(long N) {        
    long start = 1, end = N / 2;
    long mid = 0;
        
    while(start <= end) {
        mid = (start + end) / 2;
            
        long target = mid * mid;
        
        if(target > N || target <= 0) end = mid - 1;
        else if(target < N) start = mid + 1;
        else break;
    }
        
    if(N > mid * mid) mid++;
        
    return mid;
}

Main 메소드는 별거 없습니다. 입력 받은 수를 이분탐색 메소드를 통해 바로 출력해주시면 됩니다.

Boj2417.java 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        
        System.out.println(binarySearch(n));
    }
    
    private static long binarySearch(long N) {        
        long start = 1, end = N / 2;
        long mid = 0;
        
        while(start <= end) {
            mid = (start + end) / 2;
            
            long target = mid * mid;
            
            if(target > N || target <= 0) end = mid - 1;
            else if(target < N) start = mid + 1;
            else break;
        }
        
        if(N > mid * mid) mid++;
        
        return mid;
    }
}
 

제출 결과

저는 (4)의 조건을 빼먹고 한번 틀렸었네요..ㅎㅎ

이 문제의 시간 복잡도는 O(long(Long.MAX_VALUE / 2)) 이므로, 대략 O(60)정도 나오네요.

결과 시간도 꽤나 빠르게 나왔습니다. ㅎㅎ

이해안가는 것이나, 질문 또는 잘못된 부분은 댓글로 지적 부탁드려요. 감사합니다.

문제의 저작권은 백준 온라인 저지에 있습니다.