99클럽 코테 스터디 1일차 TIL

1일차 TIL
처음 벨로그를 써보는데 이렇게 쓰는게 맞는지 모르겠지만 잘 써보도록 하겠다.

오늘의 학습 키워드

이진탐색

오늘의 회고

문제

처음에 구현은 올바르게 하였지만, 시간 초과로 여럿 실패를 했었다.

새롭게 알게된 부분은 다음과 같다.

---

1. sys.stdin의 활용

시간초과가 날 경우에 sys.stdin을 활용하면 문제를 해결할 수 있다는 사실을 알고는 있었지만, 익숙하지 않아 쉽게 사용함에 어려움이 있었다. 다시 한번 찾아보고, 정리하여 익숙해지고자 하였다.

sys.stdin이란?
파이썬의 표준 입력 스트림을 나타내며, 일반적으로 사용자나 파일, 파이프 등으로부터 데이터를 입력받을 때 사용. sys.stdin은 파일 객체처럼 동작하므로, 파일을 다루는 것처럼 여러 메서드를 사용 가능.

• input()과 sys.stdin의 차이점
  input(): 한 줄의 문자열을 입력받아 반환. 입력이 끝나기 전까지 프로그램이 멈춘다.
  sys.stdin: 전체 입력, 한 줄 또는 모든 줄을 필요에 따라 읽을 수 있다. 파일, 파이프 등 다양한 입력 소스를 처리할 수 있다.

• sys.stdin 메서드 종류
  sys.stdin에서는 파일과 유사한 메서드인 read, readline, readlines를 사용하여 데이터를 읽을 수 있다.
  

그럼 sys.stdin.readline()과 input() 의 차이는 뭘까?

간단히 정리하면 간단한 사용자 입력의 경우 input()이 편리하고,
대량의 입력 또는 반복적인 입력이 필요한 경우sys.stdin.readline()이 더 빠르며 효율적으로 처리가 가능하다.

2. 이진 탐색

위 문제에서는 반복적 탐색으로 발생하는 시간을 줄이고자 이진탐색을 이용하였다.

이진탐색으로 구현하는 부분이 처음이라 어려워서, 인터넷을 통해 찾아보고 구현하는 연습을 진행하였다.

이진탐색 루프 설명

현재의 승률과 추가 승리 후 승률을 비교하면서 범위를 좁히는 방식으로 진행한다.

mid를 계산해 현재 범위(start와 end)의 중앙값으로 잡고, 현재 추가로 시도하는 게임 수로 설정하여 새로운 승률을 계산한다.

이렇게 구한 새 승률이 기존 승률과 동일하다면, 아직 승률이 증가하지 않았기에 start값을 mid + 1로 증가시켜 새로운 mid값으로 업데이트 하여 다시 비교한다.

만약 새 승률이 기존 승률보다 크다면 end를 mid - 1로 줄여 더 작은 추가 승리 횟수로도 승률 증가가 가능한지를 탐색한다.
계속 줄여서 승률이 증가하지 않는 end값을 찾아야 하는데,start가 end보다 커지면 되므로 이때까지 진행하여 과정을 마무리하고 마지막 end값을 설정한다.

예시는 다음과 같다.