99클럽 코테 스터디 1일차 TIL(이진탐색)

🚨오늘의 학습 키워드

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

⭐️이진탐색⭐️

이진 탐색이란 정렬돼 있는 데이터에서 특정한 값을 찾아내는 알고리즘
찾으려는 값(target)과 범위의 중간값(mid)을 비교해
범위를 변경하며 탐색한다

• 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식으로 동작한다.
• 주로 배열의 인덱스를 기준으로 배열 내의 값을 탐색하는데 사용되지만, 리스트, 트리 등에서도 사용할 수 있다(단, 정렬된)

1. 첫번째 시도

이진탐색을 어떻게 사용해야 하는지 모르겠다.

2. 두번째 시도 (참고 후)

이진탐색의 원리를 잘 생각해 보면 up/down으로 범위를 좁혀나가는 것이다
게임횟수에 따라 승률이 변하게 되는 게임 회수를 찾는 것이 문제의 목표이다
그렇다면 추가된 게임횟수에 의해 승률이 변화되는 최초 시점을 구하는 것이 문제이다
그래서 현재 주어진 승률과 게임 추가후 변경된 승률을 비교해본다

경우1) 추가된 게임의 승률 > 현재 승률

• 추가된 게임 수 보다 더 적게도 가능한지 확인
• (mid-1)

경우2) 추가된 게임의 승률 == 현재 승률

• 추가된 게임보다 더 많은 게임을 더 많이 추가해야 한다
• (left+1)

경우3) 현재 승률이 99% 이거나 100%

• 승률의 소수점을 고려하지 않으므로 99.99%=99.88%=99% 이다

• 그래서 아무리 게임을 추가하더라고 승률이 변하지 않는다.

  오늘의 회고

  이진탐색 원리는 알았는데 문제에 이렇게 직접 적용해보니 어떻게 해야하는건지 모르겠더라... 아는것과 적용하는건 다르다는 것을 느꼈다ㅠㅠ
  오늘 기억할 건 이진탐색 구현하기

1. 결과값을 범위 구하기
2. 범위의 중간값 구하기
3. 중간값과 결과값 비교하기
   3-1. 중간값 > 결과값
   • 중간값 줄이기 필요 -> end = mid-1
   3-2.중간값 < 결과값
   • 중간값 키우기 필요 -> start = mid+1
   👊🏻많이 경험해 보자!