알고리즘 - 답이 아니라 답에 이르는 길

내비게이션에 목적지를 찍으면 경로가 여러 개 나온다. 도착지는 같은데 걸리는 시간이 다르다. 알고리즘도 딱 그 이야기다.

같은 목적지, 다른 길

“1부터 100까지 더하라”는 문제를 받았다고 하자. 답은 5,050 하나뿐이다. 그런데 거기까지 가는 길은 둘이다.

java

int sum = 0;
for (int i = 1; i <= 100; i++) sum += i;   // 100번 더한다

java

int sum = 100 * 101 / 2;                    // 한 번 계산한다

답은 똑같고 하는 일의 양이 다르다. 100까지면 둘 다 눈 깜짝할 사이지만, 1억까지라면 위는 1억 번을 돌고 아래는 여전히 한 번이다.

같은 입력 - 1부터 100까지 더하라

↓ 사이에 낀 일의 양만 다르다 ↓

한 번에 하나씩 더한다 … 100번

식으로 한 번에 계산한다 1번

↓ 그런데 도착지는 같다 ↓

같은 답 - 5,050

위아래가 같은 곳에서 출발해 같은 곳에 닿는다. 우리가 고르는 것은 답이 아니라 사이에 낀 일의 양이다.

이게 알고리즘을 배우는 이유 전부다. 무엇이 답인가는 이미 정해져 있고, 우리가 고르는 건 거기 가는 길이다.

알고리즘이라 부를 수 있으려면

절차라고 다 알고리즘은 아니다. 세 가지를 갖춰야 한다.

반드시 끝난다. 어떤 입력을 줘도 언젠가 멈춰야 한다. 영원히 도는 건 절차이긴 해도 알고리즘은 아니다.
답이 맞다. 빠르기 전에 옳아야 한다. 틀린 답을 빨리 내는 건 아무 값이 없다.
애매한 데가 없다. “적당히 큰 것을 고른다” 같은 말이 남아 있으면 사람마다 다르게 실행한다.

셋 중 흔들리기 쉬운 건 첫 번째다. 반드시 끝난다는 조건은 코드를 짤 때 자동으로 지켜지지 않는다. 조건 하나를 잘못 적으면 무한 루프가 되고, 그건 “느린 알고리즘”이 아니라 알고리즘이 아니게 된 것이다.

참고

여기서 비유가 깨지는 자리를 먼저 밝혀둔다. 내비게이션의 경로는 길이 이미 거기 있고 우리는 고르기만 한다. 알고리즘은 다르다. 길 자체를 우리가 낸다. 그래서 없던 길을 새로 내면 남들이 몇 시간 걸리던 문제가 몇 초가 되는 일이 실제로 벌어진다. 이 시리즈에서 볼 것들은 그렇게 누군가 내둔 길이다.

길이 여럿인 이유

왜 하나로 정해지지 않을까. 길마다 무엇을 아끼고 무엇을 쓰는지가 다르기 때문이다.

어떤 길은 시간을 아끼고 메모리를 쓴다. 미리 계산해서 적어두면 다시 안 세도 된다.
어떤 길은 메모리를 아끼고 시간을 쓴다. 적어두지 않고 필요할 때마다 다시 센다.
어떤 길은 평소엔 빠른데 최악에 무너진다. 대신 평소가 압도적으로 많다.
어떤 길은 느린 대신 짧고 읽기 쉽다. 그것도 값이다.

그릇을 고를 때와 똑같은 모양이다. 자료구조가 “무엇을 싸게 하고 무엇을 비싸게 할지”를 골랐다면, 알고리즘은 “무엇을 아끼고 무엇을 쓸지”를 고른다. 공짜인 쪽은 없다.

무엇으로 재나

길을 비교하려면 잣대가 필요하다. 두 가지를 잰다.

하나는 시간이다. 데이터가 늘 때 하는 일이 몇 배가 되는가. 빅오로 재는 그것이다.

다른 하나는 공간이다. 답을 내는 동안 입력 말고 따로 쓰는 메모리가 얼마나 되는가. 입력 자체는 어차피 들고 있어야 하니 세지 않고, 추가로 쓰는 것만 센다.

이 시리즈에서 볼 것	시간	추가 공간
하나씩 다 해보기	많이 쓴다	거의 안 쓴다
반씩 버리며 찾기	아주 적게 쓴다	거의 안 쓴다
쪼개서 풀고 합치기	중간	쓴다
계산한 걸 적어두기	아주 적게 쓴다	많이 쓴다

마지막 줄이 이 표의 요지다. 시간을 극적으로 줄인 방법은 대개 공간을 지불했다. 그게 뒤에 볼 동적 계획법이다.

짧아 보이는 길이 늘 빠른 건 아니다

내비게이션이 가끔 먼 길로 안내한다. 거리는 길어도 막히지 않아서다. 알고리즘도 그렇다.

정교한 방법에는 준비 동작이 있어 출발선이 위에 있다. 그래서 데이터가 적은 구간은 단순한 방법의 몫이다.

데이터가 적을 때는 단순한 방법이 이긴다. 정교한 방법은 쪼개고 합치고 자리를 잡느라 준비 동작이 있는데, 데이터가 적으면 그 준비가 본 작업보다 비싸다.

실제로 정렬 라이브러리들은 조각이 작아지면 일부러 단순한 방식으로 갈아탄다. “더 나은 알고리즘”이 있어서 안 쓰는 게 아니라, 그 구간에서는 그게 더 나은 알고리즘이 아니기 때문이다.

그래서 판단의 첫 줄은 늘 같다. 내 데이터가 얼마나 되나. 100건이면 무엇을 써도 즉시 끝나고, 거기서 알고리즘을 고민하는 건 아끼는 시간보다 고민하는 시간이 비싼 일이다.

그릇을 바꾸면 길이 바뀐다

알고리즘과 자료구조를 따로 배우면 놓치는 게 하나 있다. 둘은 같이 정해진다.

java

for (String id : ids) {
    if (blocked.contains(id)) { … }
}

이 코드에서 절차는 그대로인데 blocked가 리스트냐 Set이냐로 전체 비용이 갈린다. 리스트면 한 줄이 처음부터 훑어서 O(n²)이고, Set이면 곧장 답해서 O(n)이다.

코드를 고친 게 아니라 그릇을 바꾼 것인데 결과는 알고리즘을 바꾼 것과 같다. 그래서 “이 문제를 어떻게 풀까”는 늘 “무엇에 담을까”와 한 몸으로 온다. 앞으로 볼 방법들도 대개 어떤 그릇을 전제로 한다. 이진탐색은 정렬된 배열을, 너비 우선은 큐를, 우선순위는 힙을 깔고 선다.

실무에서: 대부분은 남이 낸 길을 고른다

솔직하게 말할 대목이 있다. 정렬을 직접 짜는 일은 거의 없다. 언어마다 sort가 있고 그게 더 빠르고 더 안전하다.

그럼 왜 배우나. 실무에서 알고리즘 지식이 실제로 값을 하는 자리는 짜는 쪽이 아니라 읽는 쪽이다.

쿼리가 느려서 실행 계획을 봤더니 어떤 방식으로 조인하는지가 적혀 있다. 그게 무슨 뜻인지 알아야 인덱스를 어디에 걸지 판단이 선다.
목록 정렬이 새로고침할 때마다 순서가 미묘하게 달라진다. 안정 정렬이 무엇인지 알면 5분이고, 모르면 며칠 헤맨다.
배치 작업이 데이터가 늘면서 어느 날 갑자기 밤새 안 끝난다. 대개 겹친 반복 하나 때문이다.
캐시가 무엇을 먼저 버릴지 정하는 규칙에도 이름이 있고, 그 이름이 곧 알고리즘이다.

직접 만들 일이 없다는 게 몰라도 된다는 뜻은 아니다. 남이 낸 길을 고르려면 그 길이 어디로 나 있는지는 알아야 한다.

정리

알고리즘은 답이 아니라 답에 이르는 절차다. 답이 하나여도 길은 여럿이다.
알고리즘이려면 끝나야 하고, 맞아야 하고, 애매하지 않아야 한다. 빠른 건 그다음이다.
재는 잣대는 둘이다. 시간과 추가 공간. 시간을 크게 줄인 방법은 대개 공간을 냈다.
데이터가 적으면 단순한 쪽이 이긴다. 정교한 방법에는 준비 동작이 있다.
알고리즘은 자료구조와 한 몸으로 정해진다. 그릇을 바꾸면 절차를 안 고쳐도 비용이 바뀐다.

다음 글은 가장 먼저 떠올려야 할 방법에서 시작한다. 일단 다 해보는 것. 무식해 보이지만 이게 모든 판단의 기준선이다.