개발일지

sort vs stable_sort 개요 데이터를 정렬할 때 동일한 값들이 존재하는 경우가 발생할 수 있다. 이때, 우리가 사용하는 일반적인 정렬 알고리즘은 동일한 값들의 순서를 보장하지 않아서, 정렬 후의 순서가 원래의 순서와 다를 수 있다. 예를 들어, 이름으로 사람들을 정렬한 후, 나이로 다시 정렬하면 나이가 같은 사람들의 상대적인 순서가 정렬된 후에 변경될 수 있다. 본문 C++ 표준 라이브러리에는 정렬 함수로서 std::sort()와 std::stable_sort()가 존재한다. 이 두 함수는 기본적으로 배열 또는 벡터의 시작과 끝 위치를 인자로 받으며, 선택적으로 비교 함수를 추가하여 사용할 수 있다. 둘 모두 시간 복잡도는 평균적으로 O(n log n)으로, 대략적으로 n log n 번의 비..

문제설명 입출력 예제 개념 원본 수열에서 정렬을 적용한 후, 각 원소가 원래 있던 위치에서 어떤 위치로 이동하였는지 확인하는 문제다. 즉, 원본 수열의 원소들이 정렬된 후의 위치 값을 찾는 문제다. 유의해야 할 점은, 중복된 원소의 값을 처리하는 것이다. 이는 동일한 원소의 경우 원본 수열에서 사전순으로 앞서는 것을 출력해야 한다는 것을 의미한다. 따라서 각 원소의 값을 그 원소의 원래 위치와 함께 저장하는 pair 자료형을 사용하여 해결할 수 있다. 또한, 오름차순을 정렬할 때 정렬 후에 동일한 값의 원소들 사이의 상대적인 순서를 유지하기 위해 stable_sort를 사용해야 한다. 풀이 #include #include #include using namespace std; bool custom(pair..