느릴 때 무엇부터 의심하나 - 길 고르기 한 장

이 시리즈는 내비게이션 이야기로 시작했다. 목적지가 같아도 길은 여럿이고, 무엇을 골랐느냐가 걸리는 시간을 정한다는 것. 이제 길을 다 봤으니 언제 어느 길로 가느냐로 닫는다.

다시 내비게이션으로

시작할 때 한 말을 다시 꺼내자. 답은 이미 정해져 있고 우리가 고르는 건 거기 가는 길이다.

여기까지 본 길들이 그 말을 하나씩 증명했다.

완전탐색은 아무것도 안 버려서 확실한 대신 후보 수를 그대로 낸다.
이진탐색은 절반을 버리는 대가로 정렬이라는 입장료를 냈다.
분할 정복은 합치기가 싸다는 성질을 빌려 n²을 n log n으로 바꿨다.
동적 계획법은 공간을 내주고 중복 계산을 샀다.
그리디는 되돌아보기를 포기하고 속도를 얻었다.

공짜로 빨라진 길은 하나도 없었다. 전부 무언가를 내주고 무언가를 샀다. 그러니 길을 고르는 일은 “제일 빠른 것 찾기”가 아니라 **“내가 낼 수 있는 값이 무엇인지 정하기”**다.

한 장으로 본 거래표

말로 옮기면 이렇게 된다. 각 길이 무엇을 내주고 무엇을 얻었는지다.

길	얻은 것	내준 것	언제
완전탐색	반드시 맞는 답	후보 수만큼의 시간	후보가 적을 때, 그리고 채점 기준으로
정렬	이후의 모든 일이 싸진다	`n log n`과 안정성 걱정	같은 데이터를 여러 번 다룰 때
이진탐색	100만이 스무 번	정렬을 유지해야 한다	정렬된 것에서 경계를 찾을 때
재귀	중첩 구조를 그대로 옮긴다	깊이만큼 쌓인다	데이터가 자기 안에 자기를 담을 때
분할 정복	`n²`이 `n log n`이 된다	합칠 자리가 필요하다	합치기가 원래 문제보다 쌀 때
동적 계획법	중복 계산이 사라진다	표를 들고 있어야 한다	같은 작은 문제가 또 나올 때
그리디	한 줄로 곧장 내려간다	최적이 아닐 수 있다	맞는다고 증명됐거나, 최적이 불가능할 때

이 표는 “무엇이 빠른가”가 아니라 “무엇을 냈는가”로 읽어야 한다. 내가 낼 수 없는 값을 요구하는 길이면 그건 나에게 빠른 길이 아니다.

문제의 모양이 방법을 정한다

실제로 고를 때는 방법을 훑는 게 아니라 문제가 어떤 모양인지를 먼저 본다. 모양이 정해지면 방법은 대개 따라온다.

후보를 하나 고르면 나머지가 확 줄어드나. 그러면 이진탐색이나 가지치기가 붙는다. 한 번 보고 절반을 버릴 수 있다는 게 이 성질이다.

작은 문제로 쪼개지고, 쪼갠 것들이 서로 겹치나. 겹치면 동적 계획법이고, 안 겹치면 분할 정복이다. 이 둘을 가르는 건 오직 겹치느냐뿐이다.

매 순간의 최선이 전체의 최선인가. 그러면 그리디다. 단 이건 짐작하면 안 되고 확인해야 한다.

아무 성질도 안 보이나. 그러면 완전탐색이 답이다. 그리고 그게 부끄러운 결론이 아니다. 후보를 세어봐서 감당되면 거기서 끝내는 게 맞다.

그런데 대부분은 알고리즘 문제가 아니다

솔직하게 말할 대목이 있다. 실무에서 코드가 느릴 때, 원인이 알고리즘인 경우는 생각보다 훨씬 적다.

먼저 재본다느릴 것 같은 자리와 느린 자리는 다르다 느리다고 들어온 문제 전부

코드 밖을 본다DB 왕복·외부 호출·N+1 대부분 여기서 끝난다

안 보이는 반복을 찾는다반복문 안의 contains 한 줄 그릇을 바꾸면 풀린다

같은 계산을 또 하는지 본다루프마다 다시 구하는 값 쪽지 한 장

방법 자체를 바꾼다이 시리즈에서 배운 것 여기까지 오는 일은 드물다

칸의 폭 = 여기까지 내려오는 문제의 양

의심할 순서를 아는 것 자체가 이 시리즈의 값어치다. 위쪽에서 거의 다 걸러지지만, 걸러내려면 아래를 알아야 한다.

의심하는 순서가 있고, 알고리즘은 그 순서에서 한참 아래다.

첫째, 재본다. 느릴 것 같은 자리와 실제로 느린 자리는 자주 다르다. 재보지 않고 고치기 시작하면 멀쩡한 코드를 복잡하게 만들고 끝난다.

둘째, 코드 밖을 본다. 대부분 여기서 끝난다. DB를 100번 왕복하거나, 반복문 안에서 매번 쿼리를 날리거나, 외부 API를 순서대로 부르고 있다. 반복문 100만 번이 0.01초인데 네트워크 왕복 한 번이 그보다 오래 걸린다. 계산량이 아니라 왕복 횟수가 범인이다.

셋째, 안 보이는 반복을 찾는다. 반복문 안의 contains 한 줄이 O(n²)을 만드는 그 모양이다. 이건 알고리즘을 바꾸는 게 아니라 그릇을 바꾸면 풀린다.

넷째, 같은 계산을 또 하는지 본다. 루프마다 같은 값을 다시 구하고 있지 않은지. 이건 쪽지 한 장이면 끝난다.

여기까지 다 하고도 안 되면 그때가 방법 자체를 바꿀 자리다. 그리고 거기까지 가는 일은 드물다.

그럼 왜 배웠나

여기까지 읽고 나면 이상해진다. 직접 짤 일도 드물고 원인인 경우도 적다면 왜 아나.

의심할 순서를 아는 것 자체가 이 지식이기 때문이다. 위의 네 단계는 전부 이 시리즈에서 본 개념으로 쓰여 있다. 겹친 반복을 알아보려면 세는 법을 알아야 하고, 중복 계산을 의심하려면 그게 문제가 된다는 걸 알아야 한다. 모르면 순서가 없고, 순서가 없으면 아무 데나 고친다.

그리고 남이 만든 것을 읽을 때 값을 한다.

실행 계획에 적힌 조인 방식이 무슨 뜻인지, 왜 인덱스를 걸면 그게 바뀌는지
목록 순서가 새로고침마다 흔들리는 증상이 왜 정렬 안정성 문제인지
캐시 적중률이 왜 갑자기 떨어졌는지, 무엇을 버리는 규칙이 어떤 접근 패턴에 약한지
배치 작업이 데이터가 늘면서 왜 서서히가 아니라 어느 날 갑자기 안 끝나는지

마지막 줄이 이 시리즈의 요지에 가깝다. 늘어나는 모양을 아는 사람에게만 그건 예고된 일이다. 모르면 그냥 사고고, 알면 데이터가 두 배 됐을 때 무엇이 네 배가 되는지 미리 보인다.

여기서 다루지 않은 것

이 시리즈가 알고리즘 전부를 다룬 건 아니다. 자주 만나게 될 텐데 여기 없는 것들을 밝혀 둔다.

선에 값이 있는 그래프의 최단 경로. 지도 앱과 라우팅이 매일 하는 계산이다. 그리디 편에서 이름만 스쳤다.
문자열 안에서 문자열 찾기. contains 한 줄이 실제로 무엇을 하는지, 검색 기능이 왜 별도의 색인을 두는지가 여기 걸린다.
정확한 답을 포기하는 방법들. 답이 맞을 확률만 높이거나, 오차를 감수하고 메모리를 극단적으로 아끼는 자료구조들이 있다. 대용량 처리에서 실제로 쓰인다.
여러 대에 나눠 하는 계산. 이 시리즈는 내내 일꾼 하나를 전제로 셌다. 일꾼이 여럿이면 세는 법 자체가 달라진다.

없다고 적어 두는 이유는 하나다. 이 시리즈에서 배운 잣대로 안 재지는 문제가 있다는 걸 알아야 잘못 재지 않는다.

고치지 않는 것도 결정이다

마지막으로 반대 방향의 주의를 둔다. 이 시리즈를 읽고 나면 코드를 열어 방법부터 바꾸고 싶어진다. 대개는 하지 않는 게 맞다.

재보지 않았으면 고치지 않는다. 이건 앞에서 한 말이지만 두 번 적을 값이 있다.
정교한 방법은 읽기 어렵다. 팀이 유지할 코드라면 그것도 값이다. 짧고 느린 코드가 길고 빠른 코드보다 나은 구간이 실제로 있다.
데이터 크기를 모르면 판단할 수 없다. 100건이면 무엇을 써도 즉시 끝난다.
바꿀 거면 기준을 남긴다. 느려도 확실한 것을 옆에 두고 답을 맞춰본다. 빠르게 만들면서 조용히 틀리게 만드는 것이 이 작업의 진짜 위험이다.

길을 고르는 일이 값을 하는 순간은 둘뿐이다. 처음 만들 때 기본을 옳게 잡는 것, 그리고 재보고 원인이 방법으로 드러났을 때 바꾸는 것. 그 사이에서 미리 바꿔두는 것은 대개 값만 내고 아무것도 못 산다.

정리

공짜로 빨라진 길은 없었다. 고르는 일은 무엇을 내줄지 고르는 일이다.
방법을 훑지 말고 문제의 모양을 먼저 본다. 절반을 버릴 수 있나, 쪼갠 것이 겹치나, 지금의 최선이 전체의 최선인가.
쪼갠 것이 겹치면 동적 계획법, 안 겹치면 분할 정복이다. 가르는 건 그것 하나다.
실무에서 느릴 때 의심 순서는 재기 → 코드 밖(왕복) → 안 보이는 반복 → 중복 계산 → 그다음이 방법이다.
아는 값어치는 짜는 데 있지 않고 의심할 순서를 갖는 데 있다.
재보지 않았으면 바꾸지 않는다. 빠르게 만들면서 조용히 틀리게 만드는 것이 가장 큰 위험이다.