[스크랩] 알고리즘공부할 때 한눈에 보는 팁정리 C++

알고리즘공부는 어렵지만 공부할수록 프로그래밍 실력이 늘고 있다는 것을 느끼게 됩니다. 저는 C++를 그렇게 잘 알지 못했고 그 와중에 알고리즘공부를 하느라 힘들었습니다. 하나하나 C++ 개념들을 배워갔지만 모르는 것은 역시나 많았습니다. 삽질한 내용들을 토대로 정리해서 알고리즘 초보자로써 알고리즘 문제를 풀 때 좋은 팁을 모아모아 초보자라도 "이것만" 알면 C++를 사용해서 많은 문제들을 풀 수 있는 상식들을 공유합니다.

​

정렬 많이 씁니다.

sort(a.begin(), a.end(), greater<int>()) // 내림차순의 예입니다.

연산순서가 중요합니다.

int a = (int) p * 100 이것과 (int) 100 * p 는 다릅니다.

​

입력을 주다가 안주는 것은 이렇게 EOF로 거르면 됩니다.

while (scanf("%d", &n) != EOF) while (cin >> n) // cin으로는 이렇게 하면 됩니다.

지역변수로 계속 배열을 만드는 것보다는 전역변수를 쓰는게 좋습니다.

지역변수는 스택에 메모리공간이 잡힙니다. 그런데, 리눅스의 프로세스당 기본 스택사이즈는 1MB 였나 8MB 였나 여튼 저것 밖에 안됩니다. 그러니까 지역변수에 큰 배열을 선언하면 스택이 터져서 오류가 나는 것이지요. 전역변수는 힙 공간에 잡히므로 저런 제한에서 자유롭습니다

- 백준 ntopia님의 답변.

​

실수형은 웬만하면 정수형으로 받아야 합니다. 이렇게 말이죠.

scanf("%d %d.%d", &n, &m1, &m2); //3 3.21 을 받을때

​

알고리즘 template

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <numeric> #include <deque> #include <utility> #include <bitset> #include <iostream> #define MAX_N 1001 using namespace std; typedef long long ll; typedef long double LLF; typedef pair<int, int> PI; typedef deque<int> D; typedef priority_queue<int, vector<int>, greater<int>> PQ; typedef vector<int> VI; const int INF = 987654321; const ll INF2 = 1e18; const ll INF3 = 1ll << 52; #define max_n 1000001 #define FOR(i, n) for(int i = 0; i < n; i++) #define T_2(a, b) cout << a << " : " << b << '\n'; #define T_3(a, b, c) cout << a << " : " << b << " : " << c << '\n'; #define T_4(a, b, c, d) cout << a << " : " << b << " : "<< c << " : "<< d << '\n'; #define T_5(a, b, c, d, e) cout << a << " : " << b << " : "<< c << " : "<< d << " : " << e << '\n'; #define K_1(a) cout << a << '\n'; #define K_2(a, b) cout << a << " " << b << '\n'; #define K_3(a, b, c) cout << a << " " << b << " "<< c << '\n'; #define K_4(a, b, c, d) cout << a << " " << b << " "<< c << " "<< d << '\n'; #define K_5(a, b, c, d, e) cout << a << " " << b << " "<< c << " "<< d << " " << e << '\n'; int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; struct Point{ int y, x; Point(int y, int x) : y(y), x(x){} Point(){y = -1; x = -1; } bool operator < (const Point & a) const{ // if(y == a.y) return x < a.x; // return y < a.y; if(x == a.x) return y < a.y; return x < a.x; } }; int n, t; vector<Point> p; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while(t--){ } return 0; }

기본적인 cin, cout은 좀 느립니다. 시간초과가 뜨는 문제를 저렇게 ios, cin.tie 등으로 셋팅해 놓으면 시간을 줄일 수 있습니다.하지만 저걸 쓸 때는 iostream과 scanf 등의 stdio에 있는 것들을 혼용해서 쓰면 안됩니다. 저 ios_base::sync_with_stdio(false); 라는 것은 stdio의 다른 입출력함수들과 iostream의 입출력함수들과의 동기화를 푼다는 것이기 때문에 순서가 뒤죽박죽이 될 수 있어서 오류가 날 수도 있습니다.

그 외에도 typedef를 하게 되면 편하게 쓸 수 있습니다. 복붙해서 쓰시면 됩니다.

​

다닥다닥 붙여있는 입력처리

11110011 11110011 scanf("%1d", &map[i][j]);

한개의 digit을 받는다라는 뜻으로 %1d를 씁니다.

*%는 출력형식을 지정하는 것을 뜻합니다.

소수점 출력 및 포맷설정

printf("%.6lf") cout.precision(6) //02 이런식으로 출력하고 싶을때는 이렇게 합니다. int test =1; printf("%02d",test); //long long 을 출력하고 싶다면 이렇게 하면 됩니다. printf("%lld", value);

cout을 사용하면 precision을 걸면 되고 printf를 할경우에는 저렇게 .6으로 셋팅을 해줍니다. 02로 표기하고 싶을 때 저렇게 하면 됩니다.

*%는 출력형식을 지정하는 것을 뜻합니다. lf는 double, f는 float를 뜻하며 double이 더 많은 수를 표기할 수 있습니다.

lower_bound와 uppper_bound

int myints[] = {10,20,30,30,20,10,10,20}; vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 vector<int>::iterator low,up; low = lower_bound (v.begin(), v.end(), 20); // 20이 시작되는 위치, 3 up = upper_bound (v.begin(), v.end(), 20); // 마지막부터 시작했을 때 20이 시작되는 6 cout << *low << ":" << *up << '\n'; //20 : 30 cout << low - v.begin() << " : " << up - v.begin() << '\n';// 3 : 6

전자는 0번째 배열의 원소부터 찾아서 어떠한 값의 이상이 되는 위치를 반환하며 후자는 마지막 원소부터 찾았을 때 그 값이 시작되기 전의 위치를 반환합니다. 반환되는 값은 이터레이터이기 때문에 v.begin()을 빼주어서 int형으로 몇번째인지를 파악할 수 있습니다.

map

unordered_map<string, int> umap; //이렇게 넣기도 가능하고 umap.insert({"test1", 1}); //이렇게 넣을 수도 있습니다. umap.emplace("test5", 5); //또한 이렇게 변경도 가능, 추가할 수도 있습니다. umap["test1"] = 4; for(auto element : umap){ cout << element.first << " :: " << element.second << '\n'; } //map의 find메소드는 찾지 못하면 end() 이터레이터를 반환합니다. auto search = umap.find("test4"); if(search != umap.end()){ cout << "found :" << search -> first << " " << (*search).second << '\n'; }else{ cout << "not found.." << '\n'; } //이런식으로 바로 int형을 증가시킬 수 있습니다. umap["test1"]++; umap["1"]을 하게 되면 초기값은 0입니다.

map과 unordered map입니다. key와 value로 이루어져 있는 집합입니다. STL의 map은 R-B트리로 이루어져 있어 삽입, 삭제, 검색 시에 동일한 시간복잡도인 O(lgN)를 지닙니다. 반면 unordered_map은 해시테이블로 이루어져 있어 탐색에 있어 O(1)의 시간복잡도를 지닙니다. 그러나 데이타가 작은 경우에는 map이 더 좋습니다. 데이타가 큰 경우에는 unordered_map이 더 좋습니다.

 

문자열 키의 map, unordered_map 성능 비교

map 과 unordered_map 은 키, 값을 저장할 수 있는 컨테이너다. map 은 Red-Black Tree 를 사용해 키의 순서를 유지하는 반면 unoredered_map 은 해시 테이블을 사용해 키의 순서를 유지하지 않는다. unordere...

veblush.blogspot.com

데이타가 클 때 검색의 경우에는 unordered map을 사용하고 순차적인 접근에 map을 사용하는 것이 좋습니다.

* 이와 비슷한 것이 Set입니다. Set은 중복된 데이터가 없는 집합을 말합니다.

queue

priority_queue<int, vector<int>, greater<int> > pq; //오름차순 priority_queue<int, vector<int>, less<int> > pq; //내림차순 queue에서는 pop을 했을 때 원소가 없어도 문제가 발생하지 않는다.

다익스트라 알고리즘이나 여러 알고리즘에 쓰이는 자료구조 입니다. 가장 먼저 집어 넣은 데이타가 먼저 나오는 FIFO구조로 저장됩니다만 STL의 priority_queue는 queue + 우선순위먼저 나오는 que입니다.

struct 구성하기

struct point{ int x, y; point(int x, int y): x(x), y(y){} point() : point(-1, -1){} point() {point(-1, 0);} //c++11 delegating 오류가 날 때는 이렇게 정의한다. //위의 초기화 방법은 컴파일러에 따라 애러가 날 수 있으므로 아래의 코드로 짜는게 가장 안전하다. point(){x = -1; y = 0; } bool operator < (const point & a)const { if(y == a.y) return x < a.x; return y < a.y; } }; //생성할 때는 이렇게 생성하면 됩니다. point p(10, 1); //간단히는 이렇게 만들 수 있습니다. struct Edge { lli A,B,C; } E[100001]; Edge라는 struct를 가진 100001개의 E가 생성되었습니다.

비교연산자를 쓸 수 있습니다. 저렇게 operator를 걸면 됩니다.

만약 중복된 것들을 파악하고 지워야 한다면?

vector<int> s(3, 1); s.erase(unique(s.begin(), s.end()), s.end());

이렇게 unique와 erase를 쓰면 됩니다. s(3, 1)은 1이라는 원소 3를 가지는 벡터로 초기화 한다는 뜻입니다.

​

세그먼트 트리를 만들 때

//트리사이즈 구하기 int h = (int)ceil(log2(MAX_N)); int treeSize = (1 << (h + 1));

트리구조를 만들 때 얼마나 많은 트리가 생성될 것인가. 고민하게 됩니다. 가장 큰 값의 범위에 log를 먹이고 이를 토대로 treeSize를 계산 합니다. 예를 들면 4의 경우, h = 2가 되고 treeSize = 8이 됩니다.

반올림

(int)round(ret / double(n))

형변환은 중요합니다. 반올림을 하실 때 double로 나누면서 round메서드를 실행시키고 int로 형변환을 해주면 됩니다.

​

배열

//vector 초기화 하기 vector<int> v[10]; //v벡터를 10개를 생성합니다. vector<int> v(n, 0); 0이라는 value를 가진 n개의 벡터를 생성 //vector로 2차원 배열 매트릭스 만들기 vector<vector<int> > checked; vector <vector<int> > v(n + 1 , vector<int> (n + 1, 0)); //fill로도 초기화할 수 있다. fill(v.begin(), b.end(), 0); //배열초기화 shortcut : 전체 0으로 초기화한다. 일부 컴파일러에서 통하지 않을 수도 있습니다. int dp[10] = {0,}; int dp[10][10] = {{0, } }; fill(dist, dist + MAX_N, 0); //부분초기화 : 0번째를 0, 1번째를 1로 초기화한다. int a[n] = {0,1}; //memset으로 초기화합니다. 이건 아쉽게도 0밖에 못합니다. 왜냐면 바이트 단위로 초기화를 하기 때문입니다. memset(check, false, sizeof(check)); //fill을 사용한 2차원 배열 초기화는 이렇습니다. for(int i = 0;i < 10;i ++) fill(dp[i], dp[i]+10, 0); fill(&arr[0][0], &arr[0][0] + n*m, k) // 이런식으로 한번에 초기화를 할 수 있습니다.

또한, vector의 경우 v.size(), list의 경우, sizeof(arr)/sizeof(arr[0]);로 사이즈를 알 수 있습니다.

​

아스키코드

많이 쓰이는 아스키코드입니다.

0 : null입니다.

65 : A입니다.

97 : a입니다.

int CtoI(char c){ if(c <= 'Z') return c - 'A'; return c - 'a' + 26; }

이렇게 char 형을 int형으로 바꿀 수 있습니다.

*라이블로그 코드를 참고했습니다.

https://kks227.blog.me/220804885235?Redirect=Log&from=postView

문자열 입력과 출력

//문자열 입력 char s[5] = "absc"; char s[10]; //10byte의 문자만 받을 수 있다. 띄어쓰기도 받을 수 있다. fgets(s,10,stdin); //반복문을 돌릴 땐 0이 아닌가?로 종료문을..!왜냐면 끝은 null로 되는데 null은 아스키코드로 0이다. for(int i=0;x[i]!=0;i++){ //소문자를 대문자로. x[i] = x[i]-'a'+'A'; //문자열 출력 puts(s); printf("%c\n", s[3]); //character형으로 출력한다. printf("%s\n", s); //string형으로 출력한다. //문자열 길이 null값전의 까지의 길이를 추출해낸다. strlen(x) //int를 문자열로 만들자면? '0' + 1; //문자열을 int형으로 바꾸자면? 26미만으로. A[i] - 'a' //문자열을 찾는 것은 find이다. to_string은 정수를 문자열로 만들어준다. if(to_string(i).find(s) != string::npos) n--; 이렇게 찾는다. if안에 있는 구문이 true라면 찾은 것이다. //cin으로 문자열을 입력받을 때는 띄어쓰기 또는 엔터를 하게 되면 나누어서 받게 된다. getline(cin, s); //을 이용하면 띄어쓰기 등이 포함된 한줄짜리 문자열을 받을 수 있다.

마지막 문자는 끝을 나타내는 null이 되므로

초기화할 때 문자의 크기보다 +1을 해줘야 합니다.

메모이제이션시 double 형

메모이제이션을 할 때 double형은 ret == -0.5이런식으로 하면 안됩니다. 부동소수점이라서 정확한 0.5가 아니기 때문입니다.

ret <= -0.5로 잡아야 합니다.

많이 나오는 알고리즘

다익스트라

다익스트라는 현재로부터 최단거리를 뽑아 낼 때 씁니다. 현재로부터 그 지점까지의 거리를 비교하면서 dist를 업데이트하고. 그럴 때 priority queue를 이용하여 항상 "최소값"부터 비교하는게 특징입니다.

//백준 1504 특정한 최단경로 vector<P> adj[MAX_N]; P dikstra(int start, int end1, int end2){ vector<int> dist(MAX_N, INF); priority_queue<P, vector<P>, greater<P>> PQ; dist[start] = 0; PQ.push(P(0, start)); while(PQ.size()){ int here = PQ.top().second; int d = PQ.top().first; PQ.pop(); if(dist[here] < d) continue; for(P there : adj[here]){ int next = there.second; int d = there.first; if(dist[next] > dist[here] + d){ dist[next] = dist[here] + d; PQ.push(P(dist[next], next)); } } } return {dist[end1], dist[end2]}; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int u, v, w; cin >> u >> v >> w; adj[u].push_back(P(w, v)); adj[v].push_back(P(w, u)); } int a, b; cin >> a >> b; P a1 = dikstra(1, a, b); P a2 = dikstra(a, b, n); P a3 = dikstra(b, a, n); long long r1 = a1.first + a2.first + a3.second; long long r2 = a1.second + a3.first + a2.second; r1 = min(r1, r2); if(r1 >= INF){ cout << -1 << '\n'; }else{ cout << r1 << '\n'; } return 0; }

벨만 포드 알고리즘

이런이런.. 아쉽게도 경로에 음수가 있다면 다익스트라처럼 한번씩만 방문하면 되지 않습니다. 모든 경로를 탐색해줘야 한다. 왜냐면 음수로 인해 경로가 업데이트가 되기 마련이기 때문이죠.

//1865. 웜홀 문제입니다. bool minusCycle = false; dist[1] = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(dist[j] == INF) continue; for(P there : adj[j]){ int next = there.second; int d = there.first; if(dist[next] > dist[j] + d){ dist[next] = dist[j] + d; if(i == n) { minusCycle = true; } } } } } if(minusCycle) cout << "YES" << '\n'; else cout << "NO" << '\n';

피보나치수열, 빠른 거듭제곱, 행렬계산

typedef vector<vector<long long>> matrix; const long long mod = 1000000007LL; matrix operator * (const matrix &a, const matrix &b) { int n = a.size(); matrix c(n, vector<long long>(n)); for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { for (int k=0; k<n; k++) { c[i][j] += a[i][k] * b[k][j]; } c[i][j] %= mod; } } return c; } int main() { long long n; cin >> n; if (n <= 1) { cout << n << '\n'; return 0; } matrix ans = {{1, 0}, {0, 1}}; matrix a = {{1, 1}, {1, 0}}; while (n > 0) { if (n % 2 == 1) { ans = ans * a; } a = a * a; n /= 2; } cout << ans[0][1] << '\n'; return 0; } //피보나치수에서 M = 10k 일 때, k > 2 라면, 주기는 항상 15 × 10k-1 입니다

이항계수

int memo[10][10]; int bino(int n, int k){ if(memo[n][k] > 0) return memo[n][k]; if(n == k || k == 0){ return memo[n][k] = 1; } return memo[n][k] = bino(n - 1, k - 1) + bino(n - 1, k); } int main(){ memset(memo, -1, sizeof(int)*100); cout << bino(3, 2) << endl; return 0; }

에라토스테네스의 채

for(int i = 2; i <= n; i++){ if(check[i] == 0) continue; for(int j = i + i; j <= n; j += i){ check[j] = 0; } } //보통은 이렇지만 이렇게 해서 좀 더 최적화를 시킬 수 있다. vector<int> prime(1, 2); //2, 3 5 7.. this is prime for(int i = 4; i < limit; i += 2){ isP[i] = false; } for(int i = 3; i < limit; i+= 2){ if(isP[i]) prime.push_back(i); for(int j = i * i; j < limit; j += i * 2) isP[j] = false; }

최대공약수와 최소공배수

#include <algorithm> #include <cstdio> #include <string> #include <cmath> int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a%b); } 최대공배수 : (a * b) / gcd(a, b)

KMP

void setFail(string s){ for(int i = 1, j = 0; i < s.size(); i++){ while(j > 0 && s[i] != s[j]) j = fail[j - 1]; if(s[i] == s[j])fail[i] = ++j; } return; } void kmp(string T, string P){ int N = T.size(); int M = P.size(); for(int i = 0, j = 0; i < N; i++){ while(j > 0 && T[i] != P[j]){ j = fail[j - 1]; } if(T[i] == P[j]){ if(j == M - 1){ ret.push_back(i - M + 2); j = fail[j]; }else j++; } } return; }

접미사

bool cmp(int i, int j){ if(pos[i] != pos[j]) return pos[i] < pos[j]; i += d; j += d; return (i < N && j < N) ? (pos[i] < pos[j]) : (i > j); } void constructLCP(string S){ fill(lcp, lcp + N, 0); for(int i = 0, k = 0; i < N; i++, k = max(k - 1, 0)){ if(pos[i] == N - 1) continue; for(int j = sa[pos[i] + 1]; S[i + k] == S[j + k]; k++); lcp[pos[i]] = k; } return; } void constructSA(string S){ N = S.size(); fill(sa, sa + N, 0); fill(pos, pos + N, 0); for(int i = 0; i < N; i++){ sa[i] = i; pos[i] = S[i]; } for(d = 1; ; d*= 2){ sort(sa, sa + N, cmp); int temp[MAX] ={0}; for(int i = 0; i < N - 1; i++){ temp[i + 1] = temp[i] + cmp(sa[i], sa[i + 1]); } for(int i = 0; i < N; i++){ pos[sa[i]] = temp[i]; } if(temp[N - 1] == N - 1) break; } return; }

TSP

int n, start, cache[MAX_N][1 << MAX_N], dist[MAX_N][MAX_N]; int tsp(int here, int visited){ if(visited == (1 << n) - 1){ return dist[here][start] ? dist[here][start] : INF; } int &ret = cache[here][visited]; if(ret != -1) return ret; ret = INF; for(int i = 0; i < n; i++){ if(visited & (1 << i)) continue; if(dist[here][i] == 0) continue; ret = min(ret, tsp(i, visited | (1 << i)) + dist[here][i]); } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> dist[i][j]; } } memset(cache, -1, sizeof(cache)); cout << tsp(0, 1) << '\n'; return 0; }

상호배타적 집합, disjoint Set

int uf_find(int a){ if(uf[a] < 0) return a; return uf[a] = uf_find(uf[a]); } bool uf_merge(int a, int b){ a = uf_find(a); b = uf_find(b); if(a == b ) return false; uf[b] = a; return true; }

[출처] 알고리즘공부할 때 한눈에 보는 팁정리 C++|작성자 큰돌이