이진 탐색 정복 -array를 쓰지 않아도 되는 경우-

1. 문제1

 

13706번: 제곱근 (acmicpc.net)

13706번: 제곱근

 

정수 n의 제곱근을 찾는 프로그램을 작성

 

 

2. 풀이1

 

이분탐색으로 풀수있다는데 어떻게 가능할까

 

처음에는 이분탐색 알고리즘을 그대로 써서 n의 제곱근을 찾기 위해 0부터 n까지 숫자를 리스트에 담아두고

 

mid 포인트를 찾아서 array[mid]의 제곱이 target인 n이 되는 mid를 찾아 array[mid]를 return하는 방법으로 했는데

 

from sys import stdin

def binary_search(array,target,start,end):
    
    while start <= end:
        
        mid = (start+end)//2

        if (array[mid])**2 == target:
            
            return array[mid]
        
        elif (array[mid])**2 > target:
            
            end = mid-1
        
        elif (array[mid])**2 < target:
            
            start = mid + 1
    
    return 0


n = int(stdin.readline())

print(binary_search(list(range(0,n)), n, 0, n-1))

 

이게 overflow가 나더라고.. 아니 파이썬에서는 아무리 큰 정수도 overflow가 안나는거 아니었어? 했는데

 

왜 그런지 봤더니 다른데에 이유가 있더라

 

 

리스트에 너무 많은 수를 담으면 overflow가 나나봐

 

import sys

 

sys.maxsize로 최대로 저장할 수 있는 정수 크기가 있나본데

 

 

이게 변경해도 안되는것 같다.. 아무튼

 

중요한건 리스트를 만들 필요가 있나??

 

생각해보니까 그럴 필요가 전혀 없다

 

0부터 n까지에서 절반 mid 자체가 array[mid]랑 값이 똑같잖아??

 

그러니까 리스트를 만들지 말고 0부터 n까지 이 인덱스 자체를 그대로 활용하자고

 

from sys import stdin

def binary_search(target,start,end):
    
    while start <= end:
        
        mid = (start+end)//2

        if mid**2 == target:
            
            return mid
        
        elif mid**2 > target:
            
            end = mid-1
        
        elif mid**2 < target:
            
            start = mid + 1
    
    return 0


n = int(stdin.readline())

print(binary_search( n, 0, n-1))

 

2. 문제2

 

5688. 세제곱근을 찾아라

 

SW Expert Academy

SW Expert Academy

 

똑같은 문제인데 이번엔 $n=x^{3}$이 되는 정수 x를 찾는다. 그러한 정수 x가 없으면 -1을 출력

 

 

3. 풀이2

 

똑같은 방식으로 이분탐색을 수행하면 된다

 

array는 쓸 필요 없고 0~n의 인덱스만으로 mid 자체가 찾고자하는 값이니까 그대로 활용

 

인덱스가 정수이기때문에 이제 찾지 못하면 정수 세제곱근이 없는거고 -1을 return하도록

 

def binary_search(target,start,end):
    
    while start <= end:
        
        mid = (start+end)//2

        if mid**3 == target:
            
            return mid
        
        elif mid**3 > target:
            
            end = mid-1
        
        else:
            
            start = mid+1
    
    return -1

T = int(input())

for t in range(1,T+1):
    
    target = int(input())

    print('#'+str(t),binary_search(target,0,target))

 

 

3. 문제3

 

2417번: 정수 제곱근 (acmicpc.net)

2417번: 정수 제곱근

 

조금 더 어렵게 이번엔 제곱해서 n 이상이 되는 가장 작은 음이 아닌 정수를 찾는 문제

 

 

4. 풀이3

 

제곱해서 target 이상이 되는 가장 작은 정수를 찾는 문제

 

애초에 제곱근이 정수가 아닐 수 있다

 

똑같이 array를 만들지 말고 0 이상 n 이하의 index만을 가지고 제곱해서 n이 되는 mid 포인트를 찾아나간다

 

근데 이제 mid**2 >= target인 mid를 찾게된다면...

 

이 mid가 답은 아니겠지?

 

우리는 가장 작은 정수인 mid를 찾아야한다

 

그래서 mid-1의 제곱을 해보고 그것이 target보다 작다면 mid가 정답인데

 

그렇지 않다면 end를 mid-1로 해보고 다시 검사를 수행해서 더 작은 mid가 존재하는지를 탐색해야한다

 

from sys import stdin

def binary_search(target,start,end):
    
    while start <= end:
        
        mid = (start+end)//2

        if mid**2 < target:
            
            start = mid+1
        
        else:
            
            if (mid-1)**2 < target:
                
                return mid
            
            else:
                
                end = mid-1
    
    return end

n = int(stdin.readline())

if n == 0:
    
    print(0)

else:

    print(binary_search(n,0,n))

 

 

사실 이 문제는 결국 조건을 만족하는 가장 작은 정수를 찾는 문제이므로 lower bound를 찾는 문제이다.

 

mid**2이 target보다 작으면 start를 mid+1로 옮기고 크거나 같으면 end를 mid로 옮겨나간다

 

while이 끝나면 start = end가 되어서 end를 return하면 그것이 lower bound

 

근데 문제 제한조건을 보면 존재하지 않는 경우는 없는것 같아서 예외조건은 고려할 필요가 없을듯?

 

from sys import stdin

def lower_bound(target,start,end):
    
    while start < end:
        
        mid = (start+end)//2

        if mid**2 < target:
            
            start = mid+1
        
        else:
            
            end = mid
    
    return end

n = int(stdin.readline())

if n == 0:
    
    print(0)

else:

    print(lower_bound(n,0,n+1))

 

 

참고

 

 

[Python] sys.maxsize - 최대 정수값 (tistory.com)

[Python] sys.maxsize - 최대 정수값