본문 바로가기
반응형

비트마스킹12

백준 1285번 동전 뒤집기 - C++ 풀이 1. 각 행을 뒤집을지 여부를 고정한다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디 하게 정한다. 1. 각 행을 뒤집을지 여부를 고정한다. 행이 최대 20개, 열이 최대 20개이므로 각 행과 열에 대해 뒤집을지 말지 여부를 결정하는 경우의 수는 2^40가지이다. 따라서 브루트 포스로는 시간 내에 해결할 수 없다. 먼저 행에 대해서만 뒤집을지 여부를 결정해주자. 경우의 수는 2^20가지로 줄어든다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디하게 정한다. 행을 뒤집을지 말지 여부를 결정하고 나면, 이제 각 열의 뒤집을지 말지 여부는 그리디 하게 정할 수 있게 된다. 각 열끼리는 서로 영향을 미치지 않으므로, 각 열에 대해 뒤집는 경우와 뒤집지 않는.. 2022. 6. 28.
백준 10974번 모든 순열 - C++ 풀이 1. DFS를 사용하여 모든 순열을 구한다. 2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다. 1. DFS를 사용하여 모든 순열을 구한다. DFS를 돌면서, 매 depth마다 선택한 적 없는 숫자 중 하나의 숫자를 선택하면 모든 순열을 구할 수 있다. 2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다. 이때 각 숫자를 이전 depth에서 선택했었는지 여부를 비트 마스크로 나타내어 준다. #include #include using namespace std; int N; vector permu; void DFS(int depth, int mask) { if (depth == N) { for (auto x : permu) cout 2022. 6. 23.
백준 1194번 달이 차오른다, 가자. - C++ 풀이 1. 열쇠 소지 현황을 비트 마스크 keys로 나타낸다. 2. (r, c) 위치에서 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다. 3. BFS로 탈출 상황까지 가는 최단 이동 횟수를 구한다. 1. 열쇠 소지 현황을 비트마스크 keys로 나타낸다. BFS에서 방문 여부를 배열로 기록하기 쉽게 하기 위해서 열쇠 소지 현황을 비트 마스크를 이용해서 나타내 준다. 2. (r, c) 위치에서 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다. 어떠한 상황을 나타내는 데 필요한 값은 위치와 열쇠 소지 현황이다. (r, c) 위치에서 비트 마스크로 나타낸 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다. 3. BFS로 탈출 .. 2022. 6. 15.
백준 5175번 문제없는 문제 - C++(cpp) 풀이 1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. 2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다. 1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. N개 문제 중에서 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. N=20이므로 총 2^20가지의 경우가 있고 이는 시간 내에 모두 탐색할 수 있다. 2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다. 이제 모든 경우를 크기 순, 사전 순으로 탐색하면서 최초로 M개의 알고리즘을 모두 커버하는 경우를 찾아내면 된다. 크기 순, 사전 순으로 정렬하기 위해 각 경우를 비트마스크로 나타내고 1의 .. 2022. 4. 11.
백준 3259번 PEOPLE - C++(cpp) 풀이 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. N명의 거짓말쟁이 여부를 결정하는 모든 경우는 총 2^N가지이다. 각 경우가 유효한지 체크하는 데 O(2N)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(2N*2^N)이다. N이 최대 20밖에 되지 않으므로 브루트포스로도 해결이 가능하다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 어떠한 경우가 유효한지 체크하려면, 해당 경우를 기준으로 모든 사람들의 진술에 모순이 존재.. 2022. 3. 18.
반응형

티스토리툴바