프로그래머스의 [3차] 파일명 정렬 문제에서 파이썬으로 푼 방식과 똑같이 C++로 문제를 푸는데, 계속 1, 2번을 제외한 테스트케이스가 모두 틀려 의문이 들었다. 질문하기 게시판을 읽어 보았더니, 보통 C++에서 사용하는 sort() 메소드가 불안정 정렬이라서 틀렸을 것이라고 한다. 글에서 말한대로 안정 정렬을 사용하여 푸니 바로 풀렸다. 알고리즘 문제를 풀며 알게 된 안정 정렬과 불안정 정렬. 이를 까먹지 않고자 다루어보려 한다.1. 불안정 정렬이란?불안정 정렬을 설명하기 전, 정렬의 개념부터 알고 가야 할듯하다.정렬이란 데이터 요소를 특정 기준에 따라 순서대로 배치하는 과정을 말한다. 각 언어의 내장 정렬 함수는 기본적으로 숫자나 문자를 오름차순으로 정리하지만, 사용자의 정의 기준에 따른 커스텀 정..

C++에서 키-값 쌍으로 데이터를 관리하는 자료구조는 특이하게 map과 unordered_map 두 가지가 있다.이 두 컨테이너는 얼핏 봐서는 비슷해 보이지만, 내부 구현 방식이나 성능 측면에서 간과할 수 없는 차이점이 존재한다.map과 unordered_map의 차이점과 사용 사례, 성능을 비교해보며 자신의 프로젝트에 어느 자료구조를 쓰는 것이 더욱 적합한지 판단할 수 있도록 해보자.std::mapmap은 내부적으로 균형 이진 검색 트리(BST)를 사용해 데이터를 저장한다.이로 인해 키는 항상 정렬된 상태로 저장되어 요소에 대한 삽입/삭제/검색에 O(log n)의 시간복잡도를 가진다. 추가적인 트리 구조로 인하여 메모리 사용률 또한 높다. map은 보통 키의 정렬이 필요할 때, 범위 기반의 검색이 자주..