이번 스터디 그룹 모임의 주제는 "Sorting Algorithm".
정렬 알고리즘에 대해 공부하다 보니 자연스럽게 시간 복잡도(Time Complexity)에 관해서도 공부하게 되었다.
대량의 데이터를 다루는 업무에 있어서 정렬 알고리즘의 방식에 따라 처리 속도가 상당한 차이를 보일 수 있다는 점을 알게 됐다.
이 글에서는 Python 언어를 통해 [Baekjoon Online Judge] 사이트에 있는 정렬 알고리즘 문제를 풀고 스터디 그룹원들과 함께 리뷰해 보는 과정을 통해 알게 된 점들을 기록해 본다.
정렬 알고리즘(Sorting Algorithm)
정의
원소들을 일정한 순서대로 열거하는 알고리즘.
효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미 있는 결과물을 생성하는 데 흔히 유용하게 쓰인다. [출처: 위키백과 "정렬 알고리즘"]
다른 알고리즘을 최적화(Optimization)
- 이번 스터디를 통해 얻은 가장 큰 깨달음이 바로 이것이다.
최적화란 조건 내에서 가장 효율적인 결과를 이끌어내는 것이라 할 수 있다.
이번에 풀어본 정렬 문제들의 특징이 바로 주어진 조건 내에서 가장 시간 효율적인, 혹은 메모리 효율적인 코드를 작성하는 것이었다.
그동안은 생각해 보지 않았었는데, 여러 정렬 알고리즘이 그 특징에 따라 다른 알고리즘을 최적화해주고 있다는 것을 이번 기회에 알 수 있었다.
문제를 풀면서 느낀 정렬 알고리즘이 최적화를 돕는 간단한 예를 두 가지만 들자면 중앙값 찾기와 최빈값 찾기가 있다.
중앙값 찾기
우선 중앙값을 예로 들면, 중앙값의 정의 자체가 "순서대로 늘어놓았을 때 그들의 한가운데 있는 값"인 만큼 정렬을 이용하여 아래와 같은 간단한 방법으로 구할 수 있다.
- 개의 수가 있고 은 홀수일 때:
- 순서대로 정렬한다.
- 가운데 위치한 값을 찾는다.
하지만 정렬을 이용하지 않는다면 아래와 같은 방법으로 구해야 한다.
- 하나의 원소를 다른 모든 원소와의 크기를 하나씩 비교한다.
- 해당 원소보다 큰 원소의 개수와 보다 작은 원소의 개수가 같다면 중앙값이다.
- 아니라면 다른 원소 하나를 선택하여 위의 과정을 반복한다.
최빈값 찾기
최빈값의 경우 처음에는 for문으로 각 원소의 빈도를 count()로 확인한 후 그 값을 저장한 후 비교했으나, 제한 시간을 초과했다.
이후 "카운팅 정렬" 방식을 활용했더니 여유롭게 제한 시간 내에 최빈값을 찾아냈다.
시간 복잡도(Time Complexity)
하나의 알고리즘이 주어진 문제를 해결하는 데 소요되는 시간
시간 효율의 신경을 쓰면서 문제를 풀다 보니 알고리즘에 따라 소요 시간이 생각보다 차이가 꽤 나는 것을 알게 됐다.
직접 문제를 풀 때는 시간 복잡도 개념을 모른 채 그저 머릿속으로 계산해 볼 때 보다 적은 연산을 하는 방식을 택했다.
이후 시간 복잡도라는 개념을 알게 됐고, 다른 분들은 이 시간 복잡도 개념을 활용하여 보다 신속한 방식을 택하거나 느린 방식을 피하는 식으로 코드를 구성했다는 것을 알게 됐다.
검색해 보니 각 알고리즘 별 시간 복잡도나 어떠한 함수가 가진 알고리즘의 시간 복잡도를 계산해놓은 표가 많이 보였다.
업무에 따라 조건에 맞는 가장 효율적인 알고리즘을 선택하기에 굉장히 유용한 자료인 것 같다.
좀 더 공부해두면 코드를 작성할 때 즉각적으로 활용할 수도 있고, 굳이 생각해 보느라 시간 쓸 필요 없이 잘 정리된 표들을 참고하여 도움을 받을 수 있겠다는 생각이 들었다.
결론
- 알고리즘의 최적화를 위해 정렬 알고리즘을 활용할 수 있다.
- 시간 복잡도를 고려하면 최적화에 큰 도움이 된다.
- 검색하면 시간 복잡도 관련해서 잘 정리된 표가 많이 나온다. 참고하자.
