다양한 정렬 알고리즘의 특성과 메모리 사용 차이를 이해하고 있는지를 봅니다. 단순 이름 나열이 아니라 상황에 따라 어떤 알고리즘이 적합한지 판단력을 평가합니다.
이 질문 뒤에 면접관이 확인하려는 것은 따로 있습니다.
버블 정렬 외에 자주 쓰이는 알고리즘으로는 퀵 정렬과 병합 정렬이 있습니다. 퀵 정렬은 평균 `O(n log n)`이고 추가 메모리를 거의 쓰지 않는 `in-place` 방식입니다. 피벗을 기준으로 양쪽을 나눠 재귀적으로 정렬하는데, 피벗 선택이 나쁘면 최악 O(n²)이 됩니다. 병합 정렬은 항상 `O(n log n)`을 보장하지만, 분할된 배열을 합칠 때 별도 메모리가 `O(n)` 필요합니다. 안정 정렬이 필요하거나 데이터 크기가 크고 순서 보장이 중요할 때 병합 정렬을 사용합니다. 메모리가 제한적인 환경이라면 퀵 정렬, 안정성이 중요하다면 병합 정렬을 선택하는 방식으로 상황에 맞게 골라야 합니다.
알고리즘 선택은 속도만이 아니라 메모리와 안정성을 함께 고려하는 것이 중요합니다.
힙 정렬은 `O(n log n)` 시간복잡도를 보장하면서도 `in-place`로 동작하는 알고리즘입니다. 추가 메모리를 거의 사용하지 않는다는 점에서 퀵 정렬과 비슷하지만, 캐시 효율이 낮아서 실제 속도는 퀵 정렬보다 느린 경우가 많아요. 반면 삽입 정렬은 O(n²) 시간복잡도지만 데이터가 거의 정렬되어 있을 때는 빠르고 추가 메모리도 거의 없이 동작합니다. 데이터 특성에 따라 알고리즘이 달라지는 거예요. 실제로 Python의 내장 정렬은 팀 정렬이라는 방식으로, 삽입 정렬과 병합 정렬을 섞어서 씁니다.
언어 내장 정렬을 믿어도 되지만, 원리를 알면 예외 상황에서 판단이 가능해요. 알고리즘은 이론과 실전을 연결해서 이해하는 게 중요하다고 느꼈어요.
정렬 알고리즘을 메모리 관점에서 분류하면 크게 두 가지로 나뉩니다. 추가 메모리를 `O(1)` 수준으로 쓰는 `in-place` 방식(버블·선택·삽입·퀵 정렬)과 `O(n)` 수준의 추가 메모리가 필요한 방식(병합 정렬)이에요. 병합 정렬은 안정적이고 최악 성능도 O(n log n)이지만, 데이터 크기가 클수록 메모리 부담이 커집니다. 알고리즘 수업에서 실제로 각 알고리즘을 구현해보면서 메모리 사용량이 얼마나 다른지를 직접 측정해봤어요. 같은 데이터를 정렬해도 알고리즘마다 메모리 점유 패턴이 달라서 흥미로웠습니다.
어떤 알고리즘이 좋다기보다 상황에 맞는 알고리즘을 고르는 판단이 중요하다는 걸 배웠어요. 정렬 하나에서도 트레이드오프를 배울 수 있더라고요.
답변에서 흔히 빠지는 것들 — 빠져 있으면 꼬리질문이 깊어집니다.
이 질문에 이어 LG전자 기타 면접관이 던질 가능성이 높은 후속 질문.
이 페이지의 질문·답변·꼬리질문은 유사 직군 채용 시장의 공개된 면접 후기·커뮤니티 게시물을 분석해 구성한 학습 자료입니다. 특정 회사가 실제로 이 질문을 출제했다는 것을 보장하지 않으며, 모든 예시는 우문현답이 직접 작성한 창작물입니다. 해당 회사의 공식 입장과는 무관합니다. 회사 측의 정정 요청이 있을 경우 24시간 이내에 응답·수정합니다.