99클럽 코테 스터디 1일차 이분 탐색/ 이진 탐색

오늘의 학습 키워드

이분 탐색/이진 탐색(Binary Search)

이분 탐색(이진 탐색)이란?

• 정렬되어 있는 리스트에서 탐색 범위를 타노스처럼 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 탐색 기법중 하나로, 탐색하고 싶은 범위를 두 부분으로 분할해서 찾는 방법이다.
• 두 부분으로 계속 분할해서 조건에 맞는지 찾아가기 때문에, 시간 복잡도가 O(log n)으로 매우 빠른편
  
  ex) 소주 뚜껑에 써져 있는 숫자를 맞추는 up&down 게임
  • 뚜껑에 1~100까지 써져 있고 숫자를 맞출 때 대부분의 사람들은 중간의 숫자인 50을 외친다.
  • why? 숫자의 범위를 반으로 줄일 수 있다!
  • 숫자가 99인데 완전 탐색을 한다면? 1부터 99까지 다 무식하게 해야됨;;

---

오늘의 문제

백준 1072번

https://www.acmicpc.net/problem/1072

1. 승률 99% 이상 예외 상황 처리

if z >= 99:
    print(-1)
    exit()

• 승률이 99% 이상이면, 추가 게임으로 승률을 올릴 수 없기 때문에 -1을 출력하고 프로그램을 종료

  ---

2. 이분 탐색 범위 정하기

start = 1
end = 1000000000
result = -1

---

3. 이분 탐색을 통해 최소 추가 게임 횟수 찾기

while start <= end:
    mid = (start + end) // 2
    if (y + mid) * 100 // (x + mid) > z:
        result = mid
        end = mid - 1
    else:
        start = mid + 1

• mid = (start + end) // 2 : 중간 값을 계산. 이는 추가 게임 수의 후보를 결정하는 역할.
• (y + mid) * 100 // (x + mid) > z:
  • mid번 게임을 더 이겨서 새로 계산한 승률.
  • 추가한 게임(mid번)으로 인해 승률이 기존 승률 z보다 커지는지를 확인.
  • 만약 승률이 커졌다면, result를 mid로 설정하고 end를 mid - 1로 줄여 더 적은 추가 게임 수로 승률을 올릴 수 있는지 확인.
  • 승률이 변화하지 않는다면 start를 mid + 1로 늘려 더 많은 게임이 필요한지 탐색.

---

전체 풀이

x, y = map(int, input().split())
z = (y * 100) // x

if z >= 99:
    print(-1)
    exit()

start = 1
end = 1000000000
result = -1

while start <= end:
    mid = (start + end) // 2
    if (y + mid) * 100 // (x + mid) > z:
        result = mid
        end = mid - 1
    else:
        start = mid + 1

print(result)

---

오늘의 회고

🔥 이분 탐색의 원리는 알지만 문제에 적용하는 데 어려움이 있었다.
->이분 탐색의 개념도 찾아보고 적용해서 간단한 문제를 풀고 적용해보았다.
🔥 내일은 2일차 문제 + 이분 탐색 문제 1개 더 풀면서 복습 예정!