sort

🔗 문제 링크 : https://www.acmicpc.net/problem/10814  문제온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.     입출력 예시     풀이 sort()는 기본적으로 안정 정렬을 지원하지 않기 때문에, 사용하면 틀리게 된다.결국, 입력을 받을 때 인덱스를 같이 저장하거나, 안정 정렬을 지원하는 stable_sort()를 사용해야한다. 아래 코드는 stable_sort()를 사용한 풀이다.#include #include #include using namespace std;struct Member { int age; ..

개인적인 공부 목적으로 정리한 내용입니다.   ☁ 기본적인 사용법과 사용자 정의 비교 함수를 사용한 다양한 예시를 포함하였다.   sort() 함수C++의 sort() 함수는 STL(Standard Template Library, 표준 템플릿 라이브러리)의 알고리즘 라이브러리에 포함된 함수로, 배열이나 벡터와 같은 컨테이너의 요소들을 정렬하는 데 사용된다.지정된 범위에 있는 요소는 기본적으로 오름차순으로 정렬되며, 커스텀(사용자 정의) 비교 함수를 사용하여 다양한 방식으로 정렬할 수 있기 때문에 자주 사용되는 함수다. 🔎  참고로 sort()는 안정 정렬이 아니다! 안정 정렬이란?비교하는 두 값이 동일할 경우 원래의 순서를 유지하면서 정렬한다. sort()경우 안정 정렬을 지원하지 않으므로 안정 정렬을..

문제0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.      입출력 예시    풀이 sort()를 사용하되, 조건은 compare함수를 따른다.compare함수는 두 수를 이어붙인 값을 비교한다.#include #include #include using namespace std;/* 예를 들어, 3과..

🔗 문제 링크 : https://www.acmicpc.net/problem/11931  문제N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램을 작성하시오.     입출력 예시     풀이 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); int N; cin >> N; vector nums; for (int i = 0; i > n; nums.push_back(n); } sort(nums.rbegin(), nums.rend()); for (int i : nums) { cout

🔗 문제 링크 : https://www.acmicpc.net/problem/10989 💣 메모리 초과 메모리 제한이 8MB인게 핵심인 문제다. 퀵 정렬 시도하자마자 바로 컷 당해버렸다!계수 정렬을 이용하는 문제이다. 카운팅 소트Counting Sort라고도 한다.⭐ 그리고 입력받는 자연수들을 굳이 배열로 저장하여 갖고있을 필요도 없다! ⭐최대 1,000,000개의 값이 들어오는데 이 값들을 전부 배열에 저장하면 메모리 초과! 그 후 시간 초과, 출력 초과도.. 마주쳤는데.. 원인과 해결방법은 아래 풀이와 함께 참고하자.  ✒ 카운팅 정렬의 원리 카운팅 정렬은 흥미롭게도 비교 기반 정렬 알고리즘이 아닌 정렬 알고리즘이다. 카운팅 정렬에서 카운트 배열을 사용하는 이유는, 주어진 배열의 각 원소의 출현 ..

버블 정렬(Bubble Sort)을 이용한 풀이(#1)와 algorithm 내장함수를 사용한 간단한 풀이(#2)가 있습니다.  문제배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담..

🔗 문제 링크 : https://www.acmicpc.net/problem/2751  🧨 시간 초과! 처음은 퀵 정렬로 구현하였으나 시간 초과로 실패했다. 두 번째엔 힙 정렬로 바꾸었지만 시간 초과!  #1힙 정렬을 구현하였을 때, 시간초과의 원인은 출력방식에 있었다.cout endl;endl을 "\n"로 바꾸니 힙 정렬 구현 코드의 수정 없이도 바로 통과되었다.(무거운 flush 연산과 관련된 이야기인데, 조만간 따로 정리해 볼 예정이다.) #2설마! 처음에 구현했던 퀵 정렬도 혹시...? 하는 마음에 endl을 "\n"로 바꾸어 시도해 보았지만 여전히 시간초과다.🤣나의 퀵 정렬 구현 코드를 다시 살펴보니, 피벗(pivot)을 랜덤 선택하는 과정을 넣지 않아, 최악의 pivot이 선택되는 듯 하..

🔗 문제 링크 : https://www.acmicpc.net/problem/2750  문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.     입출력 예시     풀이 #1 | 퀵 정렬 (Quick Sort) 구현퀵 정렬(Quick Sort)을 구현한 풀이#include #include using namespace std;/* a와 b를 바꾸어주는 함수 */void swap(int& a, int& b) { int tmp = a; a = b; b = tmp;}/* pivot을 기준으로 벡터를 분할하는 함수 */int partition(vector& vec, int low, int high) { int pivot = vec[high]; int i ..