비트마스킹을 알고리즘 문제를 풀 때 어떻게 활용하는지 알아보기 전에 비트연산자를 먼저 알아보자. 비트연산자 연산자 기능 & AND 연산 | OR 연산 ^ XOR 연산 ~ 모든 비트를 반전 비트 열을 오른쪽으로 이동 & 연산자 true & true = true이고, 나머지는 모두 false를 반환한다 연산 결과 0 & 0 0 1 & 0 0 0 & 1 0 1 & 1 1 ex) 1001 & 1000 = 1000 | 연산자 하나라도 true라면, true를 반환한다. 연산 결과 0 & 0 0 1 & 0 1 0 & 1 1 1 & 1 1 ex) 1001 & 1000 = 1001 ^ 연산자 두 비트가 서로 다를 경우(true ^ true, false ^ false)에 true를 반환한다. 연산 결과 0 & 0 1 1..

완전탐색이란? 완전탐색은 모든 경우의 수를 탐색하는 알고리즘이다. 무식하게 한다는 의미로 브루트포스(Brute Force) 알고리즘이라고도 부른다. 직관적이기 때문에 이해하기 쉬우며 문제의 정확한 결과를 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 모든 경우의 수를 탐색하는 것은 저번 포스트의 순열이나 조합을 사용하거나, 단순 구현을 하면 된다. 하지만 시간 초과가 날 수 있으므로, 보통은 최대 범위가 1억 미만일 때까지만 한다. 완전탐색으로 문제 푸는 방법 완전탐색을 활용할 때 가장 간단한 방법은 반복문(for, while)을 활용하는 것이다. 만약 반복문만 사용하는 것이 너무 복잡하거나 특정 행위를 반복하며 매개변수만 변경하면 될 것 같은 경우에는 재귀함수를 사용할 수 있다. ex. 조합/순열 ..

누적합이란? 요소들의 누적된 합. 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어 활용하는 것을 의미한다. 앞에서부터 더하는 prefix sum, 뒤에서부터 더하는 suffix sum이 있는데, 코딩테스트에는 prefix sum이 자주 나온다. 누적합을 만들 때, 0번째 index는 비워두고 1번째 index부터 사용하는 것이 편하다 인덱스 0 1 2 3 4 원소 0 1 10 11 100 누적합 0 1 11 22 122 누적합을 C++로 간단하게 구현할 수 있다. #include using namespace std; int a[100004], b, c, psum[100004], n, m; int main() { cin >> n >> m; for (int i = 1; i..

들어가며 코딩테스트에서는 문자열을 split하는 로직(특정 문자열을 기준으로 쪼개어 배열화)이 많이 사용된다. 하지만 C++ STL에서는 관련된 함수를 지원하지 않기 때문에 직접 구현해야 한다. split() 구현 // input: 쪼갤 문자열 // delimiter: 기준 문자열 vector split(string input, string delimiter) { vector ret; long long pos = 0; string token = ""; while ((pos = input.find(delimiter)) != string::npos) { token = input.substr(0, pos); ret.push_back(token); input.erase(0, pos + delimiter.leng..

순열 vs 조합 순서와 상관 있이 뽑는 경우 > 순열 순서와 상관 없이 뽑는 경우 > 조합 순서를 재배치하여 ~~~한 순서의 경우 최대값을 구하는 문제 > 순열 1, 2, 3에서 3개를 뽑을 때 순열 - {1, 2, 3} 조합 - {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} next_permutation C++에서는 next_permutation이라는 함수를 제공하고 있다. bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); next_permutation에서는 매개변수로 시작 지점과 끝 지점 iterator을 받는다. 주의 끝 지점의 iter..