문제를 단계로 쪼개면 컴퓨터에게 시킬 수 있습니다. 그런데 같은 일을 시키더라도 방법이 하나만 있는 건 아닙니다. 방법에 따라 성능은 얼마나 달라질까요?
컴퓨터가 실제로 다루는 데이터는 수십억, 수조 개에 이릅니다. 데이터가 적을 때는 어떤 방법을 쓰든 금방 끝납니다. 하지만 커질수록 방법 간의 차이는 극적으로 벌어집니다. 한 방법은 1초 만에 끝나는데 다른 방법은 며칠이 걸릴 수 있습니다.
예를 들어 정렬된 숫자 50개에서 특정 값을 찾는다고 합시다. 처음부터 하나씩 확인하는 방법을 선형 탐색(linear search)이라 합니다.
하지만 데이터가 정렬되어 있다면 가운데를 확인하고 절반을 버리는 과정을 반복할 수 있습니다. 이것이 이진 탐색(binary search)입니다.
같은 데이터, 같은 작업인데 방법 하나로 확인 횟수가 크게 줄어듭니다. 데이터가 커질수록 차이는 극적으로 벌어집니다. 10억 개라면 하나씩 확인하면 최악의 경우 10억 번이지만, 반씩 줄이면 약 30번이면 찾을 수 있습니다.
데이터를 어떤 형태로 저장하고 관리하는 방식을 자료구조, 데이터를 처리하는 구체적인 절차를 알고리즘이라 합니다. 최댓값을 찾는 절차나 방금 본 두 탐색 방법이 알고리즘의 예입니다.
이 둘은 따로 떨어지지 않습니다. 같은 데이터라도 어떤 자료구조로 정리해 두느냐에 따라 특정 작업은 빨라지고 다른 작업은 느려집니다. 모든 작업에 최적인 자료구조는 없습니다. 풀려는 문제에 맞는 자료구조를 고르고, 그에 맞는 알고리즘을 짜는 것이 핵심입니다.
데이터를 처리하는 절차가 알고리즘이고, 데이터를 정리하는 방식이 자료구조입니다. 같은 문제라도 어떤 자료구조와 알고리즘을 택하느냐에 따라 결과는 같아도 걸리는 시간은 극적으로 달라집니다.
적합한 자료구조를 고르려면 컴퓨터가 데이터를 메모리 위에서 어떻게 조직하는지 먼저 알아야 합니다. 방법은 크게 두 가지입니다. 데이터를 메모리에 나란히 놓거나, 떨어진 조각들을 포인터로 연결하거나. 다음 글에서는 이 두 가지 기본 방식을 살펴봅니다.