*이 글은 2022년 1월~2월 노션으로 진행한 알고리즘 스터디를 옮긴 글입니다. 나동빈 저자 이것이 취업을 위한 코딩테스트다를 사용해 학습했습니다.
220211 정렬 개념 정리(02.12내용추가)
- 선택정렬
-
항상 가장 작은 원소를 선택해 가장 앞으로 보내는 정렬 알고리즘
-
시간복잡도 O(N^2)
-
효율성은 떨어지지만 특정 리스트에서 가장 작은 데이터를 찾는 일이 잦으므로 소스코드는 자주 작성해보기→손코딩도 해보자!
7 5 9 0 3 1 6 2 4 8 0 1 2 3 4 5 6 7 8 9 7 5 9 0 3 1 6 2 4 8
데이터개수 선택정렬 퀵정렬 stl n=100 0.0123 0.00156 0.00000753 n=1000 0.354 0.00343 0.0000365 n=10000 15.475 0.0312 0.000248 #include<iostream> using namespace std; int n = 10; int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 }; int main() { for (int i = 0; i < n; i++) { int min_index = i; // 가장 작은 원소의 인덱스 for (int j = i + 1; j < n; j++) { if (arr[min_index] > arr[j]) { min_index = j; } } //제일 작은 인덱스 찾은 뒤에 swap(arr[i], arr[min_index]); // 스와프 } for (int i = 0; i < n; i++) { cout << arr[i] << ' '; } }
-
- 삽입정렬
-
선택한 데이터의 이전 데이터는 모두 정렬되었다고 가정함
-
선택한 데이터와 정렬된 앞 데이터를 비교하여 선택한 데이터보다 작은 값을 만나면 그 앞에 선택한 데이터를 끼워넣음
-
시간복잡도 O(N^2). 단 정렬이 거의 완료된 데이터를 정렬하려고 할 경우 최소 O(N)의 시간복잡도를 가짐.
-
즉 이미 정렬이 어느정도 된 자료의 경우 삽입정렬이 가장 큰 효율을 낼 수 있음
7 5 9 0 3 1 6 2 4 8 0 1 2 3 4 5 6 7 8 9 7 5 9 0 3 1 6 2 4 8 #include<iostream> using namespace std; int main() { int n = 10; int array[10] = { 7,5,9,0,3,1,6,2,4,8 }; for (int i = 1; i < n; i++) { for (int j = i; j > 0; j--) { if (array[j] < array[j - 1]) { swap(array[j], array[j - 1]); } else break; } } for (int i = 0; i < n; i++) { cout << array[i] << endl; } }
-
- 퀵정렬*
-
정렬 라이브러리의 근간이 되는 알고리즘.
-
재귀함수로 구현 시 간단히 구현할 수 있음.
-
호어분할 방식에선 가장 첫 데이터를 기준(pivot)으로 설정함.
-
시간복잡도 O(NlogN)←가장 효율적인 정렬방법임
-
그러나 이미 정렬된 리스트를 퀵정렬로 정렬하는 경우 최악의 경우 O(N^2)로 작동함.
-
정리해도 머리에 잘 안들어와서 다시 봐야됨
part1. 피벗을 기준으로 좌/우 데이터를 나눔
피벗을 제외한 가장 왼쪽 데이터와 가장 오른쪽 데이터를 각각 오른쪽/왼쪽으로 비교함. 이때 왼쪽 데이터는 피벗보다 큰 수를, 오른쪽 데이터는 피벗보다 작은 수를 가진 경우를 찾아내서 양쪽이 데이터를 찾은 경우에만 왼쪽과 오른쪽 데이터를 바꿔줌(swap). 이 과정을 반복하다가 왼쪽과 오른쪽이 엇갈린 경우 작은 데이터와 피벗의 위치를 변경함.
part2. 나눠진 좌측 데이터를 다시 피벗을 설정하여 좌/우로 나눔
part3. 나눠진 우측 데이터를 다시 피벗을 설정하여 좌/우로 나눔
7 5 9 0 3 1 6 2 4 8 0 1 2 3 4 5 6 7 8 9 7 5 9 0 3 1 6 2 4 8 pivot left right #include<iostream> using namespace std; int n = 10; int arr[10] = { 7,5,9,0,3,1,6,2,4,8 }; void quickSort(int * arr, int start, int end) { if (start >= end)return; int pivot = start; int left = start + 1; int right = end; while (left <= right) { while (left <= end && arr[left] <= arr[pivot])left++; while (right > start && arr[right] >= arr[pivot])right--; if (left > right)swap(arr[pivot], arr[right]); else swap(arr[left], arr[right]); } quickSort(arr, start, right - 1); quickSort(arr, right +1 , end);//왜 right+1인가 하면 재귀함수이므로 종료조건을 만족시키기 위해서 피벗으로 쓰인 변수가 하나씩 계속 제외돼야 함. } int main() { quickSort(arr, 0, n - 1); for (int i = 0; i < n; i++) { cout << arr[i] << " "; } }
-
- 계수정렬
-
데이터 크기가 제한되어 있고 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 복잡도 O(N+M)을 보임.
-
별도의 리스트 선언 후 그 안에 정렬에 대한 정보를 담음. 앞서 설명한 세개의 방법과 구현 방식이 다름.(값끼리 상대적인 비교가 아님)
-
리스트의 가장 큰 값만큼의 리스트 선언 후(모든 데이터 0으로 초기화) 정렬할 리스트와 새로 선언한 리스트 비교하여 같을 때 1씩 더해줌
#include <iostream> const int MAX_VALUE = 9; using namespace std; int n = 15; // 모든 원소의 값이 0보다 크거나 같다고 가정 int arr[15] = { 7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2 }; // 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화) int cnt[MAX_VALUE + 1]; int main(void) { for (int i = 0; i < n; i++) { cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가 } for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인 for (int j = 0; j < cnt[i]; j++) { cout << i << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력 } } }
-
정렬 라이브러리 사용예제
- 예제
#include<iostream> #include<algorithm> using namespace std; int n = 10; int arr[10] = { 7,5,9,0,3,1,6,2,4,8 }; int main() { sort(arr, arr + n); for (int i = 0; i < n; i++) { cout << arr[i] << " "; } }#include <iostream> #include <algorithm> using namespace std; class Fruit { public: string name; int score; Fruit(string name, int score) { this->name = name; this->score = score; } // 정렬 기준은 '점수가 낮은 순서' bool operator <(Fruit& other) { return this->score < other.score; } }; int main(void) { int n = 3; Fruit fruits[] = { Fruit("바나나", 2), Fruit("사과", 5), Fruit("당근", 3) }; sort(fruits, fruits + n); for (int i = 0; i < n; i++) { cout << '(' << fruits[i].name << ',' << fruits[i].score << ')' << ' '; } }
문제풀이
- 220212 위에서 아래로
- 풀이
- 백터와 sort내장함수 사용하여 간단하게 구현.
- 내림차순 정렬 시 greater<>()를 세번째 인자에 추가하면 된다는 사실 알게 됨. 정리.
- 코드
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { vector<int>data; int a, b; cin >> a; for (int i = 0; i < a; i++) { cin >> b; data.push_back(b); } sort(data.begin(), data.end(), greater<>()); for (int i = 0; i < data.size(); i++) { cout << data[i] << " "; } return 0; }
- 풀이
- 220212 성적이 낮은 순서로 학생 출력하기
- 풀이
- 이거 스터디에서 들었던 pair 사용하면 쉽게 구현 가능할듯?? vector안에 자료형을 pair로 받기
- 근데 구현하다보니 문자열을 first로 받으면 문자열 순서대로 나열하는 문제를 찾아냄.
- 실제 저장되는 자료형은 pair<int, string>형태이고 자료 입력받을 때만 string, int 순서대로 입력받게 수정함.
- pair를 처음 사용하는데 사용방법이 미숙함. 특히 vector안에 넣어서 사용할 때는 정렬하기 위해 first끼리 값을 비교해야 하므로 이름순으로 받는게 아니면 int를 앞에 보내는게 날듯. 경우에 따라 바꿔쓰자.
- *utility stl 사용방법 익숙해지기. 비슷한 문제 나오면 pair 또 써보자.
- map이 key값을 받는다고 알고있는데 그럼 이걸로도 구현할수 있지 않을까...? 사용법 몰라서 패스.
- 생각보다 오래걸림...제한시간 안에 못 풀고 서치함
- 코드
#include<iostream> #include<utility> #include<algorithm> #include<vector> using namespace std; //pair사용이 애매한데 그냥 백터랑 페어 같이 구현할수있을까 int main() { vector<pair<int, string>>data; int a, c; string b; cin >> a; for (int i = 0; i < a; i++) { cin >> b >> c; data.push_back(pair<int, string>(c,b)); } sort(data.begin(), data.end()); for (int i = 0; i < a; i++) { cout << data[i].second << " "; } return 0; }
- 풀이
- 220213 두 배열의 원소 교체
- 풀이
- 이 문제 보자마다 그리디 알고리즘 떠오름.
- 배열A의 합이 최대가 되려면 A의 최소값과 B의 최대값을 비교하여 A의 최소값이 더 작은 경우 바꿔주면 됨.→두 배열 다 정렬하면 쉽게 구할수 있음.
- 코드
#include<iostream> #include<algorithm> using namespace std; int data_a[100000]; int data_b[100000]; int main() { int a, b, c; cin >> a >> b; for (int i = 0; i < a; i++) { cin >> c; data_a[i] = c; } for (int i = 0; i < a; i++) { cin >> c; data_b[i] = c; } sort(data_a, data_a + a); sort(data_b, data_b + a); int min = 0, max=a-1; for (int i = 0; i < b; i++) { if (data_a[min] < data_b[max]) { swap(data_a[min], data_b[max]); min++; max--; } else { break; } } int add=0; **for (int i = 0; i < a; i++) { add += data_a[i]; }** cout << add; }
- 풀이
겉촉속촉