한 문단 요약
업다운 게임은 정답이 정해진 범위 안의 정수 하나이고, 추측할 때마다 "더 크다(UP)" 또는 "더 작다(DOWN)"만 알려 주는 게임입니다. 힌트가 후보를 절반 가까이 지워 주기 때문에, 매번 남은 범위의 한가운데를 부르면 1~100에서는 최악의 경우에도 7번 안에 반드시 맞힙니다. 이 페이지는 그 이유를 계산으로 보여 주고, 남은 후보 범위와 추천 숫자를 화면에 표시해 전략을 연습하게 해 줍니다.
원리: 이진 탐색
남은 후보가 L개일 때 가운데 숫자를 부르면 정답이거나, 후보가 약 L/2개 이하로 줄어듭니다. 후보가 1개가 될 때까지 필요한 횟수는 후보 수를 반복해서 절반으로 나누는 횟수와 같습니다. 정확한 최악의 시도 횟수는 올림 log2(N+1), 즉 내림 log2(N)+1입니다. 흔히 올림 log2(N)로 외우지만 N이 2의 거듭제곱일 때는 한 번 차이가 납니다. 예를 들어 N=64이면 올림 log2(64)=6이지만 실제 최악은 7번입니다. 1~100처럼 N=100이면 두 식이 모두 7로 같습니다. 아래 표는 모든 정답 후보에 대해 직접 시뮬레이션한 값입니다(빌드 시 계산).
| 범위 1~N | 최악 시도 수 | 올림 log2(N) | 올림 log2(N+1) | 평균(중간값 전략) | 평균(무작위 찍기) |
|---|---|---|---|---|---|
| 10 | 4 | 4 | 4 | 2.90 | 3.44 |
| 20 | 5 | 5 | 5 | 3.70 | 4.56 |
| 50 | 6 | 6 | 6 | 4.86 | 6.18 |
| 64 | 7 | 6 | 7 | 5.13 | 6.64 |
| 100 | 7 | 7 | 7 | 5.80 | 7.48 |
| 128 | 8 | 7 | 8 | 6.07 | 7.95 |
| 500 | 9 | 9 | 9 | 8.00 | 10.61 |
| 1000 | 10 | 10 | 10 | 8.99 | 11.99 |
무작위 찍기는 남은 후보 안에서 아무 숫자나 부르는 전략의 평균을 점화식으로 정확히 계산한 값입니다. 매번 후보를 절반으로 가르지 못하기 때문에 1~100에서 평균이 약 7.5회로, 중간값 전략의 5.8회보다 늘 큽니다.
1~100에서 시도 횟수 분포
중간값 전략(내림)을 쓸 때 100개 정답이 각각 몇 번 만에 나오는지 센 값입니다. 7번째에 맞히는 정답이 가장 많고 8번째는 없습니다.
| 시도 횟수 | 해당하는 정답 개수 |
|---|---|
| 1번 | 1개 |
| 2번 | 2개 |
| 3번 | 4개 |
| 4번 | 8개 |
| 5번 | 16개 |
| 6번 | 32개 |
| 7번 | 37개 |
총 시도 합이 580회이므로 평균은 5.8회입니다. 이 전략은 100개 중 어떤 정답이든 7번 안에 끝납니다.
예시 1: 정답이 73일 때
| 회차 | 입력 | 힌트 | 남은 후보 |
|---|---|---|---|
| 1 | 50 | UP | 51~100 |
| 2 | 75 | DOWN | 51~74 |
| 3 | 62 | UP | 63~74 |
| 4 | 68 | UP | 69~74 |
| 5 | 71 | UP | 72~74 |
| 6 | 73 | 정답 | - |
6번 만에 맞힙니다. 후보는 100개에서 50개, 24개, 12개, 6개, 3개로 줄었습니다.
예시 2: 정답이 8일 때(최악 횟수에 걸리는 경우)
| 회차 | 입력 | 힌트 | 남은 후보 |
|---|---|---|---|
| 1 | 50 | DOWN | 1~49 |
| 2 | 25 | DOWN | 1~24 |
| 3 | 12 | DOWN | 1~11 |
| 4 | 6 | UP | 7~11 |
| 5 | 9 | DOWN | 7~8 |
| 6 | 7 | UP | 8~8 |
| 7 | 8 | 정답 | - |
7번이 걸렸지만 이것이 상한입니다. 중간값이 소수일 때는 내림이든 올림이든 한쪽을 고르면 최악 횟수는 같고, 어느 쪽으로 반올림했느냐에 따라 7번에 걸리는 정답의 종류만 달라집니다.
사용 방법과 요령
- 입력창에 1~100 사이 정수를 넣고 Enter 또는 확인을 누르세요. 소수나 범위 밖의 값은 시도로 세지 않고 안내만 합니다.
- 이미 입력한 숫자를 다시 입력하면 시도로 세지 않고 알려 줍니다.
- 화면의 "남은 후보"는 지금까지의 힌트로 계산한 정답 후보입니다. 이 범위 밖의 숫자를 부르면 정보가 하나도 늘지 않지만 시도는 1회 올라갑니다.
- "다음 추천 숫자"를 켜면 남은 범위의 중간값을 보여 줍니다. 처음에는 끄고 직접 해 본 뒤 기록을 비교해 보세요.
흔한 실수와 한계
- 힌트를 받고 직전 숫자 바로 옆을 부르면 후보가 한두 개밖에 줄지 않습니다. 후보를 절반으로 가르는 숫자가 최선입니다.
- 정답이 사람이 정한 숫자라면 균등하게 분포하지 않을 수 있습니다. 이 경우 무조건 중간값이 평균적으로 최선이라는 보장은 없습니다. 이 페이지의 정답은 컴퓨터가 1~100에서 균등하게 뽑습니다.
- 난수는 브라우저의 Math.random이며 보안용이 아닙니다. 게임에는 충분하지만 비밀번호나 추첨 증빙용으로는 쓰지 마세요.
- 최소 기록은 이 페이지를 열어 둔 동안만 유지됩니다. 서버나 브라우저 저장소에 저장하지 않으며, 새로고침하면 사라지고 다른 기기와 동기화되지도 않습니다.
- 힌트가 UP·DOWN뿐이라 범위를 넓히면 횟수가 느리게 늘어납니다. 1~1000도 최악 10번이면 충분합니다.
이 게임이 응용되는 곳
정렬된 목록에서 값을 찾는 이진 탐색, 버그가 처음 생긴 변경 지점을 찾는 이분 탐색, 숫자 범위를 질문으로 좁히는 스무고개 같은 상황이 모두 같은 구조입니다. 한 번의 질문이 후보를 절반으로 줄이면 질문 20번으로 약 100만 가지(2의 20제곱=1,048,576) 중에서 하나를 가릴 수 있습니다.
시도 횟수별로 가릴 수 있는 후보의 수
힌트 한 번이 후보를 절반으로 가르므로 k번 안에 확실히 맞히려면 후보가 2의 k제곱에서 1을 뺀 개수 이하여야 합니다. 마지막 한 번은 정답을 부르는 시도 자체에 쓰이기 때문입니다. 아래 표를 보면 범위를 두 배로 넓혀도 시도 횟수는 한 번만 늘어난다는 점이 한눈에 보입니다.
| 시도 횟수 k | 확실히 맞힐 수 있는 최대 범위(1~N) |
|---|---|
| 1번 | 1 ~ 1 |
| 2번 | 1 ~ 3 |
| 3번 | 1 ~ 7 |
| 4번 | 1 ~ 15 |
| 5번 | 1 ~ 31 |
| 6번 | 1 ~ 63 |
| 7번 | 1 ~ 127 |
| 8번 | 1 ~ 255 |
| 9번 | 1 ~ 511 |
| 10번 | 1 ~ 1023 |
그래서 "1~100을 5번 안에 맞히라"는 규칙은 어떤 정답이든 보장할 수 없는 규칙이고, "7번 안에"는 항상 가능한 규칙입니다. 친구와 내기를 걸 때 제한 횟수를 정하려면 이 표가 기준이 됩니다.
제한 횟수를 정하면 성공 확률은 얼마인가
정답이 1~100에서 균등하게 뽑히고 매번 중간값(내림)을 부른다고 가정하면, 앞의 분포표에서 k번 이내에 끝나는 정답의 개수를 누적한 값이 곧 성공 확률(퍼센트)입니다. 즉 이 표는 가장 잘 두었을 때의 상한이며, 실제 사람의 성공률은 이보다 낮을 수 있습니다.
| 제한 횟수 | 끝나는 정답 개수(누적) | 최선 전략의 성공 확률 |
|---|---|---|
| 1번 이내 | 1개 | 1% |
| 2번 이내 | 3개 | 3% |
| 3번 이내 | 7개 | 7% |
| 4번 이내 | 15개 | 15% |
| 5번 이내 | 31개 | 31% |
| 6번 이내 | 63개 | 63% |
| 7번 이내 | 100개 | 100% |
예를 들어 6번 제한이면 최선을 다해도 63%만 성공하고 나머지 37%는 운이 나빠 실패합니다. 게임 규칙을 새로 만들 때 한 판에 이길 확률을 이 수치로 가늠해 난이도를 조절할 수 있습니다.
첫 추측은 꼭 50이어야 할까
중간값이 이론상 가장 균형 잡힌 선택이지만, 최악의 횟수만 놓고 보면 50 하나만 정답은 아닙니다. 첫 추측 뒤 양쪽에 남는 후보 수가 각각 63개 이하이면, 이후 최선으로 두었을 때 7번 안에 끝낼 수 있습니다. 아래 표는 첫 추측별 최악 횟수를 계산한 것입니다.
| 첫 추측 | 이후 최선으로 둘 때의 최악 시도 수 |
|---|---|
| 1 | 8번 |
| 10 | 8번 |
| 25 | 8번 |
| 37 | 7번 |
| 40 | 7번 |
| 50 | 7번 |
| 64 | 7번 |
| 75 | 8번 |
| 90 | 8번 |
| 100 | 8번 |
7번이 보장되는 첫 추측은 37부터 64까지 28개입니다. 반대로 1이나 100처럼 가장자리를 부르면 한쪽에 99개가 남아 최악이 8번으로 늘어납니다. 다만 평균은 중간값 근처일수록 좋으므로, 기록을 줄이려는 목적이라면 50 전후를 쓰는 편이 낫습니다.
상황별 활용 시나리오
- 가족 게임 시간: 한 사람이 1~100 중 숫자를 종이에 적고 나머지가 번갈아 부르는 방식입니다. 출제자는 정직하게 UP·DOWN만 말해야 합니다. 중간값 전략을 아는 사람이 한 명이라도 있으면 7번 제한은 사실상 항상 성공하므로, 승부가 되게 하려면 제한을 6번이나 5번으로 낮추세요.
- 코딩 수업의 이진 탐색 도입: 아이들에게 먼저 이 게임을 시키고 남은 후보가 몇 개인지 화면의 값을 눈으로 보게 한 뒤, 같은 과정을 배열 탐색으로 옮겨 설명하면 100개 원소를 최대 7번 비교로 찾는다는 사실이 직관적으로 이해됩니다. 화면의 "남은 후보" 범위가 탐색 범위의 시작과 끝에 해당합니다.
- 변경 이력에서 문제 시점 찾기: 정상이던 버전과 문제가 있는 버전 사이에 변경이 약 100개 있을 때, 가운데 지점을 검사해 정상이면 뒤쪽, 문제가 있으면 앞쪽으로 좁히는 방식이 같은 구조입니다. Git의 bisect 같은 기능이 이 원리를 쓰는 것으로 알려져 있으며, 한 번의 검사가 오래 걸릴수록 횟수를 줄이는 이득이 큽니다.
- 자기 기록 갱신 연습: 처음 몇 판은 추천 숫자를 끄고 직관으로 해 본 뒤 평균을 구하고, 이후 추천 숫자를 켜고 같은 판 수를 해서 비교해 보세요. 중간값 전략의 이론 평균(1~100에서 5.8회)과 자신의 평균 차이가 습관이 얼마나 나아졌는지 보여 줍니다.
화면에서 실제로 일어나는 일(코드 기준 동작)
- 정답은 새 게임을 시작할 때 1~100에서 균등하게 하나 뽑히며, 도중에 바뀌지 않습니다.
- 입력이 비어 있으면 아무 일도 일어나지 않고, 소수·0·101 이상·음수는 시도로 세지 않는다는 안내만 표시됩니다.
- 이미 부른 숫자를 다시 부르면 시도 횟수가 오르지 않습니다. 하지만 남은 후보 밖의 새 숫자를 부르면 시도는 1회 오르고 후보 범위는 그대로입니다. 이것이 가장 아까운 실수입니다.
- 정답을 맞히면 입력창과 확인 버튼이 잠기고 남은 후보가 정답 하나로 표시됩니다. 다시 하려면 "새 숫자"를 눌러야 합니다.
- 게임 도중에 "새 숫자"를 누르면 그 판의 시도 횟수는 최소 기록에 반영되지 않고 버려집니다.
- 효과음은 sfx.js로 재생되고, 시도 기록이나 입력값은 어디에도 전송되지 않습니다.
결과를 해석하고 다음 판에 반영하는 법
한 판이 끝나면 기록 칩의 색과 화살표 순서를 보면서 어디서 후보가 덜 줄었는지 되짚어 보세요. UP 칩이 연속으로 이어졌다면 매번 이전 숫자에서 조금만 올린 것이고, 남은 범위 바깥을 부른 흔적이 있다면 범위 표시를 확인하지 않은 것입니다. 7번 안에 맞혔다면 정상 범위이고, 8번 이상이면 최소 한 번은 중간값에서 벗어난 것입니다. 5번 이하로 끝났다면 전략보다 운이 좋았던 판일 가능성이 큽니다. 앞의 누적 표에서 5번 이내에 끝나는 정답은 100개 중 31개뿐입니다.
자주 묻는 질문
1~100에서 최대 몇 번이면 반드시 맞힐 수 있나요?
매번 남은 범위의 가운데를 부르면 7번이면 충분합니다. 2의 7제곱이 128이어서 최대 127개 후보까지 7번에 가릴 수 있고 100은 그 안에 들어옵니다.
같은 숫자를 여러 번 입력해도 되나요?
이미 입력한 숫자를 다시 입력하면 같은 힌트만 반복되므로 시도 횟수에 넣지 않고 안내만 합니다. 기록 칩을 보고 새 숫자를 입력하세요.
최소 기록은 어떻게 계산되나요?
정답을 맞히기까지 걸린 시도 횟수 중 가장 적은 값을 이 페이지를 연 동안만 보관합니다. 새로고침하면 초기화됩니다.
중간값이 소수일 때는 어느 쪽으로 반올림하나요?
어느 쪽이든 최악의 시도 횟수는 같습니다. 이 페이지의 추천 숫자는 내림을 사용합니다. 예를 들어 1~100이면 50, 51~100이면 75입니다.
컴퓨터가 정답을 바꾸지는 않나요?
정답은 새 게임을 시작할 때 한 번 정해지고 바뀌지 않으며, 입력한 숫자와 비교한 결과만 힌트로 보여 줍니다.
1번에 맞히는 경우는 얼마나 드문가요?
정답이 균등 무작위이고 첫 추측이 50이라면 1번에 맞힐 확률은 100분의 1입니다. 분포표에서도 1번에 끝나는 정답은 1개뿐이고, 2번에 끝나는 정답은 2개입니다.
범위가 1~1000이면 몇 번이면 충분한가요?
2의 10제곱이 1024이므로 최대 1023개까지 10번에 가릴 수 있어 1~1000도 10번이면 충분합니다. 이 페이지의 정답 범위는 1~100으로 고정이며, 표의 1000행은 설명을 위한 계산값입니다.
추천 숫자를 따라 하면 항상 최선인가요?
정답이 균등하게 뽑히는 이 게임에서는 최악 횟수와 평균 횟수 모두 가장 좋은 선택입니다. 다만 사람이 정한 숫자를 맞히는 상황에서는 사람들이 즐겨 고르는 숫자의 쏠림을 알면 다르게 시작하는 것이 유리할 수도 있습니다.
틀린 판의 기록도 남나요?
이 게임에는 실패 개념이 없어 정답을 맞힐 때까지 계속할 수 있습니다. 최소 기록도 정답을 맞힌 판만 반영하며, 새로고침하면 사라집니다.