2417 정수제곱근

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read())

start = 0
end = N

while start <= end :

    mid = (start+end)//2
    if mid**2 == N :
        start = mid
        break

    elif mid**2 > N : # 더 줄여야한다 mid를
        end = mid-1
    else : # mid를 더 키워야한다.
        start = mid +1

print(start)

3. 생각 및 풀이

생각

이 문제는 기초적인 이분탐색 문제이다. 드디어 처음으로 내손으로 이분탐색 문제를 풀었다!

문제 풀이

제곱근이란 결국 0과 자신 사이에 어딘가에 존재할 것이다. 단 빠르게 찾기 위해서 이분 탐색을 이용해서 찾으면 되는 것이다. 시작은 0, 끝은 자기 자신 N으로 해서 절반 값을 mid로 두고 출발한다. 그리고 이분 탐색을 하면서 만약 mid의 제곱과 N이 같다면 반복문을 끝내고 출력하면되고, 아니라면 최종 start 값이 정답이 된다.

사실 나는 가끔 문제들 보면 어떤건 start, 어떤건 end를 출력값으로 놔야한다는 것들이 많아서 어떻게 판단해야하는지 잘 몰랐다. 그래서 이번 문제는 한번 예제를 손으로 적어가면서 감을 익혔는데, 앞으로도 이런식으로 파악하면 될 것 같은 느낌이 든다.