더 나아가기 문제
개념마다 확인(뜻을 맞게 알았나) → 추적(손으로 한 단계씩) → 응용(처음 보는 상황) 순서로 푼다. 풀이 보기를 누르기 전에 종이에 먼저 적어 보자.
LRU 캐시
확인
칸이 3개인 LRU 캐시의 리스트가 앞(가장 최근)부터 C, B, A다. 여기에 put(D)를 하면 무엇이 빠지는가? 그리고 노드에 값뿐 아니라 키까지 적어 두는 이유는 무엇인가?
풀이 보기
A가 빠지고 리스트는 D, C, B가 된다. tail 바로 앞 노드가 가장 오래 안 쓴 것이다.
내보낼 때는 리스트에서 노드를 떼는 것으로 끝나지 않고 맵에서도 지워야 한다. 그런데 손에 든 것은 tail 앞 노드뿐이라, 그 노드가 어떤 키였는지 알아야 맵에서 O(1)에 지울 수 있다. 키가 없으면 맵 전체를 뒤져야 해서 O(n)이 된다.
추적
칸이 2개인 LRU 캐시에 아래 요청을 차례로 보낸다. get이 적중한 횟수와 마지막 리스트 순서, 내보낸 키를 차례로 적어라(get이 실패하면 캐시는 바뀌지 않는다).
풀이 보기
적중 2번(get A, get C), 내보낸 키는 B → A, 마지막 리스트는 C, D다. 세 번째 요청 get(A)가 A를 앞으로 올렸기 때문에 put(C)에서는 B가 빠진다. 그래서 get(B)는 실패한다.
빈 캐시. 칸은 2개다. 리스트 앞이 가장 최근에 쓴 것, 뒤가 가장 오래 안 쓴 것이다.
응용
칸이 3개인 LRU 캐시가 A, B, C, D, A, B, C, D 순서로 반복 접근을 받는다. 없으면 원본에서 읽어 put한다. 적중은 몇 번인가? 칸을 4개로 늘리면 어떻게 되는가?
풀이 보기
칸 3개면 적중 0번, 칸 4개면 둘째 바퀴 네 번이 모두 적중한다. 칸 3개에서는 매번 다음에 쓸 키가 바로 가장 오래 안 쓴 키라서 하필 그것을 내보낸다.
빈 캐시. 칸은 3개다. 리스트 앞이 가장 최근에 쓴 것, 뒤가 가장 오래 안 쓴 것이다.
작업 집합이 칸보다 하나만 커도 LRU는 적중률 0%로 무너진다. 이런 순환·스캔 접근에서는 가장 최근 것을 내보내는 MRU나 무작위 교체가 오히려 낫고, 2Q·ARC 같은 변형은 한 번만 쓰인 것을 따로 두어 이 문제를 줄인다.
스킵 리스트
확인
노드 16개를 넣은 스킵 리스트에서 층을 정하는 동전의 앞면 확률이 1/2이다. k층 이상에 오르는 노드 수의 기댓값을 1층부터 5층까지 구하라. 노드 하나가 갖는 층 수의 기댓값은 얼마인가?
풀이 보기
16, 8, 4, 2, 1개이고, 노드 하나의 기대 층 수는 2다. k층 이상에 오르려면 앞면이 k − 1번 이어져야 하므로 확률이 1/2^(k−1)이고, 16을 곱하면 된다.
기대 노드 수가 1이 되는 층이 log₂ 16 + 1 = 5층이라 층 수는 log n 근처다. 기대 층 수는 1 + 1/2 + 1/4 + … = 2라 포인터는 평균 2n개, 공간은 O(n)이다.
추적
아래 스킵 리스트에서 27을 찾는다. 지나는 노드를 차례로 적고, 오른쪽 이동과 층 내려가기가 각각 몇 번인지 세어라. 맨 아래층만 걸으면 오른쪽 이동은 몇 번인가?
풀이 보기
머리(4층) → 9(3층) → 20(2층) → 27(1층)이고, 오른쪽 이동 2번, 내려가기 3번이다. 층마다 다음 노드 33이 27보다 커서 내려가고, 1층에서 다음 노드가 바로 27이라 찾는다. 맨 아래층만 걸으면 27보다 작은 노드 다섯 개를 지나 오른쪽 이동이 5번이다.
찾는 값: 27. 가장 높은 층의 머리에서 출발한다.
응용
같은 스킵 리스트에 30을 넣는다. 동전을 던져 30의 층 수는 2로 정해졌다. 30을 찾는 경로에서 층마다 마지막으로 머문 노드는 무엇이고, 어느 노드의 몇 층 포인터를 바꿔야 하는가?
풀이 보기
층마다 마지막 노드는 4층 머리, 3층 9, 2층 20, 1층 27이고, 바꿀 포인터는 27의 1층과 20의 2층이다. 30의 층 수가 2라 아래 두 층만 고친다. 30의 1층·2층 포인터는 둘 다 33을 가리키고, 27의 1층과 20의 2층은 30을 가리키게 된다.
찾는 값: 30. 가장 높은 층의 머리에서 출발한다.
넣기는 찾기 한 번에 포인터 몇 개를 바꾸는 것이라 찾기와 같은 평균 O(log n)이다. 균형 트리처럼 회전하거나 다른 노드의 층을 고칠 일이 없다.
HyperLogLog
확인
통이 4개(앞 2비트로 고름)인 HyperLogLog에 해시가 아래 다섯 개인 값을 넣는다(설명을 위해 8비트로 줄였다). 값마다 통 번호와 rank(나머지 6비트에서 첫 1이 나온 자리)를 구하고, 마지막 레지스터 네 개를 적어라.
풀이 보기
(통, rank)는 (1, 3), (3, 1), (1, 4), (0, 2), (3, 6)이고, 레지스터는 [2, 4, 0, 6]이다. rank는 0의 개수 + 1이다. 통마다 가장 큰 rank만 남기므로 통 1은 3과 4 중 4, 통 3은 1과 6 중 6이다. 통 2에는 아무 값도 오지 않아 0이다.
같은 값을 다시 넣으면 해시가 같아 같은 통에 같은 rank가 나오므로 레지스터가 바뀌지 않는다. 중복이 저절로 무시되는 이유다.
추적
통 4개의 레지스터가 [2, 0, 3, 1]이다. 추정식 E = α·m² / Σ 2^(−r)로 원시 추정값을 구하라(m = 4, α = 0.7213 / (1 + 1.079 / m)). 원시 추정값이 2.5m 이하이고 빈 통이 있으면 m·ln(m / 빈 통 수)로 바꾼다. 최종 추정값은 얼마인가?
풀이 보기
원시 추정값은 약 4.85이고, 빈 통 보정으로 최종 추정값은 4·ln 4 ≈ 5.55다.
- Σ 2^(−r) = 1/4 + 1 + 1/8 + 1/2 = 1.875
- α = 0.7213 / (1 + 1.079 / 4) ≈ 0.5681
- 원시 E = 0.5681 × 16 / 1.875 ≈ 4.85
- 4.85 ≤ 2.5 × 4 = 10이고 빈 통이 1개 → 4 · ln(4 / 1) ≈ 5.55
값이 적으면 빈 통이 많아 조화 평균 식이 크게 틀어진다. 그때는 "공을 m개 통에 던졌을 때 빈 통이 이만큼 남으려면 몇 개를 던졌어야 하나"로 세는 linear counting이 더 정확하다.
응용
서버 두 대가 같은 해시로 통 16개짜리 HyperLogLog를 따로 채웠다. 두 서버를 합친 방문자 수를 추정하려면 어떻게 하는가? 합친 레지스터와 추정값(m = 16이면 α = 0.673), 표준 오차를 구하라.
풀이 보기
통마다 큰 값을 골라 합치고, 추정값은 약 61.9명, 표준 오차는 1.04/√16 = 26%다.
Σ 2^(−r) = 2.78125라 E = 0.673 × 256 / 2.78125 ≈ 61.9다. 빈 통이 없어 보정은 하지 않는다. 같은 방문자는 두 서버에서 같은 통에 같은 rank를 내므로, 큰 값을 고르면 한 대가 모든 방문을 본 것과 똑같은 레지스터가 된다. 서버별 추정값(약 36.5와 34.0)을 더하면 겹친 방문자를 두 번 센다.
통 16개는 연습용이라 오차가 크다. Redis처럼 통 16384개를 쓰면 1.04/√16384 ≈ 0.81%다.
P와 NP
확인
부분집합 합 문제: 수 [12, 4, 9, 7, 15, 2]에서 몇 개를 골라 합이 23이 되게 할 수 있는가? 누군가 증거(고른 위치)로 ① 0·2·5번, ② 1·3·4번, ③ 3·3·2번을 건넸다. 각각 받아들이는가?
풀이 보기
①만 받아들인다. ① 12 + 9 + 2 = 23으로 맞다. ② 4 + 7 + 15 = 26이라 틀렸다. ③ 7 + 7 + 9 = 23이지만 3번 원소를 두 번 썼으므로 부분집합이 아니다.
확인은 위치가 겹치지 않고 범위 안인지 보고 많아야 n번 더하면 끝나는 다항 시간이다. "증거를 받으면 빨리 확인할 수 있다"가 NP의 정의이므로, 증거에 대한 규칙(서로 다른 원소)까지 확인기가 빠짐없이 검사해야 한다.
추적
같은 수 [12, 4, 9, 7, 15, 2]에서 합이 23인 부분집합을 모두 시험해 찾는다. 시험하는 부분집합은 몇 개이고, 답은 무엇인가? 수가 60개면 몇 개를 시험해야 하는가?
풀이 보기
2⁶ = 64개를 시험하고, 답은 {12, 4, 7}과 {12, 9, 2} 두 개다. 수가 60개면 2⁶⁰ ≈ 1.15 × 10¹⁸개라, 초당 10억 개를 시험해도 30년 넘게 걸린다.
확인은 n에 비례하는데 이 방법의 풀기는 n이 하나 늘 때마다 두 배가 된다. 수의 크기가 작으면 합을 표로 채우는 동적 계획법(O(n × 목표 합))이 있지만, 목표 합이 입력 길이에 대해 지수적으로 커질 수 있어 다항 시간 풀이는 아니다. 부분집합 합은 NP-완전이다.
응용
정점 덮개 결정 문제: "아래 그래프에 정점 3개 이하로 된 덮개가 있는가?" 누군가 증거로 {1, 2, 4}를 건넸다. 이 증거를 확인하라. 그리고 답이 "있다"인지 "없다"인지 판단하고 근거를 대라.
풀이 보기
증거 {1, 2, 4}는 간선 3–5를 덮지 못해 거절한다. 그리고 크기 3 이하의 덮개는 없다(최소 덮개는 4개).
삼각형은 정점 하나로 세 간선을 다 덮을 수 없어 적어도 두 개가 필요하다. 두 삼각형은 정점을 공유하지 않으니 덮개는 적어도 2 + 2 = 4개다. {0, 1, 3, 4}가 그런 덮개다. 크기 3짜리 부분집합 20개를 모두 시험해도 덮개는 없다.
"있다"는 증거 하나로 빨리 확인되지만, "없다"는 이번처럼 운 좋게 짧은 논증이 있을 때만 쉽게 보인다. 일반적으로 "없다"를 빨리 확인할 증거가 있는지(NP = co-NP인지)도 아직 모른다.
근사 알고리즘
확인
경로 그래프 0–1–2–3–4–5에서 2-근사 알고리즘이 간선 (0, 1), (2, 3), (4, 5)를 골라 정점 여섯 개를 덮개로 냈다. 최적 덮개를 구하지 않고도 최적이 몇 개 이상인지 말할 수 있는가? 그 근거는?
풀이 보기
최적은 3개 이상이다. 고른 세 간선은 끝을 공유하지 않으므로, 어떤 덮개든 간선마다 서로 다른 정점을 하나씩은 넣어야 한다. 그래서 근사 덮개 6개는 최적의 2배를 넘지 않는다.
실제 최적도 3개다({0, 2, 4}나 {1, 3, 4} 등). 이 그래프에서는 근사가 정확히 2배다. 최적값을 모르는 채 하한(고른 간선 수)과 비교해 비율을 보장하는 것이 근사 증명의 틀이다.
추적
2 × 3 격자 그래프의 간선을 (0, 1), (1, 2), (0, 3), (1, 4), (2, 5), (3, 4), (4, 5) 순서로 훑으며 2-근사를 돌린다. 고르는 간선과 덮개를 구하고, 모두 시험해 찾은 최적과 비교하라.
풀이 보기
고른 간선은 (0, 1), (2, 5), (3, 4)이고 덮개는 정점 6개 전부다. 최적은 3개({0, 2, 4})라 비율은 2다. (1, 2)는 1이, (0, 3)·(1, 4)는 0·1이 이미 덮개에 있어 건너뛰고, (4, 5)도 4·5가 들어간 뒤라 건너뛴다.
응용
2-근사의 "2배"는 더 줄일 수 없는 분석인가? 근사 결과가 최적의 정확히 2배가 되는 그래프를 하나 들어 보라. 가운데 정점 0에 잎 다섯 개가 붙은 별 모양 그래프는 어떤가?
풀이 보기
별 모양에서 근사는 {0, 1}(2개), 최적은 {0}(1개)으로 정확히 2배다. 첫 간선 (0, 1)의 양 끝을 넣으면 나머지 간선은 모두 0이 덮는다. 간선 하나뿐인 그래프도 같은 이유로 2배다.
이렇게 비율이 정확히 2가 되는 입력이 있으므로 이 알고리즘의 분석은 더 줄일 수 없다(tight). 정점 덮개 전체로 보면 2보다 확실히 작은 상수 비율을 내는 다항 시간 알고리즘은 아직 아무도 찾지 못했다.