#include <iostream>
using namespace std;
void insertionSort(int*arr, int n) {
for (int i = 1; i < n; i++) {
int j;
int key = arr[i]; //key값 복사
for (j = i - 1; j >= 0 && arr[j] > key; j--) {
arr[j + 1] = arr[j];
}
arr[j+1] = key; //앞선 for문에서 j가 감소되었기 때문에 1더한 자리가 맞음
}
}
int main(){
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
insertionSort(arr, n); //삽입 정렬
for (int i = 0; i < n; i++) {
cout << arr[i]<<'\n';
}
return 0;
}
★이 문제는 기본적으로 버블 정렬, 삽입 정렬로 풀 수 있다. 버블 정렬은 항상 n^2이고, 삽입 정렬은 그나마 최선일 경우 n이고 나머지가 n^2이기 때문에 삽입 정렬로 구현하였다. 자꾸 선택 정렬이랑 삽입 정렬을 헷갈리는데, 선택 정렬은 말 그대로 배열 중에서 최솟값을 선택하여 첫 번째 자리에 놓고, 그다음 최솟값을 두 번째 자리에 놓고... 하는 식이다.
삽입 정렬은 2번째 원소부터 전체 for문을 실행하여 key 값으로 복사하여 두고 새로운 for문으로 그 앞의 원소와 비교한다. 비교해서 원하는 순서와 다르면 그 앞 원소랑도 비교하여서 순서가 맞을 때까지 앞으로 끌고 나간다. 이때 j는 뒤로 밀리기 때문에 arr[j+1]=arr[j]가 되는 것이다. 또한 여기서 for문 종료 조건도 주의해야 하는데, j=i-1부터 하여 감소해나가니까 j>=0일 때까지, 거기에 추가로 key값 보다 클 동안(순서가 맞지 않는 동안) 반복해 나간다.(오름차순 기준) 안쪽 for문에서 j들을 뒤로 다 밀었으면 나오고 나서 arr[j+1]=key를 한다. 이러기 위해서 j는 상위 변수로 정의해 줘야 ㅎ하며, 앞선 for문에서 j가 --(후위 감소)로 for문을 탈출할 때 한번 더 감소가 되었으니 +1을 한 자리가 맞다.
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int j;
int key = arr[i];
for (j = i - 1; j >= 0 && arr[j] < key; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
int main(){
int n, cut=0;
cin >> n >> cut;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
insertionSort(arr, n);
cout << arr[cut-1];
return 0;
}
☆이 문제는 내림차순으로 정렬해야 하므로 삽입 정렬의 안쪽 for문 종료 조건만 약간 수정하면 된다. j>=0 && arr[j]>key : 오름차순 (key값 보다 왼쪽에 있는 arr[j]가 큰 동안 뒤로 밀리면 작은 수가 왼쪽 배치됨) j>=0 && arr[j]<key : 내림차순 (key값 보다 왼쪽에 있는 arr[j]가 작은 동안 뒤로 밀리면 큰 수가 왼쪽 배치됨)
#include <iostream>
#include <algorithm> //sort() 함수
using namespace std;
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr + n);
for (int i = 0; i < n; i++) {
cout << arr[i] << "\n";
}
return 0;
}
★이번 문제는 수가 상당히 커서 전과 같이 O(n^2)의 시간이 걸리는 정렬로 하면 시간 초과가 난다. 그래서 <algorithm> 헤더에 내장되어 있는 sort() 함수를 쓸 수 있는데, 이 함수가 힙 정렬, 병합 정렬과 같이 O(nlogn)이 걸린다. 그런데 이걸 사용해도 시간이 꽤 걸려서, c++에서 시간을 단축시킬 수 있는 코드를 더 추가하였다. 기존에도 endl 대신 \n을 사용하고 있었는데 (endl은 개행+내부 버퍼 비움까지 해서 느림) 여기에 표준 스트림 동기화 끄는 거까지 할 수 있다고 한다. c++과 c의 표준 스트림들의 동기화를 끄게 되면, 둘 사이에 입출력 순서가 보장되지 않아서 두 문법을 섞어 썼을 때 순서가 뒤섞여 나올 수 있는 등 안정성이 보장되지 않는다. 하지만 알고리즘 문제를 풀 때는 그렇게 혼용해서 쓰는 경우가 딱히 없는 데다 이걸 하면 시간이 확실히 줄어들 수 있기 때문에 주로 쓴다고 한다. 아래서부터 삽입정렬로 시도 -> 그냥 sort함수만 썼을 때 -> 표준스트림 동기화 끄는 코드 추가했을 때
#include <iostream>
using namespace std;
//병합 정렬
void merge(int* arr, int first, int mid, int last) {
int* sort = new int[last - first + 1];
int i = first; //first arr index
int j = mid + 1; //second arr index
int k = 0; //sort arr index
while (i <= mid && j <= last) {
if (arr[i] <= arr[j]) //오름차순으로 sort에 복사
sort[k++] = arr[i++];
else
sort[k++] = arr[j++];
}
if (i <= mid)
while (i <= mid) sort[k++] = arr[i++];
else
while (j <= last) sort[k++] = arr[j++];
for (i = first, k = 0; i <= last; i++, k++) {
arr[i] = sort[k];
}
delete[] sort;
}
void partition(int* arr, int first, int last) {
if (first < last) {
int mid = (first + last) / 2;
partition(arr, first, mid);
partition(arr, mid + 1, last);
merge(arr, first, mid, last);
}
}
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
partition(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << "\n";
}
delete[] arr;
return 0;
}
★병합 정렬, 또는 합병정렬은 분할정복 알고리즘으로서 언제나 O(nlogn)의 시간을 갖는다. 이번 문제도 수가 크길래 한번 병합 정렬을 해봤으나... (참고: https://kbw1101.tistory.com/48)
역시 임시 배열이 추가로 필요한 병합 정렬로 하니 메모리 초과가 떴다. + 그냥 sort함수로 해도 메모리 초과가 발생한다.
사실 이번 문제는 카운팅 정렬을 이용하라고 이미 힌트가 주어졌긴 하다. 근데 찾아봐도 뭔 소린지 이해하기 귀찮아서 그냥 위 방법으로 했는데... ㅇㄴ 그냥 다시 찾아봐야겠다
카운팅 정렬
#include <iostream>
using namespace std;
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
int arr[10001] = {0};
for (int i = 0; i < n; i++) {
int a;
cin >> a;
arr[a] += 1; //해당 숫자를 index로 하는 칸에 카운트 처리
}
for (int i = 1; i <= 10000; i++) {
for (int cnt = arr[i]; cnt > 0; cnt--) {
cout << i << '\n';
}
}
return 0;
}
카운팅 정렬로 구현하니 드디어 메모리 초과에서 벗어났다. 생각해 보니 수의 개수가 천만 개라서 이를 전부 배열에 저장하려면 상당한 메모리가 필요할 것이다(...) 따라서 약간 해쉬느낌으로 구현하는 게 카운팅 정렬이었다.
일단 각 수의 범위는 1~10000이므로 10001개의 배열을 생성한다.(0인 숫자는 안 나온다 했으므로) 동적할당이 아니니까 당연하게도 delete가 필요 없다... 안 지워서 계속 오류 났었음ㅋㅋ 또한 다 0으로 초기화를 해주자. 나중에 카운트할 때 쓰레기 값이 들어오면 또 오류 날 거 같기 때문에,,,
이 상태에서 n까지 입력받을 때 해당 입력 값을 인덱스로 갖는 칸에 카운트 처리 (++, +=1)를 한다. 그다음 출력 for문에서는 1~10000칸의 배열을 반복하며 그 칸 각각마다 다시 for문으로 카운트를 센다.
*** 예제 입력에 대해서 카운팅 정렬을 한 결과를 표로 표현하면 이런 느낌이다. 예제 입력: 10개의 수(5, 2, 3, 1, 4, 2, 3, 5, 1, 7)
0
1
2
3
4
5
6
7
8
9
X
1
1
1
1
1
1
1
1
1
1
사실 그림판으로 개대충 그려가면서 풀었는데 그걸 올리자니 쪽팔려서 다시 표로 정리함() 아무튼 이렇게 해서 카운팅 정렬을 공부해 볼 수 있었다~.~
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(int a, int b) {
return a > b; //먼저 들어간 수가 더 큼 == 내림차순
}
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, i;
cin >> n;
int arr[10];
for (i = 0; n > 0; i++) { //자릿수 분해해서 배열 저장
arr[i] = n % 10;
n /= 10;
}
sort(arr, arr + i, compare); //정렬 조건 추가
for (int j = 0; j < i; j++) {
cout << arr[j];
}
return 0;
}
★sort 함수는 다음과 같이 쓰인다. sort(arr, arr+n); 이렇게만 하면 기본적으로 오름차순으로 정렬된다. 3번째 인자로 조건을 추가하여 다르게 정렬시킬 수 있다. 아무 이름이나 붙이고 그 이름으로 bool형 함수를 만든다. 그리고 이때 받는 매개 변수가 왼쪽부터 순서대로 들어오는 순이다. 그러니까 return으로 a> b면 왼쪽에 있는 a가 b보다 크다는 거니까 내림차순이 되고, a <b면 오름차순이 되는 것이다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, x, y;
cin >> n;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
cin >> x >> y;
v.push_back({ x,y });
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
cout << v[i].first << ' ' << v[i].second << '\n';
}
return 0;
}
★이번 문제에서는 vector STL의 사용법과 sort의 특징을 알 수 있다. vector<>에 pair<>를 넣음으로써 쌍으로 이루어진 좌표를 배열 형태에 자동 저장할 수 있다. 따라서 vector는 편하지만 자동 메모리 할당 배열이기 때문에 메모리를 많이 차지하여 낭비가 있을 수 있다는 단점이 있다. 왠지 다른 것보다 조금 더 많아진 메모리 vector 객체에 push_back을 함으로써 변수를 저장할 수 있다. 이때 pair형태이기 때문에 v.push_back(make_pair(x, y)); 로 하거나 위처럼 쌍이라는 의미로 {중괄호}로 묶어서 바로 저장할 수 있다.
sort를 할 때는 시작, 끝을 인자로 넣어야 하므로 begin(), end()로 한다. 중요한 점은, 이번 문제의 조건이 x를 기준으로 오름차순, 동일하면 y를 기준으로 오름차순이라는 것인데 이는 vector나 구조체처럼 쌍으로 인자를 저장한 배열을 한 번에 전달하면 알아서 그렇게 정렬해 준다는 것이다. 물론 여기서 순서를 바꾸고 싶으면 앞선 문제처럼 비교 조건을 추가하면 된다.
반복문으로 vector 쌍을 출력하고자 할 땐 객체[index].first <- 이런 식으로 first, second 변수를 불러올 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(pair<int, int>p1, pair<int, int>p2) {
if (p1.second != p2.second) {
return p1.second < p2.second;
}
else {
return p1.first < p2.first;
}
}
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, x, y;
cin >> n;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
cin >> x >> y;
v.push_back({ x,y });
}
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < n; i++) {
cout << v[i].first << ' ' << v[i].second << '\n';
}
return 0;
}
★이 문제가 앞서 말한 대로 조건을 추가해줘야 하는 문제이다. sort에다 3번째 인자로 조건함수 이름을 넣고, 위에 bool타입의 조건 함수를 만든다. 여기서 비교하고 싶은 매개변수는 pair쌍이기 때문에, pair<int, int>의 객체 2개를 매개변수로 가지면 된다. 그리고 문제 조건대로 y가 다르면 y순으로 오름차순, 같으면 x순으로 정렬하도록 비교하여 return 한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(string a, string b) {
if (a.length() == b.length()) {
return a < b; //사전순
}
else {
return a.length() < b.length(); //길이순
}
}
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<string> v;
for (int i = 0; i < n; i++) {
string str;
cin >> str;
v.push_back(str);
}
sort(v.begin(), v.end(), cmp);
cout << v[0] << '\n';
for (int i = 1; i < n; i++) {
if (v[i] == v[i - 1]) continue;
cout << v[i] << '\n';
}
return 0;
}
★단어의 길이순, 사전순으로 정렬하기 위해 vector에 string을 담고 sort로 조건 함수를 추가한다. 길이가 같으면 그냥 string 객체 1 < string 객체 2 (오름차순)으로 return 하고, (여기서 bool 타입이기 때문에 반드시 비교형태로 return 한다. 그냥 객체만 return하면 안됨) 길이가 다르다면 객체1.length() < 객체2.length() 로 return한다.
그리고 또 하나 중요한 점은 중복인 경우 출력하면 안 되는데, 이는 2가지 방법으로 해결할 수 있다. 1. 입력받을 때부터 find함수로 중복을 찾아서 제외시키기 - if (find(v.begin(), v.end(), str) == v.end()) 면 중복이 없는 것이다. find 함수는 결과가 없을 시 v.end()를 반환하기 때문이다.
2. 정렬하고 나면 중복은 연달아 붙어있으니까, 출력할 때 앞뒤로 비교해서 같으면 continue 하기 - 여기서 계속 배열의 범위를 벗어나는 오류를 겪었다... 처음엔 아래같이 코드를 작성했는데, for (int 0 = 1; i < n; i++) { if (v[i] == v[i + 1] && i+1 < n) continue; cout << v[i] << '\n'; } 저렇게 i+1 <n일 때라는 조건을 추가했음에도 불구하고 범위 벗어남 오류가 떴다. 그래서 반대로 이렇게 짰다. cout << v[0] << '\n'; for (int 0 = 1; i < n; i++) { if (v[i] == v[i - 1]) continue; cout << v[i] << '\n'; } 처음은 일단 출력하고 두 번째부터 그전거랑 비교하는 형식이다. find방법과 이 방법 둘 다 해보면 역시나 find가 시간이 훨씬 걸린다는 것을 알 수 있다. 아래부터 순서대로 find방법 -> 범위벗어남 오류(...) -> 마지막 방법
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(pair<int, string> a, pair<int, string> b) {
return a.first < b.first;
}
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<pair<int, string>> v;
for (int i = 0; i < n; i++) {
int age;
string name;
cin >> age >> name;
v.push_back({ age, name });
}
stable_sort(v.begin(), v.end(), cmp);
for (int i = 0; i < n; i++) {
cout << v[i].first << ' ' << v[i].second << '\n';
}
return 0;
}
★이번 문제의 중요한 조건은, 나이순으로 정렬하되 만약 나이가 같으면 '먼저 들어온 순서 그대로' 정렬을 해야 한다는 것이다. 처음엔 그냥 sort를 썼다가 틀렸다. 그래서 찾아보니, sort는 퀵정렬로 구현되어 있어서 stable 한 정렬이 아니다. 첫 번째 인자를 기준으로 정렬할 때 순서가 그대로 된다고 보장할 수 없다. (만약 첫번째 인자가 같다면 순서대로 나열되어야 하는데, 퀵정렬의 경우 얘네들을 왔다갔다 하면서 정렬하기 때문에 순서가 뒤섞임) 반대로 stable_sort는 병합 정렬로 구현되어 있어서 안정적으로 순서가 보장된다.
★이 문제는 처음엔 아래 그림과 같이 풀었다. vector에 첫번째 원소로 들어온 순서(인덱스), 두 번째 원소로 좌표값을 저장한 다음 이를 정렬한 뒤 새로운 벡터에 기준대로 저장하는 것이다. 하지만 이 방법대로 하니 중복된 값을 같은 인덱스 값으로 저장하기가 상당히 어려웠다. (계속 오류 나거나 다른 값 나옴,,,,,,)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
//c, c++의 표준 스트림 동기화 끄기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<int> v2(v); //중복제거할 벡터에 복사
sort(v2.begin(), v2.end()); //오름차순 정렬
v2.erase(unique(v2.begin(), v2.end()), v2.end()); //중복 제거
for (int i = 0; i < n; i++) {
auto it = lower_bound(v2.begin(), v2.end(), v[i]);
cout << it - v2.begin() << ' ';
}
return 0;
}
일단 새 벡터를 만드는 과정부터 살펴보면, 우선 정렬된 복사 벡터를 unique로 처리하고 있다. 이 unique함수는 연속으로 중복되는 원소를 처리해 준다. 연속되어 있지 않으면 할 수 없고, (그래서 정렬 먼저 함) 배열의 크기는 그대로 하기 때문에 뒤에는 원본이 유지된 채로 채워진다. ex) 10 10 20 30 20 20 50 -> 10 20 30 20 50 20 50
그리고 원본이 유지된 첫 번째 원소의 주소값을 반환한다. -> 20 따라서 반환 값을 이용해 erase로 지워줄 수 있다. v2.erase(원본유지 첫번째 주소값, v2.end()); ->이렇게 하면 원본 유지 부분을 완벽히 다 지워줄 수 있는 것이다.
이렇게 중복이 사라진 복사 벡터 v2를 이용하여, 반복문을 돌리면서 이번엔 lower_bound() 함수를 쓴다. lower_bound(begin, end, value)처럼 lower_bound 함수는 [begin, end) 안의 원소들 중 value보다 크거나 같은 첫번째 원소를 반환한다. 없을 경우 end를 반환한다. 즉, 미리 정렬되어 있어야 하며, value를 기준으로 하한선을 반환한다는 의미이다. 이때 반환 값은 주소 값이므로 따로 auto it 등으로 저장해서 시작 주소 값을 빼줘야 인덱스 값(순서)을 구할 수 있다.
이 과정들을 그림으로 표현하면 아래와 같다. 이런 거 하려고 아이패드도 들고 왔는데 귀찮아서 굳이 굳이 그림판으로 그린게 참()
아무튼 이번 단계 풀면서 vector, pair, sort, unique, erase 등을 공부할 수 있었다,,,
