[코드트리] 정렬 알고리즘 약점 극복 학습 후기

지난 회차 갭체크를 진행하면서 알고리즘 기본 개념을 생각보다 많이 잊고 있다는 것을 느꼈다. 그래서 이번 회차에는 바로 어려운 유형으로 넘어가기보다, 코드트리 레슨을 통해 정렬 알고리즘과 시간복잡도 개념을 다시 복습했다.

 

정렬은 데이터를 특정 기준에 따라 순서대로 나열하는 알고리즘이다. 코딩테스트에서는 단순히 숫자를 오름차순으로 정렬하는 문제뿐 아니라, 다른 알고리즘을 적용하기 전 데이터를 정리하는 전처리 과정으로도 자주 사용된다.

이번 레슨에서는 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등 여러 정렬 알고리즘을 다시 확인할 수 있었다. 예전에는 파이썬의 sort()나 sorted()만 떠올렸는데, 각 정렬 방식마다 동작 원리와 시간복잡도가 다르다는 점을 다시 정리할 수 있었다.

 

예를 들어 버블 정렬, 선택 정렬, 삽입 정렬은 구조는 직관적이지만 일반적으로 시간복잡도가 O(N^2)이다. 반면 병합 정렬과 힙 정렬은 O(N log N)의 시간복잡도를 가지며, 퀵 정렬은 평균적으로 O(N log N)이지만 피벗 선택에 따라 최악의 경우 O(N^2)이 될 수 있다.

 

이번에 특히 좋았던 부분은 코드트리 레슨에서 퀵 정렬의 과정을 그림과 함께 설명해준 점이었다.

 

 

피벗을 기준으로 작은 값과 큰 값을 나누고, 다시 각 구간을 정렬하는 흐름을 시각적으로 볼 수 있어서 예전에 외우듯이 봤던 개념을 다시 이해하는 데 도움이 됐다. 코드에도 주석이 친절하게 달려 있어서 pivot, partition, 재귀 호출의 역할을 따라가기 쉬웠다.

 

실제 코딩테스트에서는 대부분 내장 정렬 함수를 사용하겠지만, 정렬 알고리즘의 원리와 시간복잡도를 알고 있는 것은 중요하다고 느꼈다. 입력 크기가 커졌을 때 어떤 풀이가 가능한지 판단하려면 시간복잡도를 알아야 하고, 코딩테스트를 기반으로 한 면접에서도 잘 대답할 수 있다. 

이번 학습을 통해 정렬은 쉬운 개념처럼 보여도 코딩테스트의 기본기와 연결된다는 것을 다시 느꼈다. 앞으로 문제를 풀 때는 단순히 정렬 함수를 쓰는 데서 끝내지 않고, 정렬 기준이 무엇인지, 시간복잡도는 충분한지, 정렬 이후 어떤 값을 활용해야 하는지를 함께 확인하려고 한다.

코드트리에서 직접 갭체크와 알고리즘 학습을 해보고 싶다면 여기에서 확인할 수 있다.