[SW Expert Academy] 알고리즘 문제 암기사항

기본적으로 cplusplus.com을 참고하여 해결한다.

1. 입출력 가속화 (비동기적 입출력)

iso_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

2. vector

#include<vector>

vector<int> vec;
vec.size();
vec.clear();
vec.push_back(5);
vec.front();
vec.erase(a.begin()+2);
vec.back();
vec.pop_back();
vec.insert(a.begin(), 3);

3. string

#include<string>

string str;
str.size();

4. algorithm

#include<algorithm>

sort(a.begin(), a.end()); //오름차순
sort(a.begin(), a.end(), cmp); //내림차순

bool cmp (int a, int b) { return a>=b;}

5. priority queue
priority_queue<int, vector<int>, greater<int> >pq; //오름차순
priority_queue<int> pq; //내림차순
pq.top();
pq.push();
pq.pop();


6. 연산자 오버로딩

막힌 부분은 다음과 같다.
구조체(사용자 정의 타입)을 우선순위 큐에 넣어 사용하고자 했다.

구조체는 연산자가 정의되어있지 않으므로, 연산자를 재정의해주었다.

struct opov{
 int x, int y;
 bool operator<(struct opov op)
 {
   return (x < op.x)? true:false;
  }
};

int main()
{
  priority_queue<struct opov, vector<struct opov>, greater<struct opov> > q;
  q.push(a);
  q.push(b);
}

하지만 에러가 발생하였다.
찾아보니, priority_queue가 받는 연산자 멤버함수(operator<, opeartor>)의 타입이 일치하지 않아 생기는 오류였다.
다음과 같이 선언하니 올바르게 구동하였다.
struct opov{
 ..
  bool operator<(const struct opov op) const
 {
   return (x < op.x)? true:false;
  }
   bool operator<(const  struct opov op) const
 {
   return (x < op.x)? true:false;
  }
};

여기서 함수에 붙은 const는 멤버 함수 내에서 멤버 변수의 변경을 금지하는 효과를 가진다.


Reference: 
http://blog.daum.net/_blog/BlogTypeView.do?blogid=0Nu8o&articleno=73&categoryId=7&regdt=20091124144927&totalcnt=35
https://stackoverflow.com/questions/37301160/invalid-operands-to-binary-expression-const-and-const
https://felixblog.tistory.com/70

7. Sort
sort의 경우 위의 priority queue와 조금 다르게 연산자를 정의할 수 있다.

sort(vector.begin(), vector.end(), comp)

여기서 comp에서 연산을 정의해주면, 쉽게 사용할 수 있다.

typedef struct edge{
 int v1, v2;
 int w;
}EDGE

vector<EDGE> v;

bool comp(EDGE e1, EDGE e2){
 return (e1.w > e2.w)? true : false; //큰놈부터 출력
}

int main{
 sort(v.begin(), v.end(), comp)
}

sort하면, 내림차순으로 출력된다.


특이한 sort
->sort( , , comp)에 들어가는 comp는 함수 포인터뿐 아니라 함수 오브젝트(구조체)도 들어갈 수 있다.  
(http://www.cplusplus.com/reference/algorithm/sort/)


-접미사 배열 생성하기 (원시적인 방식)
코드
//두 접미사 시작 위치 i,j가 주어질 때 두 접미사 중 어느 쪽이 앞에 와야 할지 비교한다.
struct SuffixComparator{
 const string& s;
 SuffixComparator(const string& s) : s(s) {} //s(s)는 argument로 받은 s를 구조체 내 s에 대입하여 초기화한다. 
 bool operator () (int i, int j){
  return strcmp(s.c_str() + i, s.c_str() + j ) < 0; //c_str()은  string 오브젝트의 포인터 반환 -> string을 char*로 변환할 때 사용
};
//s의 접미사 배열을 계산한다.
vector<int> getSuffixArrayNaive(const string& s){
 vector<int> perm;
 for(int i=0; i<s.size(); ++i) perm.push_back(i);
 sort(perm.begin(), perm.end(), SuffixComparator(s));
 return perm;
}

8. 문자열
string 함수
str.c_str(): 포인터를 반환한다. (char*)로 변환하기 좋음.
str.length(): 문자열 길이 반환
str.size(): 바이트 수를 반환한다.
str.resize(size, char c)
vector와 같은 함수:
empty(), clear(), erase(),pop_back(), push_back(item)
front(), back(): 첫번째, 마지막 문자를 반환한다.

+연산 사용 가능
==, !=, >, <, >=, <= 사용 가능

char* 함수
charr.strcmp(): 첫번쨰가 크면 >0, 두번쨰가 크면 <0, 같으면 0 리턴함.

STL 컨테이너 정리
https://modoocode.com/224

컨테이너는 시퀀스 컨테이너와 연관 컨테이너(associative container)가 있다. 

연관 컨테이너는 key-value기반의 자료구조이다. 

set(중복 불허용), multiset(중복 허용), unordered_set(정렬되지 않는 해쉬 셋)
map(중복 불허용), multimap(중복 허용), unordered_map(정렬되지 않는 해쉬 맵)

-set
set에 원소를 추가(insert)하거나 삭제(erase)하거나 탐색(find)할 수 있으며, 복잡도는 O(logN)이다.
set은 insert하면 sorted된 이진트리 자료구조가 형성되며, 부모 노드가 왼쪽 자식 노드값보다 크고, 우측 노드값보다 작은 이진 탐색 트리이다. (링크 참조)
만일 트리가 한쪽으로 치우친다면 추가/삭제/탐색 복잡도가 O(N)이 될 우려가 있지만, STL라이브러리는 균형잡인 이진트리를 유지하도록 구현되므로 걱정하지 않아도 된다. 

#include<set>
set<int> s;
s.insert(10);
for(set<int>::iterator iter=s.begin(); iter!=s.end(); ++iter)
 cout<<*iter<<endl;

if(s.find(10)!=s.end())
 s.erase(s.find(10));

set은 

-map
set과 거의 똑같은 자료구조인데, 키에 대응되는 값(value)도 같이 보관한다는 점이 다르다.
value가 있으므로 자료구조의 크기는 set보다 크다.
마찬가지로 insert, find, erase를 지원한다. 

#include<map>
map<std::string, double> hash_map; //원소로 pair을 가진다.
hash_map.insert(std::pair<std::string, double>("짱구학점", 2.23);
hash_map["짱아학점"] = 3.56;
//같은 key를 가지는 value가 또 들어오면, 새로운 value로 대체된다.
for(map<std::string, double>::iterator iter=hash_map.begin(); iter!=hash_map.end(); ++iter)
 std::cout<<iter->first<<" "<<iter->second<<std::endl;

-multiset, multimap
한키에 여러 값이 대응될 수 있다. 
find()에서 나오는 값은 여러개일 수 있다. 


#include<set>
#include<map>

std::multiset<std::string> s;
std::multimap<int, std::string> m;
s.insert("a")

m.insert(std::make_pair(1, "hello"));
m.insert(std::make_pair(1, "hi"));

auto range = m.equal_range(1);
for(std::multimap<int, std:;string>::iterator iter=range.first; iter!=range.second; iter++)
 std::cout<<iter->first<<" "<<iter->second<<std::endl;

-unordered_set, unordered_map
원소들이 정렬되있지 않은 해쉬셋, 해쉬맵이다.
insert, erase, find모두 O(1)이다.
(worst case는 엄밀히 O(N)이지만, 평균적으로 O(1)이다. 문제풀땐 O(1)로 보고 풀면 된다.)
공간복잡도는 O(N)이라고 봐도 무방하다.

해쉬문제: https://leetcode.com/problems/longest-consecutive-sequence/