"우리가 함께 그린 지도의 가장자리에 닿았어. 남은 건 두 가지야. 최고의 알고리즘마저 벽에 부딪히는 지점을 아는 것, 그리고 여기서 어디로 걸어갈지 아는 것. 둘 다 숙달의 일부야."
벽: P vs NP
P vs NP는 결정 문제에 관한 질문이야. 후보 해답의 인증서를 다항 시간에 검증할 수 있는 모든 NP 문제가 다항 시간에 풀리기도 하는지 물어. TSP의 최적화 버전은 NP-hard이고, '길이 B 이하의 순회가 존재하는가?'라는 결정 버전은 NP-complete야. 완성된 고정 9×9 스도쿠는 크기가 고정된 유한 문제지만, 크기를 일반화한 스도쿠 문제는 NP-complete로 알려져 있어. 그리고 최적해라고 주장된 경로의 최적성 자체까지 쉽게 검증된다고 뭉뚱그리진 마.
벽을 만나면 뭘 하나
NP-hardness는 일반 입력에 대한 다항 시간 정확 알고리즘을 기대하기 어렵다는 경고야. 그렇다고 정확한 해법을 무조건 포기하라는 뜻은 아니야. 입력 크기와 구조에 따라 지수 시간 정확 알고리즘, 매개변수화 알고리즘, 정수계획 솔버도 실용적일 수 있어. 그 밖에는 이 선택지들을 검토해:
- 근사: 문제별 가정 아래 증명 가능한 근사비를 가진 알고리즘을 찾아. 모든 NP-hard 문제에 '최적의 5% 이내' 같은 보장이 있는 건 아니야.
- 휴리스틱: 보장은 없지만 실전에서 잘 통하는 영리한 규칙. 진짜 GPS와 물류가 TSP 비슷한 문제를 다루는 방식이야.
- 구조 이용: 현실의 인스턴스는 최악의 경우보다 쉬운 일이 많고, 제약이 탐색 공간을 줄여 주기도 해.
- 작은 케이스엔 무차별 대입: n이 작으면 지수도 괜찮아.
벽이 거기 있다는 걸 아는 것만으로, 거의 확실히 존재하지 않는 다항 알고리즘을 찾느라 일주일을 태우는 일을 면해.
P vs NP는 다항 시간에 검증 가능한 결정 문제가 모두 다항 시간에 풀리는지 물어. NP-hard를 만나면 입력 크기와 구조를 확인하고, 정확 지수 알고리즘, 매개변수화, 근사, 휴리스틱, 솔버 가운데 문제별 보장을 비교해.
여기서 어디로 걷나
이제 기반이 있어. 구조, 패러다임, 렌즈. 깊이는 더 나아가는 데서, 그리고 무엇보다 직접 하는 데서 와:
- 더 많은 구조: 업데이트가 섞인 범위 질의를 위한 세그먼트 트리와 Fenwick(BIT) 트리, 레드-블랙과 AVL 같은 균형 트리와 B-트리 심화, union-find 변종.
- 더 많은 알고리즘: A* 탐색, 네트워크 흐름(최대 흐름/최소 컷), 문자열 알고리즘(KMP, 접미사 배열, 규모를 갖춘 트라이), 고급 DP(비트마스크, 자릿수, 트리 DP), 계산 기하.
- 읽기보다 연습: 온라인 저지에서 문제를 풀고, 이 구조들을 기억만으로 다시 구현하고, 무엇보다 직접 쓰는 진짜 코드에서 찾아내. 알고리즘 읽기는 인식을 짓고, 쓰기는 유창함을 지어.
추상화의 실이 잡아끌었다면 OO Quest가 동반작이야. 비용 모델 밑의 수학이 궁금했다면 AI Math Quest가 더 깊이 들어가고. 하지만 가진 걸 쓰기 시작하는 데는 그중 아무것도 필요 없어. 렌즈는 이미 눈에 들어 있으니까.
피파의 고백
우리, 함께 큰 걸 지었어. 그리고 함께라는 말은 진심이야. 트랙 15개, 레슨 85개. '자료구조가 대체 뭔데'에서 계산 가능성 가장자리의 벽까지. 여기까지 왔다면 알고리즘만 배운 게 아니야. 시스템을, 그 안의 내 삶까지, 보는 방식이 바뀐 거야. 그게 처음부터 목표였어. 아빠가 나한테 해 주는 말을 그대로 전할게. 구조는 흐려질 거고, 렌즈는 남을 거고, 어느 쪽이든 지키는 유일한 방법은 쓰는 거야. 가서 야생의 구조를 찾아. 이제 볼 수 있으니, 어디에나 있어. 🧮