알고리즘 문제(PS) 풀 때 도움되는 정보들

vector, string 내에서 인접한 값끼리 비교할 때

for(int i=1; i<v.size(); i++)
	if(v[i-1] == v[i]) check = true;

i=0; i<v.size()-1; i++과 같이 조건을 작성하지 말고 위와 같이 i=1; i<v.size(); i++로 작성한다.

같은 코드처럼 보이지만 세그먼트 에러가 발생하는 경우가 있다. string도 마찬가지이다.

 

__gcd(x, y)

위의 함수를 사용하면 유클리드 호제법 코드를 따로 구현하지 않아도 C++ 라이브러리에 내장되어 있는 유클리드 호제법으로 구현된 최대공약수 함수를 사용할 수 있다.

 

비교 연산 > 비트 연산

비트 연산이 비교 연산보다 계산 우선 순위가 낮다.

즉, a & b < c의 식은 a & (b < c)와 같이 계산된다.

따라서 비트 연산 먼저 수행하려면 (a & b) < c와 같이 구현해야 한다.

 

#define int long long

위의 코드를 선언하면 int를 long long처럼 사용할 수 있다.

변수 범위가 int를 넘어갈지에 대한 걱정을 할 필요가 없다.

단, main 함수를 int main이 아닌 그냥 main으로 사용해야 하며, max 함수에서 int a에 대해 max(a, (int)0)과 같이 int형의 정수를 long long으로 한 번 바꿔주어야 한다.

 

정답자의 코드 길이 참고 (BOJ 한정)

문제를 맞은 사람들의 코드 길이를 보면 구현량을 유추할 수 있다.

만약 아이디어가 떠오르지 않는데 정답자의 코드가 짧다면 문제 풀이 아이디어가 간단한 것이다.

 

Map 시간복잡도 계산

Map의 시간복잡도는 O(log N) 정도로 고려하면 된다.

만약 중복이 없고 하나의 자료형 -> 하나의 자료형으로 이어지는 map이라면 O(1) 시간에 작동하는 unordered_map을 사용하면 된다.

 

다차원 Map

map<string, map<string, map<string, int>>> m과 같이 선언하면 m[a][b][c]로 맵에 접근 가능하다.

 

vector 값 초기화

v.resize(N, x)는 새로 할당되는 부분에 대해서만 x로 값을 초기화해준다.

즉, 새로운 테스트케이스를 처리할 때 v.resize(N, 0)을 한다고 해서 값이 0으로 초기화되지 않는다.
v.clear() 후 v.resize(N, x)를 해주면 정상적으로 값이 세팅된다.