정렬과 탐색 문제
개념마다 확인(뜻을 맞게 알았나) → 추적(손으로 한 단계씩) → 응용(처음 보는 상황) 순서로 푼다. 풀이 보기를 누르기 전에 종이에 먼저 적어 보자.
버블 정렬
확인
배열 [3, 6, 2, 5, 1]에 버블 정렬을 한 바퀴 돌렸더니 아래처럼 됐다. 한 바퀴가 끝날 때마다 반드시 보장되는 것은 무엇인가? 그리고 2·5·1은 왜 아직 정렬되지 않았는가?
풀이 보기
남은 값 중 가장 큰 값이 남은 구간의 오른쪽 끝에 자리 잡는다. 가장 큰 값은 어느 이웃과 비교해도 크므로, 한 번 만나면 매번 바뀌며 끝까지 밀려간다. 그래서 바퀴마다 확정된 칸이 하나씩 늘고, 다음 바퀴는 한 칸 짧게 돈다.
나머지 값은 한 바퀴에 왼쪽으로 많아야 한 칸만 간다. 왼쪽 이웃이 자기보다 클 때 한 번 바뀌고, 그 뒤로는 비교가 이미 지나갔기 때문이다. 맨 끝의 1이 제자리(0번 칸)까지 가려면 네 바퀴가 걸린다. 버블 정렬이 느린 까닭이 이것이다.
추적
[4, 2, 5, 1, 3]을 버블 정렬한다. 첫 바퀴가 끝난 뒤의 배열을 적고, 정렬이 끝날 때까지 두 칸을 바꾸는 일이 모두 몇 번 일어나는지 세어 보라.
풀이 보기
첫 바퀴 뒤는 [2, 4, 1, 3, 5]이고, 바꾸기는 모두 6번이다. 아래 단계 그림으로 한 칸씩 확인해 보자.
정렬 전. 이웃한 두 칸을 왼쪽부터 비교해 나간다.
세지 않고 바로 아는 방법도 있다. 버블 정렬의 바꾸기 한 번은 순서가 뒤집힌 쌍(앞이 더 큰 쌍, 역순 쌍) 딱 하나를 바로잡는다. 그래서 바꾸기 횟수는 처음 배열의 역순 쌍 수와 같다. (4,2), (4,1), (4,3), (2,1), (5,1), (5,3)으로 6개다.
응용
거의 정렬된 배열 [1, 2, 3, 4, 6, 5]가 있다. "한 바퀴 동안 한 번도 바꾸지 않으면 멈춘다"는 조기 종료가 있을 때와 없을 때, 비교는 각각 몇 번 하는가? 이 결과로 버블 정렬의 최선 복잡도를 설명해 보라.
풀이 보기
조기 종료가 있으면 9번이다. 첫 바퀴에서 5번 비교하며 6과 5를 바꾸고, 둘째 바퀴에서 4번 비교하는 동안 한 번도 바꾸지 않아 멈춘다. 없으면 15번(5 + 4 + 3 + 2 + 1)을 다 한다.
정렬 전. 이웃한 두 칸을 왼쪽부터 비교해 나간다.
완전히 정렬된 입력이면 첫 바퀴의 n-1번 비교만으로 끝나므로 최선은 O(n)이다. 조기 종료가 없으면 입력과 상관없이 늘 n(n-1)/2번 비교해 최선도 O(n²)이 된다. 같은 알고리즘이라도 멈추는 조건 하나가 최선 복잡도를 바꾼다.
선택·삽입 정렬
확인
[5, 3, 6, 1, 4, 2]에 선택 정렬과 삽입 정렬을 각각 두 바퀴씩 돌렸더니 아래처럼 됐다. 두 결과 모두 왼쪽 몇 칸이 정렬돼 있다. 그런데 앞으로 값이 바뀌지 않는다고 확정된 칸은 어느 쪽에 있는가?
풀이 보기
선택 정렬의 왼쪽 두 칸(1, 2)만 확정이다. 선택 정렬은 남은 칸 전체에서 가장 작은 값을 골라 붙이니, 왼쪽 k칸은 배열 전체에서 가장 작은 k개이고 다시는 움직이지 않는다.
삽입 정렬의 왼쪽 세 칸 [3, 5, 6]은 입력의 앞 세 값을 정렬했을 뿐이다. 뒤에서 1, 4, 2가 들어올 때마다 이 값들은 오른쪽으로 밀려난다. 선택 정렬은 자리를 먼저 정하고, 삽입 정렬은 값을 먼저 정한다는 차이가 여기서 드러난다.
추적
[5, 2, 4, 6, 1, 3]을 삽입 정렬한다. 값 1을 꺼내 끼우기 직전의 배열을 적고, 정렬이 끝날 때까지 큰 값을 오른쪽으로 한 칸 미는 일이 모두 몇 번 일어나는지 세어 보라.
풀이 보기
1을 꺼내기 직전은 [2, 4, 5, 6, 1, 3]이고, 미는 일은 모두 9번이다. 1을 끼울 때 네 번(6, 5, 4, 2), 3을 끼울 때 세 번(6, 5, 4) 밀어 둘만으로 일곱 번이다.
정렬 전. 첫 칸 하나는 그 자체로 정렬된 묶음이다.
미는 한 번은 순서가 뒤집힌 쌍(역순 쌍) 하나를 바로잡는다. 그래서 미는 횟수는 입력의 역순 쌍 수와 같다. (5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3)으로 9개다. 버블 정렬의 바꾸기 횟수와 같은 수다.
응용
값을 한 번 옮겨 쓰는 비용이 비교 한 번보다 훨씬 비싼 저장 장치가 있다. 거꾸로 정렬된 [6, 5, 4, 3, 2, 1]을 정렬할 때 선택 정렬의 두 칸 바꾸기 횟수와 삽입 정렬의 미는 횟수를 각각 구하고, 이 장치에서는 어느 쪽이 나은지 답하라.
풀이 보기
선택 정렬은 바꾸기 3번, 삽입 정렬은 밀기 15번이니 이 장치에서는 선택 정렬이 낫다. 비교는 둘 다 15번(6×5/2)이다.
정렬 전. 남은 칸을 모두 훑어 가장 작은 값을 찾고, 남은 구간의 맨 앞으로 보낸다.
선택 정렬은 바퀴마다 많아야 한 번 바꾸므로 바꾸기가 n-1번을 넘지 않는다. 이 입력에서는 바꿀 때마다 양 끝 두 값이 함께 제자리에 가서 세 번이면 끝난다. 삽입 정렬의 밀기는 역순 쌍 수(여기서는 모든 쌍, 15개)만큼이라 최악이다.
병합 정렬
확인
정렬된 두 조각 [1, 4, 7, 8]과 [2, 3, 9]를 병합한다. 두 조각의 맨 앞끼리 비교하는 일은 모두 몇 번 일어나는가? 비교가 7번(값의 개수)보다 적은 까닭도 설명해 보라.
풀이 보기
6번이다. 1·2, 4·2, 4·3, 4·9, 7·9, 8·9를 비교해 1, 2, 3, 4, 7, 8을 차례로 꺼낸다. 그러면 왼쪽 조각이 비어서, 남은 9는 비교 없이 그대로 붙인다.
한 조각이 먼저 바닥나면 다른 조각의 나머지는 이미 정렬돼 있으니 비교할 필요가 없다. 그래서 길이 a, b인 두 조각을 합치는 비교는 많아야 a + b - 1번, 적게는 min(a, b)번이다.
추적
[5, 2, 7, 1, 6, 3, 8, 4]를 병합 정렬한다. 마지막 병합 직전의 두 조각은 무엇인가? 그리고 나누는 줄과 합치는 줄은 각각 몇 줄인가?
풀이 보기
마지막 병합 직전의 두 조각은 [1, 2, 5, 7]과 [3, 4, 6, 8]이다. 입력 줄 아래로 나누는 줄이 3줄(네 칸, 두 칸, 한 칸), 합치는 줄이 3줄(두 칸, 네 칸, 여덟 칸)이다.
정렬 전. 배열 전체가 한 조각이다.
n = 8 = 2³이라 나누기도 합치기도 log₂ 8 = 3단계다. 합치는 줄마다 여덟 값이 모두 한 번씩 결과로 옮겨지니 줄마다 일이 n이고, 전체는 n log₂ n에 비례한다.
응용
여덟 칸 배열을 병합 정렬할 때 비교 횟수를 센다. 이미 정렬된 [1, 2, 3, 4, 5, 6, 7, 8], 거꾸로 된 [8, 7, 6, 5, 4, 3, 2, 1], 섞인 [1, 3, 2, 7, 4, 6, 5, 8]은 각각 몇 번인가? 삽입 정렬과 견주어 무엇을 알 수 있는가?
풀이 보기
정렬됨 12번, 거꾸로 12번, 섞임 17번이다. 17번은 여덟 칸에서 나올 수 있는 최대이고, 12번이 최소다.
칸은 차례로 두 칸 병합 네 번, 네 칸 병합 두 번, 여덟 칸 병합 한 번의 비교 수와 합계다. 정렬된 입력은 매번 왼쪽 조각이 먼저 바닥나서 조각 길이만큼만 비교하고, 거꾸로 된 입력은 오른쪽 조각이 먼저 바닥나 똑같이 적다.
어떤 입력이든 12~17번 사이라 병합 정렬은 입력 순서에 거의 영향을 받지 않는다. 삽입 정렬은 정렬된 입력에 7번, 거꾸로 된 입력에 28번 비교하니 차이가 훨씬 크다. 최악이 보장되는 대신 "거의 정렬된 입력이면 빨라지는" 이점도 없는 셈이고, Timsort가 이미 정렬된 구간(run)을 따로 찾는 까닭이 이것이다.
퀵 정렬
확인
[7, 2, 9, 4, 3, 6]을 로무토 분할(맨 끝 6이 피벗)로 한 번 갈랐더니 아래처럼 됐다. 이 결과에서 보장되는 것과 보장되지 않는 것을 하나씩 들어 보라.
풀이 보기
보장되는 것: 피벗 6은 최종 자리(3번 칸)에 있고, 왼쪽은 모두 6보다 작고 오른쪽은 모두 6 이상이다. 보장되지 않는 것: 양쪽 안의 순서다. 왼쪽 [2, 4, 3]과 오른쪽 [9, 7]은 아직 정렬되지 않았다.
6보다 작은 값이 정확히 세 개(2, 4, 3)이니 정렬이 끝나도 6은 3번 칸에 있어야 한다. 그래서 피벗은 한 번 놓이면 다시 움직이지 않고, 양쪽 구간을 서로 상관없이 따로 정렬할 수 있다. 병합 정렬과 달리 합치는 단계가 필요 없는 까닭이다.
추적
[5, 3, 8, 1, 9, 2, 7]을 로무토 분할 퀵 정렬로 정렬한다. 첫 분할이 끝난 뒤의 배열을 적고, 피벗이 되는 값을 순서대로 모두 적어 보라.
풀이 보기
첫 분할 뒤는 [5, 3, 1, 2, 7, 8, 9]이고 7이 4번 칸에 선다. 피벗은 7, 2, 3, 9 순서다. 한 칸짜리 구간(1, 5, 8)은 분할 없이 바로 확정된다.
정렬 전. 구간의 맨 끝 값을 피벗(pivot)으로 삼아 구간을 둘로 가른다.
첫 분할에서 5와 3은 이미 왼쪽 묶음 자리라 바꾸지 않고, 1과 2가 i 칸과 바뀌어 왼쪽으로 온다. 왼쪽 구간 [5, 3, 1, 2]의 피벗 2는 1 하나만 작아 1번 칸에 서고, 남은 [5, 3]은 피벗 3으로 한 번 더 갈린다.
응용
이미 정렬된 [1, 2, 3, 4, 5, 6]을 맨 끝 피벗 퀵 정렬로 정렬한다. 재귀는 몇 단계 깊이까지 내려가고, 피벗과의 비교는 모두 몇 번 하는가? 같은 일이 생기지 않게 하려면 피벗을 어떻게 고르면 좋은가?
풀이 보기
깊이 5(0부터 세어), 비교 15번이다. 피벗이 늘 구간에서 가장 큰 값이라 분할할 때마다 피벗 하나만 떨어져 나가고, 비교는 5 + 4 + 3 + 2 + 1 = n(n-1)/2번이다.
무작위로 고르거나 처음·가운데·끝 세 값의 중앙값을 피벗으로 쓰면 된다. 이 입력에서 세 값 1, 3(또는 4), 6의 중앙값은 가운데 값이라 구간이 반씩 갈린다. 공격자가 입력을 고를 수 있는 서버라면 무작위 피벗이 더 안전하다.
응용
모든 값이 같은 [3, 3, 3, 3, 3]을 같은 로무토 분할(피벗보다 작은 값만 왼쪽으로)로 정렬하면 비교는 몇 번인가? 이미 정렬된 배열도 아닌데 왜 그렇게 되는가?
풀이 보기
10번(4 + 3 + 2 + 1), 최악과 같다. 피벗보다 작은 값이 하나도 없어 피벗이 늘 구간의 맨 앞(i = 시작 칸)에 서고, 나머지가 모두 오른쪽 구간으로 넘어가 구간이 한 칸씩만 준다.
같은 값이 많은 데이터(성별, 등급 같은 열)에서 흔히 생긴다. 작다·같다·크다 세 갈래로 가르면(3-way partition) 첫 분할에서 같은 값 다섯 개가 모두 가운데 묶음으로 확정되어 더 다룰 구간이 없다.
힙 정렬
확인
두 배열 A, B를 완전 이진 트리로 볼 때(i번 칸의 자식은 2i+1, 2i+2번 칸), 최대 힙인 것은 어느 쪽인가? 아닌 쪽은 어디가 어긋났는가?
풀이 보기
A는 최대 힙이고, B는 아니다. B의 5번 칸 값 6의 부모는 (5-1)/2 = 2번 칸의 5라서, 부모가 자식보다 작다.
최대 힙은 모든 부모가 두 자식 이상이기만 하면 된다. 형제끼리나 다른 가지끼리의 순서는 상관없다. A에서 7(1번 칸)이 8(2번 칸)보다 작아도 서로 부모·자식이 아니니 문제가 없다. 그래서 힙은 정렬된 배열보다 약한 조건이고, 그만큼 O(n)에 만들 수 있다.
추적
[4, 10, 3, 5, 1, 8, 7]로 힙 정렬을 한다. 최대 힙을 다 만든 직후의 배열과, 첫 최댓값을 끝으로 보내고 힙을 다시 맞춘 직후의 배열을 적어 보라.
풀이 보기
힙을 만든 직후는 [10, 5, 8, 4, 1, 3, 7], 첫 꺼내기 뒤는 [8, 5, 7, 4, 1, 3, 10]이다(10은 6번 칸에 확정).
정렬 전. 배열을 완전 이진 트리로 본다: i번 칸의 자식은 2i+1, 2i+2번 칸이다.
힙 만들기는 2번 칸(3)에서 시작해 더 큰 자식 8과 바꾸고, 1번 칸(10)은 이미 자식보다 커서 그대로 둔다. 0번 칸의 4는 10과, 이어서 5와 바뀌어 3번 칸까지 내려간다. 꺼낼 때는 10과 끝 칸 7을 바꾼 뒤, 위로 올라온 7을 더 큰 자식 8과 바꿔 한 번 내리면 다시 힙이 된다.
응용
값이 하나씩 들어오는 [5, 12, 3, 9, 15, 7, 11]에서 가장 큰 세 값만 남기려 한다. 크기 3인 최소 힙을 두고, 힙이 꽉 찼으면 새 값이 힙의 맨 위(가장 작은 값)보다 클 때만 맨 위를 새 값으로 바꾼다. 다 넣은 뒤 힙에는 무엇이 남는가? 왜 최대 힙이 아니라 최소 힙인가?
풀이 보기
11, 12, 15가 남는다. 최소 힙의 맨 위는 "지금까지의 상위 세 개 중 가장 작은 값", 곧 상위 3위에 들기 위한 문턱이라 새 값과 이것 하나만 비교하면 되기 때문이다.
9가 들어올 때 문턱 3을 밀어내고, 15는 문턱 5를, 11은 문턱 9를 밀어낸다. 7은 문턱 9보다 작아 바로 버린다. 값 n개에 힙 크기가 k라 O(n log k)이고 메모리는 k칸뿐이다. 전체를 정렬하는 O(n log n)보다 빠르고, 끝없이 들어오는 값에도 쓸 수 있다.
계수·기수 정렬
확인
값이 0~4인 [3, 1, 4, 1, 0, 3, 1]을 계수 정렬한다. 값마다의 개수와, 값마다 결과에서 시작할 자리(앞쪽 개수의 누적합)를 구해 보라.
풀이 보기
개수는 [1, 3, 0, 2, 1], 시작 자리는 [0, 1, 4, 4, 6]이다(값 0부터 4까지 차례로). 결과는 [0, 1, 1, 1, 3, 3, 4]다.
시작 자리만 알면 입력을 앞에서부터 읽으며 그 자리에 쓰고 자리를 하나 늘리면 된다. 첫 값 3은 4번 칸, 둘째 값 1은 1번 칸, 넷째 값 1은 2번 칸으로 간다. 같은 값은 들어온 순서대로 자리를 받으니 안정적이다.
추적
[329, 457, 657, 839, 436, 720, 355]를 LSD 기수 정렬한다. 일의 자리로 한 번, 십의 자리로 한 번 정렬한 뒤의 순서를 적어 보라.
풀이 보기
일의 자리 뒤는 [720, 355, 436, 457, 657, 329, 839], 십의 자리 뒤는 [720, 329, 436, 839, 355, 457, 657]이다. 백의 자리까지 하면 [329, 355, 436, 457, 657, 720, 839]로 정렬이 끝난다.
정렬 전. 값끼리 비교하지 않고, 자리 숫자만 보고 통에 나눠 담는다.
십의 자리 2인 통에 720이 329보다 먼저 들어간 것을 보자. 일의 자리 단계에서 720(0)이 329(9)보다 앞에 섰고, 통이 그 순서를 지키기 때문이다. 십의 자리 단계가 끝나면 끝 두 자리(20, 29, 36, 39, 55, 57, 57)가 정렬돼 있다.
응용
[21, 12, 22, 11]을 기수 정렬하는데, 순서를 바꿔 십의 자리부터 안정 정렬하고 그다음 일의 자리로 안정 정렬했다. 결과는 무엇이고 왜 틀리는가?
풀이 보기
결과는 [11, 21, 12, 22]로 틀린다. 마지막 단계가 일의 자리라서, 결과가 일의 자리 순서로 정렬되고 십의 자리는 같은 일의 자리 안에서만 지켜진다.
안정 정렬을 여러 번 하면 마지막에 쓴 키가 가장 중요한 키가 된다. 그래서 LSD는 가장 덜 중요한 자리부터 시작해 가장 중요한 자리로 끝낸다. 높은 자리부터 하려면(MSD) 통 하나하나를 따로 재귀로 정렬해야 한다. 안정성 절의 "여러 키로 정렬하기"와 같은 원리다.
안정성
확인
카드 [3a, 1b, 3c, 2d, 1e]를 숫자만 보고 정렬했더니 두 정렬이 서로 다른 결과를 냈다(글자는 입력 순서다). 어느 쪽이 안정 정렬의 결과인가?
풀이 보기
결과 ㄴ이다. 키 3인 두 카드가 입력에서 a, c 순서였는데 ㄴ은 3a, 3c로 그대로이고, ㄱ은 3c, 3a로 뒤집혔다. 키 1인 1b, 1e는 두 결과 모두 순서가 지켜졌다.
ㄱ은 선택 정렬, ㄴ은 삽입 정렬로 실제로 정렬한 결과다. 불안정한 정렬이 매번 순서를 뒤집는 것은 아니다. 1b, 1e처럼 우연히 지켜질 때도 있어서, 한두 번 돌려 봐서는 안정성을 확인할 수 없고 알고리즘의 성질로 따져야 한다.
추적
키가 같은 2A, 2B와 1C로 된 [2A, 2B, 1C]를 선택 정렬한다. 바퀴마다의 배열을 적고, 2A와 2B의 순서가 언제 왜 뒤집히는지 설명해 보라.
풀이 보기
첫 바퀴에 [1C, 2B, 2A]가 되고, 둘째 바퀴는 최솟값 2B가 이미 맨 앞이라 그대로 끝난다. 첫 바퀴에서 최솟값 1C를 맨 앞 칸의 2A와 멀리 떨어진 채로 바꿀 때 2A가 2B를 건너뛰어 뒤로 간다.
이웃끼리만 바꾸는 버블·삽입 정렬은 같은 키를 건너뛰는 일이 없어 안정적이다. 선택·퀵·힙 정렬처럼 멀리 있는 칸과 바꾸는 정렬은 그 사이에 있던 같은 키를 건너뛸 수 있어 불안정하다.
응용
과일 목록 (가격대, 이름)을 "가격대 오름차순, 같은 가격대는 이름 가나다순"으로 늘어놓으려 한다. 정렬 함수는 키 하나만 받고 안정적이다. 어떤 순서로 두 번 정렬하면 되는가? 결과도 적어 보라.
풀이 보기
이름으로 먼저 정렬하고, 그다음 가격대로 안정 정렬한다. 결과는 [1 감, 1 귤, 2 배, 2 사과, 2 포도, 3 자두]다. 중요한 키를 마지막에 쓴다.
순서를 거꾸로 하면 마지막 이름 정렬이 가격대 순서를 흩뜨려 [1 감, 1 귤, 2 배, 2 사과, 3 자두, 2 포도]처럼 이름순이 된다. 가격대로만 한 번 정렬하면 같은 가격대가 입력 순서(2 사과, 2 배, 2 포도)로 남는다. Python에서는 키를 튜플 (가격대, 이름)로 주어 한 번에 정렬해도 같은 결과가 나온다.
이진 탐색과 lower/upper bound
확인
정렬된 [2, 4, 4, 4, 7, 9]에서 lower_bound(4), upper_bound(4), lower_bound(5), upper_bound(10), lower_bound(1)을 구해 보라. 답은 칸 위치이고, 해당하는 칸이 없으면 배열 길이 6이다.
풀이 보기
차례로 1, 4, 4, 6, 0이다. lower_bound(4)는 4 이상인 첫 칸(1번), upper_bound(4)는 4보다 큰 첫 칸(4번, 값 7)이다. 5는 배열에 없지만 5 이상인 첫 칸은 7이 있는 4번이다. 10보다 큰 값은 없어 6, 1 이상인 첫 칸은 맨 앞 0번이다.
upper_bound(4) - lower_bound(4) = 3이 4의 개수다. lower_bound(5) = upper_bound(5) = 4처럼 두 경계가 같으면 그 값은 없고, 그 위치가 정렬을 깨지 않고 5를 넣을 자리다.
추적
[1, 3, 4, 7, 7, 9, 12, 15]에서 7의 lower bound와 upper bound를 이진 탐색으로 찾는다. 각각 가운데 칸을 몇 번 보는지, 그리고 7이 몇 개인지 답하라.
풀이 보기
lower bound는 3번 칸, upper bound는 5번 칸이고, 둘 다 가운데 칸을 3번 본다. 7은 5 - 3 = 2개다.
lower — 7 이상인 첫 칸을 찾는다. 답은 늘 [lo, hi) 안에 있다.
첫 가운데 칸(4번)의 값이 7이다. lower bound는 "7 이상"이니 답이 여기거나 왼쪽이라 hi = 4로, upper bound는 "7보다 큰" 칸이 아니니 오른쪽으로 lo = 5로 간다. 길이 8이면 log₂ 8 = 3번이면 구간이 한 칸도 남지 않는다.
추적
같은 배열 [1, 3, 4, 7, 7, 9, 12, 15]에서 배열에 없는 8의 lower bound와 upper bound를 찾으면 무엇이 나오는가? 그 결과로 무엇을 알 수 있는가?
풀이 보기
둘 다 5번 칸이다. 두 경계가 같으니 8은 0개이고, 5번 칸(9 앞)이 정렬을 유지한 채 8을 넣을 자리다.
lower — 8 이상인 첫 칸을 찾는다. 답은 늘 [lo, hi) 안에 있다.
"값이 있나?"만 묻는 이진 탐색은 없으면 -1이나 None을 돌려주고 끝나지만, 경계 탐색은 없을 때도 쓸모 있는 답(넣을 자리)을 준다. Python의 bisect.insort가 bisect_right로 자리를 찾아 넣는 이유다.
응용
무게 [3, 2, 2, 4, 1, 4]인 짐을 이 순서대로 3일 동안 나른다. 하루에 싣는 무게의 합은 트럭 용량을 넘을 수 없다. 필요한 최소 용량을 이진 탐색으로 찾으려면 무엇을 탐색하는가? 답은 얼마인가?
풀이 보기
최소 용량은 6이다. 배열이 아니라 "용량 c면 3일 안에 되는가?"라는 판정의 경계를 탐색한다. c가 커지면 판정은 거짓에서 참으로 한 번만 바뀌고 되돌아가지 않으니(단조성), 참이 되는 첫 c가 곧 lower bound다.
탐색 범위는 가장 무거운 짐(4, 이보다 작으면 실을 수 없다)부터 전체 합(16, 하루에 다 싣는다)까지다. 판정 한 번에 짐을 한 번 훑으니 O(n), 이진 탐색이 O(log(합))번이라 전체 O(n log(합))이다. 용량 6이면 [3, 2] [2, 4] [1, 4]로 딱 3일이다.
응용
"x 이하인 마지막 칸"을 찾으려고 닫힌 구간 [lo, hi]로 아래처럼 짰다. 배열 [1, 3]에서 x = 3을 찾으면 어떻게 되는가? 어떻게 고치면 되는가?
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] <= x: lo = mid
else: hi = mid - 1
return lo풀이 보기
끝나지 않는다. mid = (0 + 1) // 2 = 0이고 a[0] = 1 ≤ 3이라 lo = mid = 0, 구간이 그대로라 같은 일이 영원히 되풀이된다. 고치려면 mid = (lo + hi + 1) // 2로 가운데를 위쪽으로 올린다.
lo = mid로 옮기는 분기가 있으면 mid가 lo와 같을 때 구간이 줄지 않는다. 구간이 두 칸 남았을 때 아래로 내림한 mid는 늘 lo다. 노트의 반열린 [lo, hi) 꼴은 lo = mid + 1과 hi = mid만 써서 이 문제가 생기지 않는다. 같은 답을 upper_bound(x) - 1로 구하는 편이 실수가 적다.