[C++팁] 비트 개수 세는 함수 __popcnt / __builtin_popcount

비트마스크 문제에서 자주 사용되는 함수인 __popcnt 와 __builtin_popcount가 있는데 사용하다 보면 visual studio에서 는 잘 되다가도 백준에서는 제출 시 오류가 발생하고 반대로 하면 백준에서 컴파일이 안되는 상황이 발생합니다. 그 이유는 백준의 채점환경은 gcc환경이기 때문이고 비쥬얼 스튜디오는 msvc 이기 때문입니다. 이를 사용할 때마다 바꿔주는 건 귀찮기 때문에 다음과 같이 코드를 작성합니다. #if defined(_MSC_VER) h = __popcnt(arr[j] ^ b); // __builtin_popcount(gcc에서 사용하는 것, msvc에서는 __popcnt를 사용해야함) #else h = __builtin_popcount(arr[j] ^ b); #endif..

[BOJ / 인덱스 트리] 1572 중앙값

https://www.acmicpc.net/problem/1572 1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1 www.acmicpc.net 1572 중앙값 알고리즘 : 인덱스트리 / 이분탐색 알고리즘 중에 힙 두개를 사용하여 데이터가 순서대로 들어올 때마다 현재 쿼리에서 중앙값을 구하는 중앙값 알고리즘이 있습니다. 이 알고리즘은 지금까지 받은 전체 범위에서 중앙값을 구하는 반면, 해당 문제는 범위를 주어주고 그 내에서 중앙값을 구해야 하므로 위 알고리즘을 활용해서 풀이할 수 없습니다...

[BOJ / 세그먼트 트리] 10999 구간 합 구하기 2

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 10999 구간 합 구하기 2 알고리즘 : 세그먼트 트리 / 게으른 전파(Lazy Propagation) 세그먼트 트리 문제의 정석인 문제입니다. 구간 합 구하기 1에선 세그먼트 트리만 구현해도 되었지만, 2에서는 N이 커지고 쿼리가 많아져 할때마다 모든 연산을 다 해준다면 시간초과가 나게 됩니다. 이를 방지하기 위해 게으른 전파 ..

[백준] 400문제 달성! (PLATINUM IV)

[BOJ / DP] 13398 연속합 2

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 13398 연속합 2 알고리즘 : 누적합 / DP 일단 연속합의 최대를 구하는 sum을 이용해 연속합1 의 답을 구해준 뒤, - dp[0][i]에는 배열의 앞에서부터 i번째까지의 최대연속합 - dp[1][i]에는 배열의 뒤에서부터 i번째까지의 최대연속합 을 구해줍니다. 그 뒤, 1~n까지 돌며 dp[0][k-1] + dp[1][k+1]로 k번째 수를 제외하였을 때 연속합의 최대를 갱신해 답을 구해줍니..

[BOJ / 휴리스틱(시뮬레이티드 어닐링)] 16992 3-SAT

https://www.acmicpc.net/problem/16992 16992번: 3-SAT 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 100)과 절의 개수 M (1 ≤ M ≤ 1000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 세 정수 i, j, k (1 ≤ |i|, |j|, |k| ≤ N)로 이루어져 있으며, i, j, k가 www.acmicpc.net 16992 3-SAT 알고리즘 : 휴리스틱(시뮬레이티드 어닐링) 시뮬레이티드 어닐링(담금질 기법)을 이용한 휴리스틱 풀이입니다. 휴리스틱이란 정해를 구하기엔 시간이 충분하지 않거나 정보의 부족으로 인하여 합리적인 해를 제시할 수 없을 때, 빠르게 사용할 수 있는 확률에 의지하는 방법 입니다. SCPC에 자주 나오는 유형이라 이번에 ..

[BOJ / 플러드필 BFS] 2638 치즈

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2638 치즈 알고리즘 : 플러드필 / BFS 바깥공기와 치즈, 안쪽 공기를 나누어 표기하고 첫 큐를 이용해 바깥공기를 처리, 공기에 맡닿은 치즈를 골라주고, 두번째 큐를 이용하여 다음 시간대에 녹을 치즈를 골라줍니다. 그렇게 골라서 만약 바깥공기와 안쪽 공기가 닿을 경우 첫 큐를 이용하여 처음과 같은 처리를 다시 이용해 주되, 메모이제이션을 통해 중복된 연산을 하지 않도록 합니다. ..

[BOJ / 메모이제이션 BFS] 2157 여행

https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 2157 여행 알고리즘 : 메모이제이션 / BFS 기본적인 메모이제이션을 이용한 BFS 풀이입니다. 인접리스트를 이용하여 각 도시간 항로를 만드는데 도착지가 출발지보다 작은 경우는 추가하지 않습니다. (시간 절약) 메모이제이션 테이블은 DP[A][B]=K를 - A : 현재까지 들린 도시의 수 - B : 현재 도시 번호 - K : 최대 ..