챕터5-4. 정렬 | 문제풀이(1)

정렬을 적용한 문제풀이

# N개의 수를 입력받아서 정렬하는 문제
- https://www.acmicpc.net/problem/2751 

- 퀵 정렬 직접구현, 병합 정렬 직접구현,  STL sort함수 사용 3가지 방법으로 풀이를 진행하였음

# (x, y) 좌표 정렬하기 문제
- https://www.acmicpc.net/problem/11650
- 아래의 여러가지 방법으로 정렬할 수 있음
   1) pair, vector, sort 사용
   2) struct, vector, sort ( , , 비교함수) 사용

   3) struct, vector, sort( , , 람다함수)
   4) struct, vector, sort, 연산자 오버로딩

 

# (x, y) 좌표 정렬하기2 문제
- https://www.acmicpc.net/problem/11651
- 바로 위 문제의 풀이 방법을 적용하여 해결 가능
   1) pair, vector, sort 사용 : first <-> second 를 뒤바꿔 입력받아 정렬한뒤 출력 때 다시 뒤집어 출력하는 방식
   2) pair, vector, sort ( , , 비교함수) 사용

   3) pair, vector, sort( , , 람다함수)
   4) 바로 위 문제에서 사용한 struct를 이용한 해결방법 모두 적용 가능
   * pair는 연산자 오버로딩 불가

 

# Stable Sorting(안정 정렬)

- stable sorting이란 같은 것이 있는 경우에 정렬하기 전의 순서가 '항상' 유지되는 정렬 알고리즘이다.
   (가끔 되기도 하고 아니기도 한 것들은 stable 알고리즘이라 부르지 않는다.)
ex) 7&    5*   2$   5& 를 카드 번호가 증가하는 순서대로 정렬한다면
     2$   5*   5&   7& 또는 2$   5&   5*   7& 가 될 수 있을 것이다. 
     이 때 '항상' 전자같이 같은 번호가 있는 경우에 처음 입력과 같은 순서로 유지되는 알고리즘을 stable 정렬 알고리즘이라 한다.
- O(NlogN) 정렬 알고리즘 중에서는 병합 정렬(Merge Sorting)이 Stable에 해당됨
- O(N^2) 정렬 알고리즘 중에서는 버블 정렬(Bubble Sorting)이 Stable에 해당됨
- STL에는 stable_sort 알고리즘을 사용하면 됨(사용 방법은 sort함수랑 같음)
   동일값의 경우 처음 입력순서는 유지하면서 어떤 한 변수만 비교하여 정렬되도록 할땐 stable_sort( , , 비교함수 or 람다함수)

 

# 나이순 정렬 문제
- https://www.acmicpc.net/problem/10814 

   1) STL의 sort_stable(, , 나이만 비교하는 비교함수) 을 사용하거나, 
   2) 구조체에 나이, 이름 이외에 가입순서를 변수로 넣어 비교함수로 sort( , , 비교함수 or 람다함수)하면 됨.

 

# 국영수 문제
- https://www.acmicpc.net/problem/10825

   1) 구조체와 sort( , , 비교함수)를 사용한 방법 -> 비교함수를 연습하기 좋은 문제
   2) tutple 을 사용해 중첩된 if문을 없앤 방법

 

# 수 정렬하기 3 

- https://www.acmicpc.net/problem/10989

- 입력받은 수를 전부 다 입력 받아서 저장하게 되면 제한된 8MB의 메모리를 초과해버린다.
   숫자를 카운트 해두었다가 표준출력으로 출력만 해주는 방식을 사용해야한다.
   (10^7 * 4byte = 40MB이므로)