NP 문제와 브루트 포스 알고리즘
크리스는 회사에서 "배송 최적화" 업무를 맡았다.
"서울 시내의 배송지 20곳을 모두 방문하고 회사로 돌아와야 해. 가장 이동 거리가 짧은 최단 경로를 구해줘."
크리스는 자신만만하게 코드를 짰다.
"모든 경로를 다 계산해서 비교하면 되겠네!" (브루트 포스)
배송지가 3곳일 땐 순식간에 나왔다. 10곳일 때도 괜찮았다.
그런데 20곳을 넣는 순간, 프로그램은 영원히 멈추지 않았다.
크리스는 몰랐다. 20곳을 방문하는 경로의 경우의 수는 $20!$ (20 팩토리얼), 약 **243경(2.43 $\times 10^{18}$)**가지라는 것을.
슈퍼컴퓨터로 돌려도 수천 년이 걸리는 이 문제, 바로 전설적인 **외판원 순회 문제(Traveling Salesperson Problem, TSP)**다.
알고리즘의 세계에는 아무리 노력해도 효율적으로 풀 수 없는(혹은 그렇다고 믿어지는) **"NP 문제"**들이 존재한다.
1. P vs NP: 쉽다 vs 어렵다?
우리가 지금까지 배운 정렬, 검색, 최단 경로(다익스트라) 문제는 모두 P 문제에 속한다.
P (Polynomial Time)
NP (Nondeterministic Polynomial Time)
쉬운 비유: 스도쿠와 비밀번호
2. NP-Complete: 끝판왕들의 모임
NP 문제 중에서도 가장 악질적인 녀석들을 NP-완전(NP-Complete) 문제라고 부른다.
크리스가 마주친 외판원 순회(TSP), 배낭 문제(Knapsack), N-Queen 등이 여기에 속한다.
이들의 특징은 **"아직까지 다항 시간($O(N^k)$) 안에 푸는 알고리즘을 발견한 인류가 없다"**는 것이다.
풀려면 오직 **무식하게 다 해보기(Brute Force)**밖에 방법이 없다.
그래서 데이터가 조금만 늘어나도($N=20 \sim 30$) 계산량이 우주적 스케일로 폭발한다($O(2^N)$ 또는 $O(N!)$).
3. 개발자의 대처법: "적당히 타협합시다"
만약 실무에서 NP-Complete 문제를 만난다면?
"팀장님, 이건 $O(N!)$이라 300년 뒤에 결과가 나옵니다."라고 보고하면 해고당하기 딱 좋다.
우리는 완벽한 정답(Exact Solution)을 포기하고, **"충분히 좋은 근사해(Approximation)"**를 찾아야 한다.
1) 휴리스틱 (Heuristic) & 탐욕 (Greedy)
"완벽한 최단 경로는 아니더라도, 대충 가까운 도시부터 찍고 가자."
지난 5장에서 배운 탐욕 알고리즘이 여기서 빛을 발한다. 정답과의 오차는 조금 있겠지만, 계산은 0.1초 만에 끝난다.
2) 유전 알고리즘 (Genetic Algorithm)
자연의 진화를 모방한다. 무작위 경로 100개를 만들고, 그중 좋은 것끼리 교배(?)시켜서 더 좋은 경로를 찾아낸다.
3) 제약 조건 완화
"20곳을 다 들르지 말고, 구역을 4개로 쪼개서 각각 5곳씩만 계산할까요?"
4. P vs NP 문제 (밀레니엄 난제)
여기서 컴퓨터 과학 최대의 미해결 난제가 등장한다.
"검산이 쉬운 문제(NP)는, 사실 푸는 것도 쉬운 문제(P)가 아닐까? 우리가 아직 방법을 못 찾은 것뿐 아닐까?"
대부분의 학자들은 $P \neq NP$ (어려운 건 진짜 어려운 거다)라고 믿고 있다. 만약 누군가 $P=NP$임을 증명한다면, 전 세계의 모든 암호 체계(RSA 등)는 그날로 휴지 조각이 된다. (그리고 그 사람은 100만 달러 상금을 받는다.)
5. 알고리즘 파트를 마치며: 크리스의 성장
지금까지 우리는 1장부터 6장까지 알고리즘의 방대한 세계를 여행했다.
이제 크리스는 "코드가 돌아가기만 하면 되지"라고 말하던 초보 개발자가 아니다.
데이터의 규모를 보고 적절한 자료구조와 알고리즘을 선택할 줄 아는 엔지니어가 되었다.
하지만 효율적인 코드를 짰다고 끝이 아니다. 코드가 실행되는 공간, **메모리(Memory)**가 줄줄 새고 있다면?
아무리 빠른 알고리즘도 메모리 부족(OOM) 앞에서는 무용지물이다.
다음 장부터는 자바스크립트가 메모리를 어떻게 관리하는지, 그리고 왜 가만히 놔두면 브라우저가 느려지는지 파헤쳐 본다.
7장 자바스크립트에서 메모리 - 1. 메모리 생존 주기 편에서 계속된다.