[파이썬] 백준 13706 이분탐색이란

✅ 백준 문제 링크: 백준 13706번 - 제곱근

백준 13706

1. 이분 탐색(Binary Search) 기본 원리

 

이분 탐색은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘이다.

다음과 같은 방식으로 동작한다.

 

1️⃣ 배열의 중간값을 찾는다.

2️⃣ 찾고자 하는 값과 중간값을 비교한다.

• 중간값이 찾는 값보다 크면 왼쪽 부분을 탐색한다.
• 중간값이 찾는 값보다 작으면 오른쪽 부분을 탐색한다.

3️⃣ 이 과정을 반복하여 값을 찾을 때까지 탐색한다.

 

✅ 이분 탐색의 전제 조건:

• 탐색할 배열이 반드시 정렬된 상태여야 한다!

 

2. 이분 탐색 기본 알고리즘 (반복문 & 재귀 호출)

 

📌 반복문(Binary Search - Iterative)

#이분탐색 반복문
def binary_search(target, data):
    data.sort() #data 정렬 먼저
    start = 0 	#배열의 맨 처음 위치
    end = len(data) - 1 	# 배열의 마지막 위치

    while True:
        if start > end:
            break; # target 값 없음
        # 중간값 위치
        mid = (start + end) // 2				
        # target 값 찾음. 위치 반환
        if data[mid] == target:
            return mid 		
	    # target 값이 작으면 왼쪽 탐색. end 변경
        elif data[mid] > target: 
            end = mid - 1
        # target 값이 크면 오른쪽 탐색. start 변경
        else:
            start = mid + 1
    return

 

📌 재귀 호출(Binary Search - Recursive)

#이분탐색 재귀
def binary_search(target, start, end):
    if start > end:	    # 범위를 넘어도 못찾는다면 -1 반환
        return -1
    mid = (start + end) // 2  # 중간값 위치

    if data[mid] == target:   # target 값 찾음. mid 위치 반환
        return mid 
    # target 값이 작으면 왼쪽 탐색. end 변경
    elif data[mid] > target:
        end = mid - 1
    # target 값이 크면 오른쪽 탐색. start 변경
    else:
        start = mid + 1
    # 줄어든 범위를 더 탐색
    return binary_search(target, start, end)

def call_search(target, data):
    data.sort()  #data 정렬 먼저
    start = 0    #배열의 맨 처음 위치
    end = len(data) - 1  # 배열의 마지막 위치
    return binary_search(target, start, end) #이분탐색 호출

 

3. 문제 해결 방법 (제곱근 찾기)

 

이 문제에서는 이분 탐색을 활용하여 양의 정수 N의 제곱근을 찾는 문제이다.

• N의 제곱근은 항상 정수이다.
• 이분 탐색을 활용하여 제곱근을 찾는다.

4. 파이썬 코드 구현 (이분 탐색으로 제곱근 찾기)

import sys
#양의 정수 N이 주어진다
N = int(sys.stdin.readline().rstrip())
start = 0
end = N
#이분탐색 로직으로 정수 N의 제곱근 찾는다.
while True:
    #범위를 벗어나면 빠져나감
    if start > end:
        break
    #중간값 계산
    mid = (start + end) // 2    
    #제곱근이 N 보다 작으면 오른쪽 탐색
    if mid ** 2 < N:
        start = mid + 1
    #제곱근이 N 보다 크면 왼쪽 탐색
    else:
        end = mid - 1
print(start)

 

5. 예제 테스트

 

✔ 입력 예시 1

36

 

✔ 출력 예시 1

6

 

✔ 입력 예시 2

226576

 

✔ 출력 예시 2

476

 

6. 시간 복잡도 분석

• 이분 탐색의 시간 복잡도: O(log N)
• 최대 입력값 N이 800자리인 경우에도 매우 빠르게 동작한다! 🚀