정렬

[C++] std::map을 value 기준으로 정렬하기

std::map 정렬map의 자료구조는 기본적으로 key 값 기준 오름차순 기반 정렬을 하고 있다template , // map::key_compare class Alloc = allocator > // map::allocator_type > class map; 만약 우리가 key 값 기준 내림차순으로 변경하기 위해선 3번째 인자에 greater()를 넣어주면 된다// 키, 데이터, comparemap> m;value 값 기반 정렬하기map에는 정렬 함수가 따로 없어서, vector를 활용해야한다. 구체적으로, map은 tree형태로 되어져있고, tree 형태를 만드는 과정에서 key을 기준으로 정렬을 한다. 완성된 tree를 ..

[C++] set, map 정렬 기준 바꾸는 방법

C++ STL에서 제공하는 set, map, multiset, multimap 등의 컨테이너는 자동으로 데이터를 정렬된 상태로 유지시켜 준다. 그래서 이러한 컨테이너에 데이터를 넣고 그대로 출력하기만 하면 오름차순으로 정렬된 데이터를 얻을 수 있지만 가끔은 내림차순 정렬이 필요하거나 내가 원하는 방식대로 정렬되어야 하는 경우도 생긴다. set의 템플릿 (template)을 살펴보면 다음과 같이 되어 있다template , class _Alloc = allocator> _Kty 부분은 흔히 사용하는 키 타입을 설정하는 부분이다. 우리가 봐야 할 부분은 _Pr이다 기본 값으로 less가 설정된 모습을 볼 수 있는데 이 less는 아래와 같이 정의되어 있다template struct less { _CXX..

[C++] map value sort - 맵 값 정렬

Map 컨테이너에서 처음 선언하는 방식의 따라 Key 기준으로 오름차순, 내림차순을 지정할 수 있지만 만약 Key가 아닌 Value를 비교하여 정렬을 하고 싶을 경우라던지 단순히 오름차순, 내림차순이 아닌 특정 조건에 의하여 정렬을 하고 싶을 경우 Map을 Vector로 변환한다음 Vector에서 정렬을 하던것처럼 해주면 된다. #include #include #include #include using namespace std; typedef pair ii; int main() { map map; map[5] = 20; map[2] = 50; map[3] = 10; map[4] = 40; map[1] = 30; map[6] = 60; for (auto it : map) { cout

[SQL] 테이블 생성, 입력, 조회 및 정렬

1. 테이블 생성(CREATE TABLE) 및 데이터 입력(INSERT) CREATE TABLE emp_table ( emp_id NUMBER NOT NULL, emp_name VARCHAR2(100) NOT NULL, gender VARCHAR2(10) NULL, age NUMBER NULL, hire_date DATE NULL, etc VARCHAR2(300) NULL, PRIMARY KEY (emp_id) ); INSERT INTO 테이블 명 VALUES (값1, 값2, ...); INSERT INTO emp_table (emp_id, emp_name, gender, age, hire_date) VALUES (1, '홍길동', '남성', 33, '2018-01-01'); INSERT INTO emp..

sort() 함수에서 쓰여지는 정렬 알고리즘 (Intro 인트로, Tim 팀)

일반적으로 시간 복잡도를 기준으로 sort 알고리즈므이 성능을 판단하지만, 실제로는 지역성이나 실 데이터의 분포 등 고려할 것들이 많다. 언어마다 default로 사용하는 sort들이 정해져있다. C++ : Intro Sort c++의 std::sort로 사용되고 퀵 정렬, 삽입 정렬, 힙 정렬로 이루어져 있다. 특징 기본적으로 퀵 정렬로 시작을 한다. 정렬할 element가 Threshold(일반적으로 16) 미만일 때는, 삽입 정렬로 수행된다. 재귀 depth가 정렬되는 element 수(n)과 비교해 log N보다 많아지면 힙 정렬로 수행된다. 퀵, 삽입 정렬은 지역성의 이점을 얻는 알고리즘(배열의 경우)으로 유명하다. 특히, 삽입 정렬은 참조 지역성을 아주 잘 만족한다고 한다. 삽입 정렬의 경우 ..

[C++] Radix Sort (기수 정렬)

기수정렬은 정말 신기하게도 비교를 하지 않고 정렬을 하는 방법이기에 시간 복잡도가 O(n)이다. 구체적인 정렬 법을 알기 전에 이름인 '기수'가 뭔지 부터 알아보자. 여기서 '기수'라는 것은 '자릿수'를 의미한다. 자릿수로 뭘 어떻게 하는 것일까?? 방법은 다음과 같다. 1. 1의 자릿수를 보면서 각각의 버킷에 알맞게 담아준다. 버킷에서 순차적으로 뺀다면 1의 자릿수에 맞게 정렬이된다. 2. 1)에 의해서 정렬된 배열에서, 10의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 3. 2)에 의해서 정렬된 배열에서, 100의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 4. 최대 자릿수까지 계속해서 반복한다.. 구체적인 과정을 알아보자. 먼저 최대자릿수 까지 위의 과정을 반복해야 하므로 우리는 최대..

각 정렬의 특징 및 장단점 & 시간복잡도 + 코드

선택정렬 (Selection Sort) 선택정렬은 앞에서부터 차례대로 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬 방법이다. 코드가 직관적이기에 구현도 비교적 간단하다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여준다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준..

VSCode에서 코드 자동 정렬하는 법

방법 1 (수동) 오른쪽 상단 File -> Preferences -> Keyboard Shortcuts 클릭 검색 창에 format을 검색한다. format document에 표시되어있는 keybinding 단축기를 사용하면, vscode에서 자동으로 지원하는 python formatting을 사용할 수 있다. Shitf + Alt + F 단축키는 사람마다 다를 수 있다. 방법 2 (자동) 오른쪽 상단 File -> Preferences -> Settings 클릭 User > Text Editor > Formatting 클릭 Format On Paste, Format On Save, Format On Type 체크 Format On Paste : 코드를 붙여넣기 했을 때, 자동으로 코드를 정렬해준다. ..

구조체 또는 클래스 관련 정렬 (sort 함수)

구조체 또는 클래스는 항상 연산자 오버로딩을 해줘야하고 클래스명으로 가야한다. struct Student { int id, pow; char team; Student(int a, char b, int c) : id(a),team(b),pow(c) { } bool operator(const Student& b) const { return pow > b.pow; } }; 여기서 pow 기준으로 정렬할텐데 이때 algorithm 헤더파일 내에 sort 함수를 사용하고 pred 인자로 해당 연산자 오버로딩 함수를 보내주면 된다. 디폴트 값 : less(); vector st; // pred 템플릿 인자로 무조건 클래스명으로 줘야한다. sort(st.begin(), st.end(), greater()); less..

C 정렬 코드

선택 정렬 #include int size; // 배열의 크기 void selectionSort(int a[], int size) { int t, temp; printf("\n정렬할 원소 : "); for (t = 0; t = 1) { for (int i = 0; i >", interval); for (t = 0; t < inde..