1. 오늘의 문제
오늘은 어제와 이어 똑같은 유형의 이진탐색 문제가 나왔다.
승택이는 강을 건너려 한다.
승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.
승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.
승택이는 이제 강의 한쪽 변 앞에 서 있다.
강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.
강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.
이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.
물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.
- 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
- 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
- N번 징검다리는 반드시 밟아야 한다.
- N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.
승택이가 위의 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?
문제에서 승택이가 밟을수 있는 징검다리의 최대 수이기 때문에 첫번째 점프는 반드시 1이어야 하며, 1씩 증가하면서 뛰어야 한다.
결국 등차가 1 등차수열의 합을 구한 뒤, 합이 징검다리의 최대보다 많으면 리턴하면 된다.
for나 while 문으로도 가능하지만, 어제 배운 이진탐색을 적용해보기로 했다.
2. 쉽게 풀어쓴 이진탐색
이진탐색을 누군가에게 어떻게 쉽게 설명할 수 있을지 고민해 보았는데, 업다운 게임이 최고인 것 같다.
업다운 게임은 수의 범위를 지정하고 상대방이 부른 수보다 큰지, 작은지만 알려주며 임의의 숫자를 맞추는 게임이다.
술자리나 모임에서 하는 게임이니 인싸인 그대들은 알거라 생각한다.
보통은 램던하게 임의의 숫자를 부르며 정답에 많이 가까워 지려고 하지만, 값이 무엇인지 모르므로 확률 상 보았을 때 중앙 값을 부르는게 가장 유리하다.
예를들어, 술자리에서 소주병 뚜껑의 10이라는 숫자를 보고 범위를 0~100으로 잡았다고 하자.
그럼 나는 계속 중앙값만 부르는 것이다.
처음에는 50을 부르면 친구는 '다운' 이라고 할 것이다.
그럼 다시 50을 최고값으로 잡고 25(다운) -> 12(다운) 순으로 값을 점검한다.
6을 불렀을 때 친구는 '업'이라고 할 것이다.
그 때는 6을 최솟값으로 잡고 6~12의 중앙값인 9를 부른다.
그 다음 부터는 이전에 했던 행동의 반복이다.
이 과정을 반복하다 보면 결국 원하는 정답을 얻게 된다.
이진 탐색의 장점은 범위 내에서 어떤 값이 어디에 위치하든지 상관없이 거의 비슷한 탐색깊이를 가진다는 것이다.
범위가 2의 n제곱으로 감소하므로 범위가 100이면 7회 이내에 답을 찾는것이 가능하다.
이제 이 과정을 코드로 구현해보자.
3. 내가 풀어본 코드
위에서 적은 것과 똑같은 논리로 코드를 구현해 보았다.
from sys import stdin
# 먼저 받을 데이터의 횟수를 입력받는다.
put = stdin.readline
number = int(put())
# for문을 돌면서 데이터 입력
for i in range(number):
num = int(put())
# 최소, 최대의 범위는 1~다리의 개수로 잡았다.
max = num
min = 1
# 다리가 2개 미만이면 무조건 1이다.
if num <=2 :
print(1)
continue
# 그 이상일 경우 max가 min보다 작은 범위에서 반복한다.
while max > min:
# 중앙값과 등차수열의 합을 구한다.
mid = (max+min)//2
result = mid*(mid+1)//2
# 만일 min과 max가 같다면 답을 찾은것이므로 멈춘다.
if min == mid or min == max:
break
# 등차수열의 합이 징검다리의 개수보다 많으면 중앙값을 최댓값으로 한다.
if result > num:
max = mid
# 등차수열의 합이 징검다리의 개수보다 적으면 중앙값을 최솟값으로 한다.
else:
min = mid
print(mid)
5. 느낀점과 깨달은 점
어제 위와 같은 코드를 작성했을 때 무한 루프에 빠지는 현상이 있었다.
오늘 생각해보니 mid값을 2로 나눈 몫으로 정했으므로 최솟값이 3, 최댓값이 4일 때 징검다리의 개수가 5라면 최댓값과 최솟값이 계속 재할당되는 문제가 있었다.
그래서 최댓값, 혹은 최솟값이 중앙값과 같으면 루프를 빠져나오도록 하니 코드가 잘 작동한다.
이번 계기를 통해서 이진탐색을 제대로 알고, 스스로 구현할 줄도 알게 되어서 기쁘다.
오늘 남은 하루는 next.js를 배우는데 할애할 수 있을 것 같다.
내일 문제가 또 기대된다.
