d라이브러리

 

 

수호가 스파크에게 대항할 방법을 찾은 것 같아요. 아마도 중요한 힌트는 롤랑이 이야기한 ‘좋은 알고리즘’과 그렇지 않은 알고리즘일 거예요. 그렇다면 이 둘을 어떻게 나눌 수 있을까요?

보통 알고리즘은 주어진 문제를 효율적으로 처리하기 위해서 만들어요. 바꿔 말하면, 주어진 문제를 가장 효율적으로 처리할 수 있는 알고리즘이 가장 좋은 알고리즘이지요. 일반적으로 알고리즘의 ‘효율’은 많은 양의 문제를 가능한 한 적은 과정의 일(연산)로 빠르게 처리할수록 높아진답니다. 이 개념을 ‘시간복잡도’라고 해요.

예를 들어 설명해 볼게요. 몇 화 전에 정렬 알고리즘에 대해 이야기한 적이 있어요. 주어진 데이터를 순서대로 늘어놓는 알고리즘이지요. 정렬 알고리즘에는 크게 ‘거품 정렬’과 ‘퀵 정렬’이 있어요. 거품 정렬은 바로 옆에 있는 두 데이터의 크기를 비교해서 순서를 바꿔가며 정렬하는 방법이에요. 반면 퀵 정렬은 임의로 데이터 하나를 기준으로 잡은 뒤, 그보다 큰 데이터는 오른쪽으로 적은 데이터는 왼쪽으로 보내는 방법이지요.

거품 정렬은 ‘옆에 있는 데이터와 크기를 비교하라’, ‘크기에 따라 순서를 바꿔라’ 등 적은 양의 명령어만 있으면 ‘일’을 할 수 있어요. 그래서 코드도 비교적 간단하게 짤 수 있답니다. 하지만 정렬이 시작될 때부터 끝날 때까지 계속 모든 명령어를 사용하며 같은 양의 일을 반복해야 하지요. 그렇기 때문에 데이터의 양이 늘어나면 날수록 처리하는 속도가 느려져요.

반면 퀵 정렬은 기준값을 고르고, 데이터의 위치를 조건에 따라 바꾸는 등 거품 정렬보다 명령어가 많아요. 그래서 코드 길이가 길어지지요. 하지만 정렬이 진행되면 될수록 할 ‘일’이 줄어드는 장점이 있어요.

 

 

이 덕분에 데이터의 양이 늘어나면 거품 정렬보다 더 빠르게 정렬을 끝낼 수 있답니다. 이 경우 퀵 정렬은 거품 정렬보다 시간복잡도가 낮은 알고리즘이 되지요.

컴퓨터에서 쓰는 알고리즘은 우리가 상상하기 힘든 엄청난 양의 데이터를 다루는 경우가 많아요. 그러다 보니 시간복잡도가 좋은 알고리즘을 판단하는 중요한 기준이 되지요. 시간복잡도를 줄이기 위해 계속 고민하다 보면 더 이상 복잡도가 줄어들 수 없는, 다시 말해 그 문제를 처리하는 데 있어서 속도가 더 이상 빨라질 수 없는 알고리즘이 등장할 수 있어요. 이걸 ‘최적화 알고리즘’이라고 해요. 최적화 알고리즘이 바로 한 문제를 해결하기 위해 가장 좋은 알고리즘이라 할 수 있답니다.

 

 

단, 시간복잡도만으로 알고리즘을 판단하기 어려울 때도 있어요. ‘1부터 10까지의 수를 정렬하라’처럼 해결해야 할 데이터의 수가 너무 적으면 거품 정렬처럼 적은 양의 명령어로 간단하게 만든 알고리즘이 더 좋은 방법이에요. 시간이 오래 걸리더라도 더 정확한 답을 내어놓아야 할 문제도 시간복잡도를 고려할 필요가 없답니다. 지금까지 다양한 알고리즘을 다루어 보았어요. 다음부터는 우리가 생각지도 못했던 재미있는 알고리즘과 프로그램의 예시를 차례차례 소개할게요.