알고리즘,
움직이는 그림으로 이해하기

얼마나 빠른가 — 빅오

그로밋이 치즈 창고에서 웬슬리데일 한 조각을 찾습니다. 창고에 상자가 10개일 때와 100만 개일 때, 일이 몇 배로 늘어나는가. 알고리즘의 성능은 초 단위가 아니라 이 늘어나는 모양으로 말합니다. 컴퓨터가 두 배 빨라져도 모양은 그대로이기 때문입니다.

쓰이는 곳 — 두 방법 중 어느 쪽을 쓸지 고를 때. 실무에서 "이거 데이터 늘어나면 터져요"의 근거.

선형 탐색

그로밋이 선반의 치즈 상자를 왼쪽부터 하나씩 열어 봅니다. 특별한 요령은 없습니다. 찾을 때까지, 혹은 선반이 끝날 때까지. 세상에서 가장 단순한 알고리즘이고, 정리되어 있지 않은 자료에는 이 방법밖에 없습니다.

쓰이는 곳 — 정렬되지 않은 목록, 한 번만 찾는 경우, 자료가 아주 적을 때.

이진 탐색

이번엔 상자에 무게가 적혀 있고, 가벼운 것부터 정렬되어 놓여 있습니다. 그로밋은 한가운데 상자부터 봅니다. 찾는 것보다 무거우면 오른쪽 절반은 통째로 버립니다. 한 번 볼 때마다 후보가 절반으로 줄어듭니다. 100만 개도 스무 걸음이면 끝납니다.

쓰이는 곳 — 사전 찾기, 데이터베이스 색인, 게임의 난이도 조절, "조건을 만족하는 최솟값" 문제 전반.

버블 정렬

치즈 조각들을 크기순으로 세우는 첫 번째 방법. 그로밋은 옆에 놓인 둘만 비교합니다. 왼쪽이 더 크면 자리를 바꿉니다. 이걸 끝까지 한 바퀴 돌면, 가장 큰 조각이 거품처럼 맨 오른쪽까지 떠밀려 갑니다. 그 자리를 확정하고 다시 한 바퀴.

쓰이는 곳 — 교육용. 그리고 "거의 정렬된 데이터를 한 번 점검"할 때 아주 가끔.

선택 정렬

그로밋이 아직 정리되지 않은 구역 전체를 눈으로 훑어 가장 작은 조각 하나를 고릅니다. 그걸 맨 앞자리 조각과 딱 한 번 맞바꿉니다. 앞자리가 확정되면, 남은 구역에서 다시 최솟값을 고릅니다. 비교는 많지만 실제로 물건을 옮기는 횟수는 n번뿐입니다.

쓰이는 곳 — 데이터 이동 비용이 클 때, 메모리가 극도로 부족한 임베디드 환경.

삽입 정렬

손에 든 카드를 정리하는 방식 그대로입니다. 왼쪽은 이미 정렬된 부분, 오른쪽은 아직 손대지 않은 부분. 그로밋은 오른쪽에서 조각 하나를 뽑아 들고, 왼쪽 정렬된 줄에서 제자리를 찾을 때까지 뒤로 밀며 끼워 넣습니다.

쓰이는 곳 — 원소 20개 이하의 작은 배열, 실시간으로 하나씩 들어오는 데이터, 하이브리드 정렬의 마무리 단계.

병합 정렬

그로밋은 혼자 다 하지 않습니다. 줄을 절반으로 자르고, 또 절반으로 자르고, 조각이 하나가 될 때까지 자릅니다. 하나짜리는 이미 정렬된 상태죠. 그다음 정렬된 두 줄을 앞에서부터 비교하며 하나로 합칩니다. 합치는 일은 두 줄의 맨 앞만 보면 되므로 놀랄 만큼 빠릅니다.

쓰이는 곳 — 메모리에 다 안 들어가는 거대 파일 정렬(외부 정렬), 자바의 객체 정렬, 안정성이 필요한 모든 곳.

퀵 정렬

그로밋이 조각 하나를 기준(피벗)으로 집습니다. 기준보다 가벼운 건 왼쪽으로, 무거운 건 오른쪽으로 던집니다. 이 한 번의 작업이 끝나면 기준 조각의 자리는 영원히 확정됩니다. 그리고 왼쪽 무더기와 오른쪽 무더기에 같은 일을 반복합니다.

쓰이는 곳 — 대부분의 언어에서 기본 정렬의 뼈대. 메모리가 빠듯하고 평균 속도가 중요할 때.

계수 정렬 — 비교하지 않는 정렬

지금까지의 정렬은 전부 "둘을 비교"했습니다. 그런데 값의 범위가 좁다면 — 예컨대 치즈 숙성 연차가 0~9년뿐이라면 — 비교할 필요가 없습니다. 그로밋은 0번부터 9번까지 바구니를 늘어놓고 조각을 해당 바구니에 던져 넣은 뒤, 바구니를 순서대로 비웁니다. 비교 정렬의 O(n log n) 한계를 뚫고 O(n)에 끝납니다.

쓰이는 곳 — 나이·점수·색상값처럼 범위가 정해진 데이터, 이미지 처리의 히스토그램, 기수 정렬의 부품.

정렬 — 무엇을 언제 쓰는가

여섯 가지를 봤습니다. 실무에서 직접 구현할 일은 거의 없지만, 왜 언어가 이걸 골랐는지를 알면 데이터가 커졌을 때 무엇을 의심할지 알게 됩니다. 아래 무대에서 세 가지 정렬을 같은 데이터로 동시에 돌려 보세요.

재귀 — 자기 자신을 부르기

그로밋의 치즈 접시가 세 개의 받침대 중 첫 번째에 크기순으로 쌓여 있습니다. 규칙: 한 번에 한 장만, 큰 접시를 작은 접시 위에 올리면 안 됨. 전부 세 번째 받침대로 옮기려면? "n장 옮기기"를 "n−1장 옮기기 + 한 장 옮기기 + 다시 n−1장 옮기기"로 바꿔 말하는 순간 문제가 풀립니다. 자기보다 작은 자기 자신에게 일을 떠넘기는 것 — 이게 재귀입니다.

쓰이는 곳 — 폴더 안의 폴더 탐색, 트리 순회, 파서, 그리고 아래 나올 거의 모든 알고리즘.

분할 정복 — 반씩 접기

병합 정렬과 퀵 정렬이 이미 이 방식이었습니다. 쪼갠다 → 각각 푼다 → 합친다. 이 습관의 위력을 가장 짧게 보여 주는 예가 거듭제곱입니다. 그로밋이 2를 20번 곱해야 한다면 곱셈을 20번 할 필요가 없습니다. 2¹⁰을 구한 뒤 자기 자신과 한 번 곱하면 2²⁰이니까요. 20번이 5번으로 줄어듭니다.

쓰이는 곳 — 암호(RSA), 행렬 거듭제곱, 큰 수 곱셈, 병합·퀵 정렬, 가장 가까운 두 점 찾기.

백트래킹 — 아니면 되돌아가기

그로밋이 정원에 양들을 배치합니다. 규칙은 체스의 퀸과 같아서, 어떤 두 마리도 같은 가로줄·세로줄·대각선에 있으면 안 됩니다. 방법은 단순합니다. 한 줄씩 놓아 보고, 놓을 수 없게 되면 직전 선택을 취소하고 다른 자리를 시도합니다. 미로에서 막다른 길을 만나면 갈림길로 되돌아가는 것과 똑같습니다.

쓰이는 곳 — 스도쿠 풀이, 미로 찾기, 시간표 짜기, 정규식 매칭, 조합·순열 만들기.

탐욕법 — 지금 제일 좋아 보이는 것

그로밋이 거스름돈을 줍니다. 앞일은 생각하지 않고 매 순간 가장 큰 동전부터 집습니다. 놀랍게도 우리 동전 체계에서는 이게 항상 최소 개수의 정답입니다. 미래를 계산하지 않고도 정답이 나오는 문제들이 있고, 그런 문제에서는 탐욕법이 가장 빠르고 가장 간단합니다.

쓰이는 곳 — 거스름돈, 회의실 배정, 파일 압축(허프만 코딩), 최소 신장 트리, 다익스트라.

동적계획법 — 두 번 계산하지 않기

탐욕법이 미래를 안 보는 방법이라면, 동적계획법은 미래를 전부 보되 낭비하지 않는 방법입니다. 그로밋이 피보나치 수를 재귀로 계산하면 같은 값을 수백 번 다시 구합니다. 한 번 구한 답을 수첩에 적어 두고 다시 물어보면 수첩을 보는 것 — 그것만으로 O(2ⁿ)이 O(n)이 됩니다.

쓰이는 곳 — 맞춤법 검사, 유전자 서열 비교, 최적 경로, 자원 배분, 게임 AI.

배낭 문제 — 무엇을 담을까

그로밋이 소풍 가방을 쌉니다. 가방은 무게 10까지만 견디고, 짐마다 무게와 만족도가 다릅니다. 만족도 합을 가장 크게 하려면 무엇을 담아야 할까요? 여기서 탐욕법(비싼 것부터)은 틀립니다. 표를 "짐 1개만 쓸 때 / 2개까지 쓸 때 …" 순으로 채워 올라가야 정답이 나옵니다.

쓰이는 곳 — 예산 배분, 광고 편성, 화물 적재, 투자 포트폴리오, 클라우드 자원 할당.

편집 거리 — 얼마나 닮았는가

그로밋이 쪽지에 적힌 gromit을 gadget으로 고치려 합니다. 글자를 넣거나, 지우거나, 바꾸는 최소 횟수는 몇 번일까요? 이 숫자가 두 단어의 거리입니다. 오타 교정, 검색어 추천, 유전자 비교가 전부 이 표 한 장에서 나옵니다.

쓰이는 곳 — 맞춤법 검사기, 검색엔진의 "이것을 찾으셨나요", 생물정보학, 버전 관리 도구.

그래프 — 무엇이 무엇과 이어져 있는가

웨스트 웰링턴 마을에는 집이 여덟 채 있고, 길이 그 사이를 잇습니다. 집을 점(정점), 길을 선(간선)이라 부르면 이 마을은 그래프입니다. 지하철 노선도, 친구 관계, 웹페이지의 링크, 작업의 선후 관계 — 전부 같은 그림입니다. 여기서부터 나오는 알고리즘은 모두 이 그림 위를 걸어 다니는 방법입니다.

쓰이는 곳 — 내비게이션, SNS 친구 추천, 배달 경로, 빌드 순서, 인터넷 라우팅.

너비 우선 탐색 — 가까운 곳부터

그로밋이 집집마다 신문을 돌립니다. 방식은 물결처럼입니다. 우리 집에서 한 걸음 거리의 집을 전부 돌고, 그다음 두 걸음 거리의 집을 전부 돕니다. 다음에 갈 집을 줄 세워 두고 앞에서부터 꺼내는 것이 전부입니다. 이렇게 하면 모든 집까지의 최소 걸음 수가 저절로 나옵니다.

쓰이는 곳 — 미로 최단 경로, SNS 친구 거리, 웹 크롤러, 이미지의 영역 채우기.

깊이 우선 탐색 — 끝까지 가 보고

이번엔 성격이 정반대입니다. 그로밋은 길이 나오면 일단 끝까지 갑니다. 더 갈 곳이 없으면 되돌아와 아직 안 가 본 갈림길을 택합니다. 백트래킹과 같은 몸짓이고, 실제로 재귀 한 줄이면 구현됩니다. BFS가 넓게 퍼지는 물결이라면 DFS는 깊게 파는 굴입니다.

쓰이는 곳 — 연결 요소 찾기, 순환 감지, 위상 정렬, 미로 생성, 백트래킹 전반.

다익스트라 — 진짜 최단 경로

이제 길마다 걸리는 시간이 다릅니다. 그로밋이 집에서 치즈 가게까지 가장 빨리 가는 길을 찾습니다. 요령은 이렇습니다. 지금까지 알아낸 것 중 가장 가까운 집을 확정하고, 그 집을 거쳐 가면 더 빨라지는 이웃이 있는지 갱신합니다. 확정된 집은 다시 보지 않습니다 — 그게 이 알고리즘이 빠른 이유입니다.

쓰이는 곳 — 내비게이션, 네트워크 라우팅, 게임 캐릭터 길찾기, 항공권 최저가 탐색.

최소 신장 트리 — 가장 싸게 다 잇기

마을에 수도관을 놓습니다. 모든 집에 물이 가야 하지만, 공사비는 최소여야 합니다. 그로밋의 방법: 모든 길을 싼 것부터 줄 세우고, 위에서부터 하나씩 채택합니다. 단, 이미 이어진 두 집을 또 잇는 길은 낭비이므로 버립니다. 이것이 크루스칼 알고리즘입니다.

쓰이는 곳 — 통신망·전력망 설계, 도로 건설 계획, 회로 배선, 이미지 분할, 군집 분석.

문자열 찾기 — 헛걸음 줄이기

그로밋이 신문에서 "CHEESE"라는 단어를 찾습니다. 순진한 방법은 한 칸씩 밀며 매번 처음부터 대조하는 것입니다. 그런데 이미 맞춰 본 글자에는 정보가 남아 있습니다. "CHEE"까지 맞다가 틀렸다면, 다음에 한 칸이 아니라 여러 칸을 건너뛰어도 안전한지를 미리 계산해 둘 수 있습니다. KMP 알고리즘의 아이디어입니다.

쓰이는 곳 — 문서 검색, 로그 분석, 침입 탐지 패턴 매칭, DNA 서열 검색, grep.

못 푸는 문제 — 어려움의 경계

모든 문제가 빠른 방법을 갖고 있지는 않습니다. 그로밋이 마을의 모든 집을 한 번씩만 들러 돌아오는 가장 짧은 배달 경로를 찾으려 하면, 집이 20채만 되어도 경우의 수가 천문학적입니다. 지금까지 아무도 빠른 방법을 찾지 못했고, 애초에 존재하는지조차 모릅니다.

한눈에 비교

25장을 지나왔습니다. 마지막으로 문제를 만났을 때 무엇을 꺼낼지의 관점에서 정리합니다. 알고리즘 공부의 실제 쓸모는 외우는 데 있지 않고, "아, 이건 그거네"라고 알아보는 데 있습니다.