지난 글까지 0과 1에서 시작해 동작하는 컴퓨터 한 대를 조립했다. 이제 이 컴퓨터로 문제를 풀 차례다. 하지만 컴퓨터는 혼자 생각하지 못한다. 어떤 문제든 사람이 먼저 쪼개고, 풀이 순서를 하나하나 정해줘야 한다.
숫자 다섯 개가 있다. 14, 3, 27, 8, 21. 가장 큰 수는?
27이라는 답이 떠오른다. 하지만 우리가 방금 한 일을 되짚어보자. 순서야 사람마다 다르겠지만, 결국 숫자를 하나씩 확인하면서 지금까지 본 것 중 가장 큰 수를 머릿속에 담아두고 있었다. 다섯 개쯤이야 너무 빨라서 이런 절차가 있었다는 것 자체를 의식하지 못한 것뿐이다.
이 과정을 큰 수를 골라낸다라고 적으면 충분할까? 라면을 끓여라라는 말을 사람은 이해하지만, 컴퓨터는 물을 어디에 담는지, 봉지를 뜯는 건지, 적당히가 몇 분인지 하나도 모른다. 적혀 있지 않기 때문이다. 큰 수를 골라낸다도 마찬가지다. 어디서부터 보는지, 무엇과 비교하는지, 언제 멈추는지가 빠져 있다. 누가 따라 하더라도 똑같은 순서로 똑같은 결과가 나와야 비로소 컴퓨터에게 시킬 수 있는 절차가 된다.
이번에는 정렬을 생각해보자. 카드 다섯 장이 뒤섞여 있다. 작은 수부터 순서대로 놓고 싶다.
사람이 자연스럽게 하는 방법 중 하나는 전체에서 가장 작은 카드를 찾아 맨 앞에 놓고, 나머지에서 또 가장 작은 걸 찾아 그 다음에 놓는 것이다. 직관적으로는 명확하다. 하지만 컴퓨터에게 시키려면 어디서부터 찾는지, 언제 멈추는지, 각 단계에서 정확히 무엇을 하는지 빠짐없이 적어야 한다.
이것이 선택 정렬(selection sort)이라 불리는 알고리즘이다. 1단계의 가장 작은 값을 찾는다는 방금 최댓값을 찾을 때 쓴 절차와 같다. 이미 만든 절차를 부품처럼 가져다 쓴 것이다.
절차를 쪼개면 컴퓨터에게 시킬 수 있다. 그런데 같은 일을 시키더라도 방법이 하나만 있는 건 아니다. 방법에 따라 성능은 얼마나 달라질까?
컴퓨터가 실제로 다루는 데이터는 수십억, 수조 개에 이른다. 데이터가 적을 때는 어떤 방법을 쓰든 금방 끝난다. 하지만 커질수록 방법 간의 차이는 극적으로 벌어진다. 한 방법은 1초 만에 끝나는데 다른 방법은 며칠이 걸릴 수 있다.
예를 들어 정렬된 숫자 50개에서 특정 값을 찾는다고 하자. 처음부터 하나씩 확인하는 방법을 선형 탐색(linear search)이라 한다.
하지만 데이터가 정렬되어 있다면 가운데를 확인하고 절반을 버리는 과정을 반복할 수 있다. 이것이 이진 탐색(binary search)이다.
같은 데이터, 같은 작업인데 방법 하나로 확인 횟수가 크게 줄어든다. 데이터가 커질수록 차이는 극적으로 벌어진다. 10억 개라면 하나씩 확인하면 최악의 경우 10억 번이지만, 반씩 줄이면 약 30번이면 찾을 수 있다.
데이터를 어떤 형태로 저장하고 관리하는 방식을 자료구조, 데이터를 처리하는 구체적인 절차를 알고리즘이라 한다. 앞서 최댓값을 찾을 때 풀어 쓴 세 단계가 알고리즘의 한 예다.
이 둘은 따로 떨어지지 않는다. 같은 데이터라도 어떤 자료구조로 정리해 두느냐에 따라 특정 작업은 빨라지고 다른 작업은 느려진다. 모든 작업에 최적인 자료구조는 없다. 풀려는 문제에 맞는 자료구조를 고르고, 그에 맞는 알고리즘을 짜는 것이 핵심이다.
우리가 당연하게 하는 일도 명확한 단계로 쪼갤 수 있고, 단계로 쪼갤 수 있으면 컴퓨터에게 시킬 수 있다. 이 절차가 알고리즘이고, 데이터를 정리하는 방식이 자료구조다. 같은 문제라도 어떤 자료구조와 알고리즘을 택하느냐에 따라 결과는 같아도 걸리는 시간은 극적으로 달라진다.
적합한 자료구조를 고르려면 컴퓨터가 데이터를 메모리 위에서 어떻게 조직하는지 먼저 알아야 한다. 방법은 크게 두 가지다. 데이터를 메모리에 나란히 놓거나, 떨어진 조각들을 포인터로 연결하거나. 다음 글에서는 이 두 가지 기본 방식을 살펴본다.