데이터와 알고리즘

알고리즘은 레시피, 자료구조는 그릇

알고리즘(algorithm)은 문제를 푸는 절차다. 요리로 치면 레시피다. 같은 김치찌개도 레시피에 따라 30분이 걸리기도 하고 3시간이 걸리기도 한다. 자료구조(data structure)는 데이터를 담는 방식이다. 양념을 서랍에 아무렇게나 넣어 두면 찾을 때마다 다 뒤져야 하지만, 이름순으로 꽂아 두거나 칸마다 라벨을 붙이면 금방 찾는다.

알고리즘이 얼마나 빠른지는 초(秒)가 아니라 단계 수로 잰다. 초는 컴퓨터마다 다르지만, 단계 수는 방법 자체의 성질이기 때문이다. 그리고 가장 중요한 질문은 “데이터가 10배, 1000배로 늘면 단계 수는 어떻게 늘어나나”다.

찾기: 하나씩 볼까, 반씩 버릴까

전화번호부에서 이름 하나를 찾는다고 하자. 첫 장부터 한 명씩 확인하는 것이 순차 탐색(linear search)이다. 하지만 전화번호부는 가나다순으로 정렬되어 있다. 가운데를 펼쳐 찾는 이름이 앞쪽인지 뒤쪽인지 보고, 절반을 통째로 버리는 일을 반복할 수 있다. 이것이 이진 탐색(binary search)이다.

정렬: 줄 세우기 경주

이진 탐색을 쓰려면 먼저 정렬해야 한다. 정렬은 컴퓨터가 가장 많이 하는 일 중 하나다. 쇼핑몰의 “낮은 가격순”, 메일함의 “최신순”, 검색 결과의 순위가 모두 정렬이다. 방법은 여러 가지다.

• 버블 정렬: 이웃한 둘을 비교해 큰 것을 뒤로 보내는 일을 반복한다. 단순하지만 느리다.
• 삽입 정렬: 카드를 한 장씩 집어 이미 정리된 손패의 알맞은 자리에 끼운다. 거의 정렬된 데이터에 강하다.
• 병합 정렬: 반으로 나누고, 각각 정렬한 뒤, 두 줄을 앞에서부터 비교하며 합친다.
• 퀵 정렬: 기준값 하나를 골라 그보다 작은 것과 큰 것으로 나누고, 각 쪽을 다시 같은 방법으로 정렬한다.

빅오: 데이터가 늘면 시간은 어떻게 늘까

정렬 경주에서 본 것처럼, 중요한 것은 지금 몇 번인지보다 데이터가 늘 때 단계 수가 늘어나는 모양이다. 이것을 나타내는 표기가 빅오(Big-O)다. O(n)은 “데이터가 2배면 시간도 2배”, O(n²)은 “데이터가 2배면 시간은 4배”라는 뜻이다. 컴퓨터를 10배 빠르게 사도, O(n²) 알고리즘으로는 데이터를 약 3배밖에 더 처리하지 못한다.

그릇 고르기: 배열, 연결 리스트, 해시 테이블

데이터를 메모리에 어떻게 놓느냐에 따라 잘하는 일이 다르다. 6장의 메모리 사물함을 떠올리자.

해시 테이블(hash table)은 16장의 해시 함수를 응용한다. 이름을 해시 함수에 넣어 나온 수를 칸 번호로 쓰면, 찾을 때도 같은 계산으로 바로 그 칸에 간다. 문제는 서로 다른 이름이 같은 칸 번호를 받는 충돌(collision)이다. 그때는 그 칸에 줄을 세운다.

지도 앱은 어떻게 길을 찾을까

지도 앱의 길 찾기, 10장의 라우터가 패킷 경로를 고르는 일, 게임 캐릭터가 벽을 피해 움직이는 일은 모두 같은 문제다. 장소를 점으로, 길을 선으로 놓은 그래프(graph)에서 최단 경로(shortest path)를 찾는 것이다. 아래 격자에서 벽을 그리고 세 가지 방법을 비교해 보자.