0과 1에서 시작해 동작하는 컴퓨터 한 대를 조립했습니다. 이제 이 컴퓨터로 문제를 풀 차례입니다. 하지만 컴퓨터는 혼자 생각하지 못합니다. 어떤 문제든 사람이 먼저 쪼개고, 풀이 순서를 하나하나 정해줘야 합니다.
숫자 다섯 개가 있습니다. 14, 3, 27, 8, 21. 가장 큰 수는?
27이라는 답이 떠오릅니다. 하지만 우리가 방금 한 일을 되짚어봅시다. 순서야 사람마다 다르겠지만, 결국 숫자를 하나씩 확인하면서 지금까지 본 것 중 가장 큰 수를 머릿속에 담아두고 있었습니다. 다섯 개쯤이야 너무 빨라서 이런 절차가 있었다는 것 자체를 의식하지 못한 것뿐입니다.
이 과정을 큰 수를 골라낸다라고 적으면 충분할까요? 라면을 끓여라라는 말을 사람은 이해하지만, 컴퓨터는 물을 어디에 담는지, 봉지를 뜯는 건지, 적당히가 몇 분인지 하나도 모릅니다. 적혀 있지 않기 때문입니다. 큰 수를 골라낸다도 마찬가지입니다. 어디서부터 보는지, 무엇과 비교하는지, 언제 멈추는지가 빠져 있습니다. 누가 따라 하더라도 똑같은 순서로 똑같은 결과가 나와야 비로소 컴퓨터에게 시킬 수 있는 절차가 됩니다.
이번에는 정렬을 생각해봅시다. 카드 다섯 장이 뒤섞여 있습니다. 작은 수부터 순서대로 놓고 싶습니다.
사람이 자연스럽게 하는 방법 중 하나는 전체에서 가장 작은 카드를 찾아 맨 앞에 놓고, 나머지에서 또 가장 작은 걸 찾아 그 다음에 놓는 것입니다. 직관적으로는 명확합니다. 하지만 컴퓨터에게 시키려면 어디서부터 찾는지, 언제 멈추는지, 각 단계에서 정확히 무엇을 하는지 빠짐없이 적어야 합니다.
이것이 선택 정렬(selection sort)이라 불리는 알고리즘입니다. 1단계의 가장 작은 값을 찾는다는 방금 최댓값을 찾을 때 쓴 절차와 같습니다. 이미 만든 절차를 부품처럼 가져다 쓴 것입니다.
우리가 당연하게 하는 일도 명확한 단계로 쪼갤 수 있고, 단계로 쪼갤 수 있으면 컴퓨터에게 시킬 수 있습니다. 이 절차가 알고리즘입니다. 같은 일이라도 방법에 따라 걸리는 시간이 얼마나 달라지는지는 다음 글에서 살펴봅시다.