[알고리즘 #2] Sorting, Searching, Data Structures
Sorting
실제 상황에서 Sorting 이 필요한 경우 내부 라이브러리 사용하는 것이 빠르고 간편하다 (C++) ( sort(시작주소, 끝주소다음)) 입력
#include <algorithm>
ex) vector 정렬
vector<int> v = {4, 2, 5, 3, 5, 8, 3};
sort(v.begin(), v.end()); // sort(시작 주소, 끝 주소다음)
ex) array 정렬
int n = 7;
int a[] ={4,2,5,3,8,3};
sort(a, a+n); // sort(array 시작 주소, 끝주소다음)
ex) string 정렬
string s = "monkey";
sort(s.begin(), s.end()); // string 에서도 begin(), end()함수로 주소 접근 가능
- sort 함수 사용을 위해서는 정렬할 원소들이 각각 비교가능해야 한다.
- C++ 에는 숫자는 크기 순, 문자는 아스키코드 알파벳 순, pair 나 tuple 은 왼쪽 요소가 작은 순서대로 비교 연산자가 정의 되어있다
- 만약 이 비교 기준을 바꾸고 싶을 땐, bool compare 함수를 재정의 한다.
- 사용자 정의 구조체(클래스)에는 비교 연산자가 없으므로 operator < 를 따로 정의해준다.
ex) vector<pair<int, int>> v;
v.push_back((1,5));
v.push_back(2,3));
v.push_back(1,2));
sort(v.begin(), v.end());
// result : [(1,2), (1,5), (2,3)] // 기본 정렬은 왼쪽요소가 작은 순서대로
# 내림차순으로 정렬위해 compare 재정의
bool compare(int i, int j) {return i>j;}
sort(v.begin(), v.end(), compare);
# 오른쪽 요소부터 오름차순으로 정렬위해 compare 재정의
bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
if(i.second() == j.second
return i.first < j.first;
else
return i.second < j.second;
}
대부분의 문제는 sorting 알고리즘을 구현하지 않아도 되지만 예외가 존재한다
ex) 사이즈가 n인 array A가 있다. 해당 array 의 inversion 개수를 출력하는 프로그램을 작성하라
inversion : 두 i < j 일 때, A[i] > A[j] 인 index pair (i,j)
위 sorting algorithm 중에서 inversion 과 직접적인 관계가 있는 알고리즘은 Bubble sort 와 insertion sort 이다.
( 항상 두 페어를 비교한다. 그렇게 모든 페어를 비교하기 때문이다.)
=> O(n^2) 시간 소요
merge sort( O(nlog n))
Merge sort 도중 두 Array A1[1,...,n1] 과 A2[1,...,n2] 를 merge 할 때, A1[i]>A2[j] 라면 A2[j] 와 A[i,...n1] 사이의 모든 element 간에 inversion 이 존재한다.
(A1, A2 는 Sorted array 이기 때문에 A[i,..,n1] 은 무조건 A[i] 보다 크다.(A[i,..n1] > A[i]) 따라서 A1[i] > A2[j] 라면
A1[i,..,n1] > A1[i] > A2[j] 가 성립한다. 따라서 A2[j] 와 A1[i,..n1] 사이 모든 elemet 간에 inversion 존재한다.
* 관련 코드 작성 *
Searching
Searching : Array 등 자료 구조에서 특정 element 찾는 문제이다
1. Linear search( O(n)) : Array 의 모든 원소를 하나씩 살펴보면서 찾는다
2. Binary Search ( O(nlog n) : Array 가 정렬된 경우만 사용할 수 있다.
3. Hashing (O(1)) : 보통 쓸일이 없음
C++ 의 경우 binary_search() 함수 혹은 lower_bound(upper_bound) 이용하여 binary_search 수행할 수 있다.
vector<int> arr = {10, 15, 20, 25, 30, 35);
if(binary_search(arr.begin(), arr.end(), 15))
cout << "15 exists in vector " ;
else
cout << "15 does not exist " ;
cout << lower_bound(arr1.begin(), arr1.end(), 15) - arr1.begin();
//arr 부터 끝까지 탐색하면서 15 이상의 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환
// 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 됩니다
ex) Array 가 아닌 자료구조에서의 BS : Node 가 N개인 tree 가 있다. 각 노드에는 weight 가 있으며, weight 는 tree 의 root 에서 leaf 로 갈수록 증가한다. Node v가 주어졌을 때, v의 ancestor 들 중 weight 가 P이상이면서 root 에 가장 가까운 node 를 구하라 ( 이런 query Q개가 문제에서 미리 주어진다고 하자)
1. O(QN) Solution : 각 query 마다 tree 위로 올라가면서 탐색
Q와 N 범위가 큰경우 N<= 80000, Q<=20000 / 1초 제한 기준으로 TLE
2. O(Q log N) : 모든 쿼리들을 미리 저장한 다음 , 다음 처럼 진행
- DFS 로 모든 노드 탐색 -> O(N)
- 탐색하면서 현재까지 지나간 node 들을 array 에 저장한다.(해당 array 는 sorted)
- 탐색하면서 query node 를 만날 경우 , 현재 저장한 array 에서 lower_bound 를 이용하여 binary search ( query 당 O(log N) ) 답은 따로 저장해 놓음
- 저장한 답 한번에 출력
Linear Data Structures
1. Vector
일반적인 dynamic array 와 비슷하게 사용가능. 맨 마지막 위치에 원소를 넣거나 지우는 연산을 O(1) 시간에 할 수 있다. 추가하는 경우는 O(n) 시간 소요된다.
- c++ 에는 iterator 라고 하는 자료구조의 element 가리키는 변수가 존재한다.
- 보통 begin 과 end ( 마지막 원소 다음) 를 많이 사용
vector<int> v;
v.push_back(3);
v.push_back(2);
v.push_back(5); //Vector 초기화랑 원소 추가
cout << v[0] // 3
cout << v[1] // 2
vector<int> a(8) // size가 8이고 초기값 0인 벡터 a
vector<int> b(8,2); //size 8이고 초기값 2인 벡터 b
sort(v.begin(), v.end()); //정렬
reverse(v.begin(), v.end()); //뒤집기
random_shuffle(v.begin(), v.end()); //무작위 섞음
cout << *v.begin() //첫번째 원소 출력
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // 중복된 원소 모두 제거
* unique : Vercor 에서 unique 한 원소들을 앞에서부터 배치함 + unique 한 원소 끝나고 난 다음 위치 reuturn.
2. Deque
양 끝 부분에 원소를 추가/삭제를 평균 O(1) 시간에 할 수 있는 자료구조
- 끝부분에 추가 . 삭제 : push_back, pop_back
- 처음 부분에 추가. 삭제 : push_front , pop_front
이중링크리스트보다 access 빠르다( linked list 는 경진대회에선 거의 안씀)
deque<int> d;
d.push_back(5); //[5]
d.push_back(2); // [5,2]
d.push_front(3); // [3,5,2]
d.pop_back(); //[3,5]
d.pop_front(); // [5]
3. Stack
끝 부분(stack top) 에 원소를 추가(push) 및 제거 (pop) : Stack top 의 원소는 top 함수를 이용해 반환 가능 (모두 O(1))
stack<int> q;
q.push(2); //[2]
q.push(5); //[2,5]
cout << q.top() //5
q.pop(); //[2]
cout << q.top() // 2
4. Queue
끝 부분에 원소를 추가(push) 하고 앞부분부터 차례대로 제거(pop) Queue 의 가장 앞을 front 마지막은 back 으로 원소 반환 가능 ( O(1))
queue<int> q;
q.push(2); //[2]
q.push(5); //[2,5]
cout << q.front() //2
q.pop(); //[5]
cout << q.back(); //5
같은 O(1) 이라도 스택과 큐가 deque 보다 빠르다
ex) Rails (Uva 00514 )
스택 활용 문제
Algorithm/Rails_00514.cpp at main · aengzu/Algorithm (github.com)
ex) Reading Books (CSES)
책들 중 가장 오래 걸리는 책의 시간을 m, 나머지 책들을 읽는데 걸리는 시간들의 총합을 s라하자.
둘 다 모든 책을 읽어야하므로 strict 한 lower bound 는 m+s 이다.
(*lower bound 특정 key 값 이상이 처음 발견되는 값, 즉 key 값 이상인 수들 중에 가장 작은 수)
하지만 언제나 lower bound 를 만족하진 않는다
Case 1 : m>s 일 때는 2*m
=> 가장 오래 시간이 걸린 책을 읽지 않는 사람은 무조건 기다리는 시간이 존재함
Case 2: m <= s -> m+s
=> 이 경우 가장 오래 시간이 걸린 책을 읽은 사람은 절대 쉴 일이 없다
(WHY? )
Algorithm/CSES_ReadingBooks.cpp at main · aengzu/Algorithm (github.com)