1. 오늘의 주제 : 백준 1072번, 이진탐색
오늘은 코딩 테스트 첫날. 주어진 문제는 백주의 1072번 문제였다.
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.
이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.
게임 기록은 다음과 같이 생겼다.
- 게임 횟수 : X
- 이긴 게임 : Y (Z%)
- Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.
X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.
간단하게 예를 들어보면 형택이가 총 10번 게임중에 5번을 이겼다고 하자.
이때 승률은 퍼센트에서 소숫점을 버리면 50%이다.
그럼 앞으로 게임을 할 때 계속 이긴다면, 몇번을 해야 승률이 올라가는가?
만약 1번을 이긴다면 승률은 6/11 * 100 ==> 54% 이므로 1번만 이기면 된다.
결과부터 이야기해보자면 엄청나게 틀리다가 결국에는 티스토리 형님들의 글을 보고 깨닫게 되었다.
2. 무엇이 문제였나?
처음에는 그냥 간단하게 while문으로 해결하려고 했다.
해결은 가능하다.
하지만 문제는 처음부터 끝까지 숫자를 더하면서 탐색하므로 시간이 엄청나게 오래 걸린다.
from sys import stdin
from sys import exit
put = stdin.readline
games, win = map(int, put().split())
# 퍼센트 몫을 구함
quotient = win*100/games
# 만일 99%라면 100%는 불가능하므로 종료
if quotient >= 99:
print(-1)
exit(0)
# while문을 돌면서 값을 찾음
more = 0
while True:
games += 1
win += 1
more += 1
percent = win/games
percent *= 100
quotientRe = int(percent // 1)
if quotient != quotientRe:
break
print(more)
2초 안에 문제를 해결하기 위해서는 이진탐색이라는 알고리즘을 사용해야 했다.
3. 이진탐색이란?
이진탐색은 정렬되어 있는 값들 중 특정한 값을 찾기 위해 이용하는 알고리즘이다.
이진 탐색을 위해서는 먼저 데이터가 정렬되어 있다는 조건이 필요하다.
말이 어려운데 그냥 업다운 게임에서 중간값만 부른다고 생각하면 된다.
예를들어 0~10까지의 숫자가 있다고 하자.
이 중에 7라는 숫자를 찾는 과정을 설명해보자.
1) 이진탐색으로 0~10에서 7찾기
- 범위에서의 중앙값이 찾고자 하는 숫자보다 큰지, 작은지를 비교한다.
- 만일 중앙값보다 찾고자 하는 값이 크다면, 이전의 중앙값 보다 큰 값에서 중앙값을 찾고 비교한다.
- 만일 중앙값보다 찾고자 하는 값이 작다면, 이전의 중앙값보다 작은 값에서 중앙값을 찾고 비교한다.
- 값이 찾아질 때 까지 이 과정을 반복한다.
여기서는 0~10까지의 숫자 중 7을 찾기위해서 5번의 이진탐색을 진행했다.
만일 이것을 0에서부터 10까지 숫자를 더했다면 적어도 8번의 덧셈을 해야 했을 것이다.
값의 범위가 넓으면 넓을수록 원하는 값을 찾기 위해 탐색해야 하는 범위 차이는 더 커질 것이다.
문제는 어떻게 이걸 문제에 적용해야 할지 감이 오지 않았다.
3. 문제에 적용해보기
문제에서는 결국 '어떠한 값을 더해야 마지막 자리가 변화하는가' 이다.
따라서 중앙값을 더해보면서 범위를 좁혀나가는 방식이다.
1) 중앙값을 분모, 분자에 더했을 때 마지막 자리가 변화하지 않는다면 중앙값보다 큰 범위에서 탐색한다.
2) 중앙값을 분모, 분자에 더했을 때 마지막 자리가 변화한다면 중앙값보다 작은 범위에서 탐색한다.
3) 이것을 반복한다.
이제 이것을 코드로 구현해보자.
4. 파이썬으로 구현해보기
아래는 파이썬으로 해당 코드를 구현하면서 주석을 달아보았다.
from sys import stdin
from sys import exit
put = stdin.readline
games, wins = map(int, put().split())
# 먼저 몇퍼센트인지 구해본다.
percent = wins*100//games
# 탐색의 범위를 임의로 지정한다.
# 보통 티스토리 형님들은 총 게임횟수로 하시더라
left = 0
right = games
# 만일 99%이상이면 -1을 출력하고 멈춘다.
if percent >= 99:
print(-1)
exit(0)
# 최소값이 최대값보다 작을 때만 반복한다.
while right > left:
# 중앙값을 구하고....
mid = (right+left) // 2
# 중앙값을 분자, 분모에 더한 것보다 기존의 값이 더 작으면 중앙값보다 작은 범위에서 탐색
if (wins + mid)*100//(games+mid) > percent:
right = mid
# 그게 아닐경우 중앙값보다 큰 범위에서 탐색
else:
left = mid + 1
# 루프를 탈출하면 두 값을 더한 뒤 몫을 출력
print((right+left)//2)
5. 느낀점
이진탐색이라는 것을 들어는 보았지만, 이것을 문제에 해결해 본건 처음이었다.
설명은 길었지만 구현하는 코드는 생각보다 짧음에 첫번째로 놀라고, while문을 통해 탐색하는 것보다 속도가 월등히 빠름에 두번째로 놀랐다.
문제 해결의 과정에서 알고리즘이 중요하다는 것을 다시금 깨닫는 시간이었다.
6. 내일 공부할 것
원래는 문제 하나 스근하게 풀고 자바 스크립트나 타입 스크립트로도 풀어보려고 했는데 그건 나의 오만이었다.
그냥 나오는 문제 보고 열심히 알고리즘 공부 한 뒤에, Next.js로 대시보드나 클론코딩 해봐야 겠다.
더욱 겸손해지는 하루였다.
