[항해99] 99클럽 코테 스터디 0일차 TIL + 오늘의 학습 키워드

99클럽 코테 스터디 0일차 TIL + 이분탐색

오늘의 학습 내용

• 이분탐색을 활용한 알고리즘 구현
• 시간 초과 문제 해결 방법
• 백준 1072번 '게임'

공부한 내용

처음에는 단순하게 게임 한판 씩 추가로 수행하며 변화하는 승률을 비교하는 방식을 사용하였습니다. 그러나 입력 값이 큰 경우에는 시간 초과 문제가 발생하였습니다.

초기 시간 초과 코드

• 문제점:
  • 한 판씩 확인하는 방식으로 시간복잡도가 O(N)
  • 입력값이 큰 경우 실행 시간이 매우 길어짐
  • 메모리 사용량도 비효율적

X, Y = map(int, input().split())
Z = (Y * 100) // X  

# 승률이 99%이상이면 절대 바뀔 수 없음
if Z >= 99:
    print(-1)
else:
    result = 0

    while True:
        # 게임 한 판 추가
        X+=1
        Y+=1
        result+=1

        # 새로운 승률 계산
        new_Z = (Y * 100) // X

        # 승률이 변했으면 종료
        if new_Z > Z:
            break

    print(result)

시간 초과 문제를 개선한 코드

- 이분탐색을 사용하여 시간복잡도를 O(logN)으로 개선

X, Y = map(int, input().split())
Z = (Y * 100) // X  

# 승률이 99%이상이면 절대 바뀔 수 없음
if Z >= 99:
    print(-1)
else:
    # 이분 탐색
    left, right = 0, 10**9
    result = -1
    while left <= right:
        mid = (left + right) // 2
        new_X = X + mid
        new_Y = Y + mid
        new_Z = (new_Y * 100) // new_X

        if new_Z > Z:
            result = mid
            right = mid -1
        else:
            left = mid + 1


    print(result)

오늘의 회고

• 문제점과 시도
  • 처음에는 단순 반복문으로 접근했지만 시간 초과 발생
  • 시간 초과 문제를 해결하기 위해 '이분 탐색' 방법 활용
• 해결 과정
  • 이분탐색을 통해 시간복잡도를 O(log N)으로 개선
• 어떻게 해결했는지(이분탐색)
  • 단순 구현보다 알고리즘적 접근이 중요함을 깨달음
  • 시간 복잡도를 고려한 문제 해결의 중요성 인식
  • 수학적 접근방식의 효율성 확인
• 향후 계획
  • 처음 문제풀이시에 시간 초과문제를 의식하고 문제를 해결할 것