Today's keyword : 이진탐색
이진탐색이란?
정렬된 배열에서 특정 값을 찾기 위해 반으로 나누면서 탐색해 나가는 알고리즘입니다. 이 방법은 배열이 정렬되어 있어야 사용 가능합니다.
이진탐색 작동원리
1. 초기 설정 : 배열의 시작과 끝 인덱스를 설정
2. 중간 인덱스 계산 : 시작 인덱스와 중간 인덱스 계산
3. 비교
- 중간 인덱스의 값이 찾고자 하는 값과 같으면 탐색 종료
- 중간 인덱스의 값이 찾고자 하는 값보다 크면, 끝 인덱스를 중간 인덱스 - 1로 설정하여 왼쪽 절반을 탐색
- 중간 인덱스의 값이 찾고자 하는 값보다 작으면, 시작 인덱스를 중간 인덱스 + 1로 설정하여 오른쪽 절반을 탐색
4. 반복 : 절반으로 나누면서 시작 인덱스가 끝 인덱스 초과할 때까지 반복
문제설명
형택이가 게임을 몇 번 더 해야 승률이 변하는지를 찾는 것으로, 주어진 입력은 두 개의 정수 (총 게임 수)와 (이긴 게임 수)입니다. 승률 는 𝑌를 𝑋로 나눈 후 100을 곱하여 계산합니다. 이때 소수점은 버립니다.
이 문제에서 이진 탐색이 필요한 이유는 예시 문제와 범위를 보면 탐색해야 할 범위가 큽니다. 단순히 반복문으로 순차적으로 탐색할 경우, 시간초과에 걸리게 됩니다. 이진 탐색을 사용하면 탐색 범위를 반으로 줄여가며 효율적으로 답을 찾을 수 있습니다.
이 문제는 승률이 증가하는 조건이 정렬된 상태로 나타납니다. 즉, 추가 게임 수가 증가할수록 승률도 증가하는 경향이 있습니다. 이진 탐색은 이러한 정렬된 상태에서 매우 효과적입니다.시간 복잡도는 O(log N)입니다.
https://www.acmicpc.net/problem/1072
문제풀이
X, Y = map(int, input().split())
current_win_rate = (Y * 100) // X # 현재 승률
# 승률이 변하지 않는 경우
if current_win_rate >= 99:
print(-1)
exit()
# 이진 탐색을 위한 초기 설정
min_games = 0
max_games = 10**9 # 충분히 큰 수로 설정
result = -1
while min_games <= max_games:
mid_games = (min_games + max_games) // 2
new_wins = Y + mid_games
new_games = X + mid_games
new_win_rate = (new_wins * 100) // new_games
if new_win_rate > current_win_rate:
result = mid_games # 승률이 변하는 경우
max_games = mid_games - 1 # 더 적은 게임 수를 시도
else:
min_games = mid_games + 1 # 더 많은 게임 수를 시도
print(result)
1. 현재 승률 계산: `current_win_rate`를 계산합니다. 이때 소수점은 버리기 위해 몫을 계산합니다.
2. 승률이 변하지 않는 경우 처리: 현재 승률이 99% 이상인 경우, 승률이 변하지 않으므로 -1을 출력합니다.
3. 이진 탐색 수행:
- 최소 게임 수(min_games)와 최대 게임 수(max_games)를 설정합니다.
- 중간 게임 수(mid_games)를 계산하여 새로운 승리 수와 게임 수를 업데이트합니다.
- 새로운 승률이 현재 승률보다 크면, 승률이 변하는 경우이므로 결과(result)를 업데이트하고 더 적은 게임 수를 시도합니다.
- 그렇지 않으면 더 많은 게임 수를 시도합니다.
3. 결과 출력: 최종적으로 승률이 변하기 위해 필요한 최소 게임 수를 출력합니다.
오늘의 회고
이진탐색의 기본적인 문제를 풀었다. 탐색 범위가 넓은 정렬된 배열에서 이진탐색은 효과적이며, 작동원리는 탐색 시작점과 끝점을 초기 설정한 후 조건에 맞을 때까지 (여기서는 승률 변화) 중간 인덱스를 업데이트 하는 방식으로 진행한다.
