코딩(1)

1)

memset은 bit를 모두 초기화 해주기 때문에 0이나 -1로만 초기화 가능하다. fill을 사용하는 것이 낫다

 

2)

2차원 배열을 fill해주기 위해선

fill(&arr[0][0], &arr[max-1][max], val) 꼴

max-1이 아니라 max로 해서 틀린 문제때문에 1시간은 날린 듯 하다.

 

3)

탐색 시 경로 저장 (bfs, dfs, 다익스트라 등)

prev[next] = curr;

prev[next]가 여러번 호출 돼도 마지막에 호출되는 경우가 유효하므로 덮어쓰기가 된다.

 

4)

1<<n  = 2^n

 

5)

c++의 string형을 서식문자 %s로 받으려면 str.c_str()을 보내주면 된다.

 

6)

gcd(fibo(n), fibo(m) == fibo(gcd(n,m))

 

7)

이분탐색 시 범위가 음수일 경우, 내가 평소에 쓰는 방법이 유효하지 않을 수 있다.

 

int lo = -1e9, hi = 1e9;
while (lo < hi) { 
   int x = (lo + hi) / 2;
   if (pos(x))lo = x+1;
   else hi = x;
}

 

예를들어 lo = -3, hi= -2인경우 무한루프이다.

 

확실하지 않으면 삼분탐색마냥 다음과 같이 하는 방법도 괜찮아 보인다.

 

int lo = -1e9, hi = 1e9;
while (lo+2 < hi) { 
	int x = (lo + hi) / 2;
	if (pos(x)) hi = x;
	else lo = x+1;
}
for (int j = lo; j <= hi; j++) if (pos(j)) {
	lo = j;
	break;
}

 

8)

정수 x,y에 대해 x+y = 소수인 경우 x,y는 서로소이다.