요약

매개변수 탐색과 방정식의 근을 찾는 이분법은 둘 다 양 끝에서 대답이 다른 구간을 쥐고, 가운데를 물어 대답이 바뀌는 쪽 절반만 남긴다. 그래서 대답이 여러 번 바뀌어도 바뀌는 자리 하나는 늘 찾는다. 하지만 그 자리가 가장 작은 답이라는 보장은 대답이 한 번만 바뀔 때만 있다. 정수에서는 이웃한 두 수 사이에 틈이 없어 연속 조건이 필요 없고, 실수에서는 함수가 끊기지 않아야 그 자리가 진짜 근이 된다.

먼저 비교해 보기

표를 펼치기 전에 두 사례의 공통 구조와 대응 관계를 먼저 적어 본다. 왼쪽은 매개변수 탐색 확인 문제 C3의 판정 줄이다. 오른쪽은 정수 0 ~ 4에서 “\(f(x) \ge 0\)인가?”의 대답이 그 줄과 똑같이 나오는 삼차함수다1.

알고리즘: 단조가 아닌 판정 줄 미적분: 근이 셋인 삼차함수
\(x = 0, 1, 2, 3, 4\)에서 \(ok(x)\) = 거짓, 참, 거짓, 거짓, 참 \(f(x) = (x - 0.5)(x - 1.5)(x - 3.3)\), \(f(0) < 0 < f(4)\)
최소형 틀 \([0, 4]\): \(mid = 2\)(거짓) → \(lo = 3\), \(mid = 3\)(거짓) → \(lo = 4\) 이분법 \([0, 4]\): 중점 2(−) → \([2, 4]\), 3(−) → \([3, 4]\), 3.5(+) → \([3, 3.5]\), 3.25(−) → \([3.25, 3.5]\), …
4를 돌려준다. \(ok(3)\)은 거짓, \(ok(4)\)는 참 3.3으로 모인다. \(f(3.3) = 0\)
참인 가장 작은 \(x\)는 1이다 가장 작은 근은 0.5다
대응 관계
알고리즘 수학 공통 구조
판정 함수 \(ok(x)\). \(ok(hi)\)는 참이고, 범위 바로 앞 칸 \(lo - 1\)은 거짓으로 친다. 이 칸이 \(a\) 자리다 연속함수 \(f\), \(f(a) < 0 < f(b)\). \(ok(x)\)를 “\(f(x) \ge 0\)“으로 읽는다 양 끝에서 대답이 다르다
약한 불변식: \(ok(hi)\)는 참이고, \(lo\)가 처음 시작점이 아니면 \(ok(lo - 1)\)은 거짓 남은 구간 \([a_k, b_k]\)에서 \(f(a_k) < 0 \le f(b_k)\) 바뀌는 자리를 품은 구간을 지킨다
\(ok(mid)\)가 거짓이면 \(lo = mid + 1\), 참이면 \(hi = mid\) 중점에서 \(f < 0\)이면 그 중점이 새 \(a\), 아니면 새 \(b\) 구간을 반으로 줄인다. 거짓인 \(mid\)는 범위에서 빠지지만 새 \(lo - 1\)이 되어, 실수 쪽의 새 \(a\)와 같은 자리를 맡는다
범위 크기가 \(m\)이면 판정 많아야 \(\lceil \log_2 m \rceil\)번 \(k\)번 뒤 폭 \((b - a)/2^k\) 한 번에 1비트씩 정확해진다(비율 1/2의 선형 수렴)
끝: \(hi - lo\)는 0 이상의 정수라 유한 번 뒤 \(lo = hi\) 끝: 폭이 0에 한없이 다가가고, 실수에 빈틈이 없어서(완비성) 양 끝이 한 점 \(c\)로 모인다 같은 불변식이 증명을 끝낸다
돌려준 \(r\): \(ok(r - 1)\)은 거짓, \(ok(r)\)은 참 (또는 \(r\)이 범위 시작) 부호가 바뀌는 점 \(c\). \(f\)가 연속이면 \(f(c) = 0\) 대답이 바뀌는 자리
단조(대답이 한 번만 바뀐다)면 \(r\)이 참인 가장 작은 \(x\) \(f\)가 줄지 않으면 \(c\)는 \(f(x) \ge 0\)인 가장 왼쪽 점, 늘기만 하면(순증가) 근이 하나 단조성이 “가장 작은”을 보장한다

그림

위 그림의 네모는 정수 0 ~ 4에서의 판정이다(초록은 참, 주황은 거짓). 아래 보라 막대는 이분법이 반씩 줄여 간 구간이다. 구간은 늘 부호가 바뀌는 자리를 품은 채 오른쪽 근 3.3으로 모이고, 가장 작은 근 0.5는 첫 걸음에 구간 밖으로 빠진다2.

어디까지 같은가

  • 둘 다 부호 1비트만 쓴다. 이분법도 \(f\)의 크기는 보지 않고 부호만 본다. 그래서 정수 칸과 실수 구간에서 코드의 뼈대가 같다. 다른 점은 그 밑에 깔린 값이다. 수학 쪽은 \(f\)가 미분 가능하면 값과 기울기를 써서 뉴턴 방법으로 갈아탈 수 있다. 판정 함수 밑의 값은 토막 수, 사람 수처럼 개수일 때가 많다. 개수는 정수라 계단 모양이다. 매개변수 탐색의 통나무 예에서 토막 수 \(\lfloor 8/L \rfloor + \lfloor 5/L \rfloor + \lfloor 11/L \rfloor\)(\(\lfloor\ \rfloor\)는 소수점 아래를 버린 정수)는 \(L\)을 조금 바꿔도 대개 그대로이고, \(L\)이 4를 막 넘으면 5에서 4로 뛴다. 기울기가 0이거나 없으니 뉴턴 방법은 못 쓰고, 부호만 보는 이분법은 그대로 쓴다.
  • 불변식은 두 겹이다. 매개변수 탐색의 증명이 쓰는 “\(lo\)보다 작은 \(x\)는 모두 거짓”은 강한 불변식이다3. 단조성이 있어야 지켜진다. 이분법의 “양 끝 부호가 다르다”는 끝점만 보는 약한 불변식이다. 위 판정 줄에서 \(lo = 3\)이 되면 \(x = 1\)이 참이라 강한 불변식은 깨진다. 그래도 \(ok(2)\)는 거짓, \(ok(4)\)는 참이라 약한 불변식은 끝까지 남는다. 이분 탐색의 말로 하면, 정렬이 주는 “버린 쪽에 답이 없다”가 강한 쪽이다. 약한 쪽에 연속을 더하면 “남긴 쪽에 근이 있다”가 된다.
  • “가장 작은”은 단조성이 보장한다. 단조가 아닐 때 틀이 돌려주는 바뀌는 자리는 범위 바로 앞 칸을 거짓으로 쳐야 사잇값 정리의 \(f(a) < 0\)과 맞는다. 처음부터 \(ok(lo)\)가 참이면 틀은 범위 시작을 돌려줄 수도 있다. 예: [참, 참, 거짓, 참] → 0. 수학 쪽도 같다. 이분법은 근 하나를 찾을 뿐 가장 작은 근을 약속하지 않는다. 또 \(f\)가 줄지 않는다는 것만으로는 근이 하나라는 보장이 없다. \(f(x) = \min(0, x) + \max(0, x - 1)\)은 \(f(-1) = -1\), \(f(2) = 1\)인데 \([0, 1]\) 전체가 근이다. 이분법은 그중 가장 왼쪽인 0으로 간다. \(f\)가 늘기만 하면(순증가) 근은 딱 하나다.
  • 정수 쪽에는 연속이 필요 없다. 범위 바로 앞 칸이 거짓이고 맨 끝 칸이 참이면, 처음 참이 나오는 칸의 바로 앞은 거짓이다. 그래서 거짓에서 참으로 바뀌는 이웃 쌍이 늘 있다(이산 사잇값 정리). 실수 쪽은 끊긴 점 하나로 무너진다. \(f(x) = 1/x\)를 \([-1, 2]\)에서 돌리면 \(f(-1) < 0 < f(2)\)라서 이분법은 부호가 바뀌는 점 0으로 좁혀 간다. 하지만 \(f\)는 0에서 정의조차 안 되고, 구간 어디에도 근이 없다. 연속이 하는 일은 “부호가 바뀌는 점”을 “근”으로 만드는 것 하나다. \([-1, 1]\)에서는 첫 중점이 0이라 계산이 아예 막힌다.
  • 실수에서는 부동소수점 간격 아래로 좁혀지지 않는다. 컴퓨터의 수는 띄엄띄엄 있다(극한). 값이 \(10^9\) 근처면 이웃한 두 배정밀도 수의 간격이 \(2^{-23} \approx 1.19 \times 10^{-7}\)이다4. 양 끝이 이 간격만큼 붙으면 중점이 \(lo\)나 \(hi\)와 같아져 구간이 더 줄지 않는다. 그래서 답이 \(10^9\) 근처면 while hi - lo > 1e-9는 끝나지 않는다. 정수 쪽에서 lo = mid로 두면 끝나지 않는 것과 같은 자리의 실패다. 실수 답을 “정해진 횟수만큼” 돌리는 까닭이 이것이다.

이 연결로 얻는 것

  • 끝난 뒤 확인으로는 단조성을 모른다. \(ok(hi)\)가 참이면 틀이 돌려준 \(r\)은 단조가 아니어도 “\(ok(r)\)은 참, \(ok(r - 1)\)은 거짓”을 늘 만족한다. 약한 불변식이 끝까지 남기 때문이다. 그래서 끝난 뒤 이 둘을 확인해도 단조가 아닌 판정을 잡아내지 못한다. 단조성은 판정이 왜 한 번만 바뀌는지(예: \(L\)이 커지면 토막 수가 늘지 않는다)로 따로 따져야 한다.
  • 실수 답의 오차를 바로 센다. 처음 범위가 \([lo, hi]\)이면 \(k\)번 뒤 폭은 \((hi - lo)/2^k\)이고, 이 폭이 오차의 확실한 상한이다. 수열의 극한과 e의 “이웃 값의 차가 작으면 멈춘다”와 달리 틀린 곳에 멈추지 않는다. 범위 \(10^9\)를 100번 줄이면 수학으로는 폭이 \(10^9/2^{100} \approx 7.9 \times 10^{-22}\)이다. 실제로 남는 폭은 이 값과 답 근처 부동소수점 간격 중 큰 쪽 정도다. 답이 \(10^9\) 근처면 이웃한 두 수 사이 약 \(1.19 \times 10^{-7}\)에서 멈춘다. 횟수를 정했으니 어느 경우든 루프는 끝난다.
  • 사잇값 정리의 증명. 연속과 사잇값 정리는 증명을 생략한다. 이분법을 루프 불변식으로 읽고 실수의 완비성을 더하면 증명이 된다56.
이분법으로 사잇값 정리 증명하기

\(f\)가 \([a, b]\)에서 연속이고 \(f(a) < 0 < f(b)\)라 하자.

  1. 불변식: \(a_0 = a\), \(b_0 = b\)에서 시작한다. 중점 \(p_k = (a_k + b_k)/2\)에서 \(f(p_k) \ge 0\)이면 \(b_{k+1} = p_k\), 아니면 \(a_{k+1} = p_k\)로 두고, 다른 끝은 그대로 둔다. 그러면 모든 \(k\)에서 \(f(a_k) < 0 \le f(b_k)\)이고 \(b_k - a_k = (b - a)/2^k\)이다. 초기화와 유지는 위의 약한 불변식과 같고, 단조성은 쓰지 않는다.
  2. 한 점으로 모인다: \(a_k\)는 줄지 않고 \(b\)를 넘지 않는다. 단조 수렴 정리에 따라 \(a_k \to c\)인 \(c \in [a, b]\)가 있다. \(b_k = a_k + (b - a)/2^k\)이므로 \(b_k \to c\)이다. 실수의 빈틈없음(완비성)은 이 단계에서 쓰인다.
  3. 근이다: \(f\)가 \(c\)에서 연속이므로 \(f(c) = \lim f(a_k) \le 0\)이고 \(f(c) = \lim f(b_k) \ge 0\)이다. 그래서 \(f(c) = 0\)이다. 연속은 이 단계에서만 쓰인다. ∎

일반적인 사잇값 \(y\)는 \(f(a) < y < f(b)\)이면 \(f - y\)에, \(f(a) > y > f(b)\)이면 \(y - f\)에 같은 논증을 쓴다. 정수 칸에서는 2단계가 “\(hi - lo\)는 정수라 유한 번 만에 \(lo = hi\)“로, 3단계가 “\(ok(lo - 1)\)은 거짓, \(ok(lo)\)는 참”으로 바뀐다. 극한도 연속도 필요 없다.

전이 문제

(컴퓨터 통신) 어떤 경로로 보낼 수 있는 가장 큰 패킷 크기(MTU)를 찾는다. 크기 \(x\)바이트 패킷을 보내면 “끝까지 갔다”와 “못 갔다”만 알 수 있다. MTU는 576 ~ 9000바이트 사이라는 것만 안다7.

  1. 보통은 \(x\)가 MTU 이하면 가고, 넘으면 못 간다. 판정 함수와 틀(최소형·최대형)을 쓰고, 많아야 몇 번 보내면 되는지 구하라.
  2. 경로 중간에 어떤 크기 구간만 버리는 장비가 있어 판정이 단조가 아니라면(576바이트는 여전히 간다), 같은 틀이 돌려준 값에서 무엇은 여전히 맞고 무엇은 틀릴 수 있나? 그런 자리가 반드시 있는 까닭도 말하라.
답
  1. 판정은 \(ok(x)\) = “크기 \(x\)가 끝까지 간다”이고, 줄이 참…참 거짓…거짓이라 최대형이다. \(ok(576)\)이 참인 것은 MTU ≥ 576이라는 전제에서 나온다. 범위 크기는 \(9000 - 576 + 1 = 8425\)이고 \(2^{13} = 8192 < 8425 \le 2^{14}\)라 많아야 14번 보낸다. MTU 값에 따라 14번이 꼭 필요한 경우도 있다.
  2. 최대형 틀은 \(ok(r)\)이 참이고, \(r = 9000\)이거나 \(ok(r + 1)\)이 거짓인 \(r\)을 돌려준다. 곧 “간다”에서 “못 간다”로 바뀌는 자리 하나다. 576바이트는 간다고 했고, MTU ≤ 9000이라 9001바이트는 못 간다. 그래서 줄의 맨 앞은 참이고 맨 끝 바로 다음은 거짓이다. 유한한 줄이니 참에서 거짓으로 바뀌는 이웃 쌍이 반드시 있다. 사잇값 정리의 “양 끝 부호가 다르면 사이에 근이 있다”의 정수판이다. 하지만 그 \(r\)이 MTU라는 보장은 없다. 실제로는 9000바이트까지 가는데 4000 ~ 6000바이트만 버리는 장비가 있으면, 첫 질문 4788이 “못 갔다”라서 틀은 3999를 돌려준다.

확인 문제

C1 판정 줄 [거짓, 참, 거짓, 거짓, 참]에서 최소형 틀이 돌려준 4는 쓸모없는 값인가? 이분법이 근을 찾는 방식과 비교해 말하라.

답: 아니다. \(ok(3)\)은 거짓, \(ok(4)\)는 참이라 4는 거짓에서 참으로 바뀌는 자리 하나다. 이분법도 양 끝 부호만 다르면 근 하나를 찾을 뿐, 가장 작은 근을 약속하지 않는다. 틀린 것은 “참인 가장 작은 값”이라는 해석이고, 그 해석에는 단조성이 필요하다. 흔한 오답은 “단조가 아니니 아무 값이나 나온다”이다.

C2 이분법으로 사잇값 정리를 증명할 때 연속이라는 가정은 어느 단계에서 쓰이나? 정수 칸의 매개변수 탐색에 그 가정이 필요 없는 까닭은?

답: 마지막 단계에서만 쓰인다. 양 끝 \(a_k\), \(b_k\)가 한 점 \(c\)로 모인 뒤 \(f(c) = \lim f(a_k) \le 0\)과 \(f(c) = \lim f(b_k) \ge 0\)을 끌어낼 때다. 정수 칸에서는 \(hi - lo\)가 정수라 유한 번 만에 \(lo = hi\)가 되고, 그때의 이웃 쌍 “\(ok(lo - 1)\) 거짓, \(ok(lo)\) 참”이 곧 답이다. 극한을 취할 일이 없다. 단조성을 꼽으면 틀린다. 단조성은 “가장 작은” 자리를 위한 조건이고, 사잇값 정리에는 쓰이지 않는다.

C3 정렬되지 않은 배열 \(a\)에서 \(a[0] < 0 \le a[n-1]\)이다. \(a[i] < 0 \le a[i+1]\)인 \(i\) 하나를 칸을 약 \(\log_2 n\)번만 보고 찾는 방법을 쓰고, \(a = [-5, 3, -2, -7, 4, -1, 6]\)에 적용하라.

답: \(lo = 0\), \(hi = n - 1\)로 두고 “\(a[lo] < 0 \le a[hi]\)“를 불변식으로 지킨다. \(hi - lo > 1\)인 동안 \(mid = \lfloor (lo + hi)/2 \rfloor\)를 보고, \(a[mid] < 0\)이면 \(lo = mid\), 아니면 \(hi = mid\)로 옮긴다. 끝나면 \(i = lo\)다. 많아야 \(\lceil \log_2(n - 1) \rceil\)칸을 본다. 예: \(lo = 0\), \(hi = 6\) → \(mid = 3\), \(a[3] = -7 < 0\) → \(lo = 3\) → \(mid = 4\), \(a[4] = 4 \ge 0\) → \(hi = 4\). 두 칸만 보고 \(i = 3\)(\(-7 < 0 \le 4\))을 찾는다. 정렬되지 않아도 되는 까닭은 이산 사잇값 정리다. 다만 가장 앞의 \(i = 0\)(\(-5 < 0 \le 3\))은 놓친다.

검증: 비교 표의 두 추적(판정 줄과 삼차함수의 이분법), 길이 1 ~ 12인 모든 참·거짓 줄에서 약한 불변식·돌려준 값의 성질·판정 횟수(최소형·최대형)와 거짓인 \(mid\)가 새 \(lo - 1\)이 되는 것, 강한 불변식이 깨지는 자리, 끝난 뒤 확인이 단조가 아닌 줄 2만 개를 하나도 못 잡음, 토막 수의 계단 모양, \(\min(0, x) + \max(0, x - 1)\)과 \(1/x\)의 이분법, \(10^9\) 근처 간격 \(2^{-23}\)과 끝나지 않는 hi - lo > 1e-9, 100번 뒤 남는 폭, 증명의 불변식, 전이 문제의 14번과 3999, C3의 추적과 무작위 배열 2만 개. 모두 실험으로 확인한 것이고, 사잇값 정리와 이산판의 증명은 본문에 있다 — 39_parametric-search-ivt_verify.py

  1. 비교 표의 삼차함수는 정수 0 ~ 4에서 “f(x) ≥ 0인가?”의 대답이 매개변수 탐색 C3의 판정 줄과 같도록 근 0.5, 1.5, 3.3을 골라 만든 예다. 표의 중점과 부호의 근거: 39_parametric-search-ivt_verify.py. ↩

  2. 39_parametric-search-ivt_plot.py로 그렸고, 정수 0 ~ 4의 판정 줄(거짓, 참, 거짓, 거짓, 참), 이분법 구간 [0, 4] → [2, 4] → [3, 4] → [3, 3.5] → [3.25, 3.5], 60번 뒤 양 끝이 3.3과 \(10^{-12}\) 안으로 붙는다는 것을 같은 코드로 확인했다. ↩

  3. 판정 함수의 경계를 이분 탐색으로 찾는 틀은 Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 3.3 “Binary search”의 Finding the smallest solution. 불변식의 세 단계(초기화·유지·종료)는 Cormen 외, Introduction to Algorithms 3판, 2.1절의 방식을 따랐다. ↩

  4. Python 3 표준 라이브러리 문서, math.ulp(어떤 부동소수점 수와 그다음 수의 간격). math.ulp(1e9)를 계산하면 \(2^{-23}\)이다. ↩

  5. Bartle·Sherbert, Introduction to Real Analysis 3판(Wiley, 2000), 5.3절 “Continuous Functions on Intervals”의 정리 5.3.5 Location of Roots Theorem. 구간을 반씩 나누어 근이 있음을 보이고, 이 증명이 곧 이분법(Bisection Method)이라고 적는다. 사잇값 정리의 진술은 OpenStax, Calculus Volume 1, 2.4절. ↩

  6. 연속과 사잇값 정리 문서에서 생략한 증명이다. Bartle·Sherbert의 이분법 증명을 매개변수 탐색의 불변식 말로 쓴 것이다. Bartle·Sherbert는 중점에서 \(f = 0\)이면 거기서 멈추고, 완비성을 축소 구간 성질(Nested Intervals Property)로 쓴다. 이 문서는 \(f(p_k) \ge 0\)을 오른쪽 끝으로 보내 멈춤 없이 이어 가고, 완비성을 단조 수렴 정리의 형태로 쓴다. ↩

  7. MTU 상황과 4000 ~ 6000바이트를 버리는 장비는 이 문서에서 만든 예다. 수치의 근거: 39_parametric-search-ivt_verify.py(576 ~ 9000의 모든 MTU 값, 무작위로 버리는 구간 300가지). ↩