0. 정렬 문제

알고리즘 문제는 컴퓨터 분야에서 중요하게 여기는 문제 중 하나로, 여러 데이터들이 주어졌을 때 "최적의" 자원으로 이를 나열하는 문제다. 정렬의 기준은 숫자의 크기가 될 수도 있고, 문자의 순서도 될 수가 있으며, 이런 다양한 상황을 얼마나 효과적으로 해결할 수 있느냐가 문제의 핵심이다.

 

왜 정렬을 해야할까? 그 이유는 탐색을 위해서다. 수백만, 수천만 개가 넘어가는 데이터중 원하는 데이터를 효과적으로 찾는 강력한 탐색 알고리즘인 이진 탐색은 데이터가 정렬이 되어있는 조건 하에 동작한다. 정렬된 데이터의 특징은 특정 값의 오른쪽은 무조건 크거나 같은 값이 있으며, 왼쪽에는 작거나 같은 값이 있다. 때문에 한 번의 탐색으로 데이터의 절반을 추려낼 수 있고, 이는 탐색시간의 감소로 이어진다. 이러한 이유로 컴퓨터에서 정렬을 하는 가장 큰 이유가 바로 이 이진 탐색이 가능한 데이터를 만들기 위해서이다.

 

알고리즘에 있어 자원은 두가지인데, 사용한 시간과 사용한 공간으로 알고리즘의 최적도를 판단한다. 물론 각각의 환경과 조건에 따라서 그 기준이 달라질 수 있으나, 보다 더 적은 시간과 공간을 사용한 알고리즘이 최적의 알고리즘이다. 이를 객관적인 지표로 나타낸것이 시간복잡도와 공간복잡도로, 코드의 진행에 따라 사용하게 되는 시간/공간적 용량을 수학적인 표기로 나타낸 것이다.