Algorithm/비트마스킹

[알고리즘] 백준 14391 종이조각 // 비트마스킹, 1차원을 2차원으로 바꾸는힘

* 요약차원을 2차원으로 바꾸는힘i*m + j 암기!!!!i*m + j 공식이 어떻게 2차원 배열을 1차원으로 변환하는지 설명예를 들어 2x3 배열이 있다고 해보죠:1 2 34 5 6이 공식이 작동하는 방식을 단계별로 설명하겠습니다:각 행(i)마다 건너뛰어야 하는 개수:첫 번째 행(i=0): 0개 건너뜀 (0*m)두 번째 행(i=1): m개 건너뜀 (1*m)세 번째 행(i=2): 2m개 건너뜀 (2*m)열 위치(j)를 더하기:j=0: 첫 번째 열j=1: 두 번째 열j=2: 세 번째 열예시로 (1,2) 위치의 경우:i=1, j=2, m=3일 때1*3 + 2 = 5즉, 1차원 배열에서 5번 위치가 됨이렇게 변환하는 이유:비트마스크는 1차원으로만 동작2차원 위치를 1차원으로 고유하게 매핑해야 함각 위치가 겹치..

[알고리즘] 백준 2234 성곽 // 비트마스킹, vis의 값에 의미를 부여하라, i번째 비트끄기

https://www.acmicpc.net/problem/2234 * 풀이1connted component, 구역수 세기는 잘 풀었다.int dfs, 전체에대해 dfs돌리면서 cnt를 세면됨방문조건에 bit가 들어간다.dy,dx에 따라 동서남북을 체크하고 해당비트가 꺼져있으면 next로 이동한다.문제는 벽을하나씩 부스는것이 문제다.첫풀이벽을하나씩 부스면서 (i번째 bit를 끄면서) 똑같이 dfs를 돌리고, 원복하면 될거라고 생각했다.문제점이웃한 벽도 같이 부서줘야함매번 dfs 돌기전에 vis를 초기화 해줘야함현재는 벽제거후 그곳에서만 dfs호출, 벽을제거한후 모든 지점에서 dfs를 호출해야 완탐이됨//n^2 C 1 * 4(동서남북) 벽제거 memset(vis,0,sizeof(vis)); f..

[알고리즘] 백준 1062 가르침 // 조합, 비트마스킹, 백트래킹

https://www.acmicpc.net/problem/1062* 내 풀이최초풀이 : 막구현 -> 26C13 (최악의경우) = 1천만 -> 시초a,n,t,i,c는 무조건 뽑아야함 -> 미리선택, 비트켜기입력: N, K 입력받기 N개의 단어 입력받아 arr에 저장필수 처리: if K #include using namespace std;typedef long long ll;int n,k,ret;int study[26];vector arr;void go(int subset) { memset(study,0,sizeof(study)); for(int i=0;i v) { if(v.size()==k) { memset(study,0,sizeof(study)); fo..

[알고리즘] 백준 1987 알파벳 // 비트마스킹, i번째 비트켜짐확인, vis를 숫자1개로 나타내는 힘

https://www.acmicpc.net/problem/1987* 고민했던 부분비트마스킹 발상하기N이 30미만 -> 비트마스킹 도전 -> vis를 숫자 1개로 나타내보자.알파벳을 숫자로 표현하기A - 'A' =0B-A = 1 C-A = 2...A를 1로 (1B를 2로 (1C롤 4로 표한하면 되겠다! (11을 알파벳-'A'만큼 밀면 현재 비트가 나온다! // (1i번째 비트가 켜진것을 확인하기(상태 & 현재비트) !=0 -> i번째 비트는 켜진것. -> already visited주의사항비트연산에는 항상 괄호를 사용할것!모든 탐색이 끝나고 return 될때 정답갱신하는 부분을 어디에 둘지* 의사코드알고리즘: 알파벳 보드에서 중복되지 않는 알파벳으로만 이동하는 최장 경로 찾기입력:- R: 보드의 행 개수-..

[알고리즘] 백준 19942 다이어트 // 비트마스킹, 1-idx

https://www.acmicpc.net/problem/19942* 개선할점비트마스킹 패턴 암기필요subset 은 정수 1 부터 2^n -1 (255)까지이를 비트연산 하면서 비트가 켜져있으면, 해당 원소를 선택한다.if문아래에 로직을 넣는다.이때, 선택된원소들은 1-idx이므로 i+1 해준값을 결과에 저장한다.정답이 여러개인 경우map>>에 가격별 정답후보들을 담는다. // m[300] : {1,2,3 / 4,5,6}이를 정렬후 m[ret][0]을 꺼내면 원하는 idx들이 출력된다. * 전체코드#include using namespace std;typedef long long ll;int n,mp,mf,ms,mv;int arr[16][6];int ret=987654321; //최소비용구하기, 초기화=..

[알고리즘] 백준 17471 게리멘더링 // 비트마스킹, dfs 구역체크는 노드1곳에서 시작

https://www.acmicpc.net/problem/17471* 행동영역dfs 구역체크는 노드1곳에서만 시작해라 * 오답정리이전에 dfs를 모든노드에서 하고있었음그런데, 연결확인을 위해서는 첫노드에서 시작하는것만으로 충분함!필요없이 반례) 1-2 / 3-4 인경우1,2,3이 구역1에 묶일때, visit 체크를 맨위에서 해주기때문에 {1,2,3}은 한구역이라고 잘못판단함.애초에 구역 1에서 dfs를 했으면 이런 문제가 없음! * 의사코드전체 코드의 흐름을 단계별로 정리: 1. **입력 처리**    - N개의 구역과 각 구역의 인구수 입력    - 각 구역별로 인접한 구역 정보를 입력받아 양방향 그래프 생성 2. **모든 가능한 분할 시도** (비트마스킹 활용)    - 1부터 2^N-1까지 모든 경..

[알고리즘] 백준 1285 동전뒤집기 // 비트마스킹, 상태가 2개면 비트마스킹을 생각

https://www.acmicpc.net/problem/1285* 행동영역상태가 2개면 비트마스킹을 생각하라* 풀이일단 시간복잡도가 2^40 아닌가? -> 각행, 각열을 완탐but, 행만 완탐후, 열은 최적해가 정해져있음 -> 직접뒤집을필요x, 상태가 2개이므로 절반보다 크면 뒤집고 아니면 안뒤집으면 됨 -> 2^20핵심은 동전의 상태가 2개-> 0과 1 비트 숫자 1개로 상태를 저장하는 것임배열에 넣는경우, 뒤집는 연산 for(~~~) 을 직접해야함.a[i] : 행 i 의 상태 저장재귀함수go(here) : here번째 행의 동전을 뒤집은경우, 안뒤집은경우동전을 뒤집는 연산을 ~ 으로 구현백트래킹으로 완전탐색리턴조건n이 다찼을때,각 열 (|) 을 탐색 할 변수 i : 1, 2, 4, 8 ... // ..

리트코드 1비트의 갯수 c++ //비트마스킹, 최하위 1지우는법

https://leetcode.com/problems/number-of-1-bits/description/1. 최하위 1지우는법n=n&(n-1) 하면 된다.ex) 11 & 10 == 10으로 최하위 1이 지워진다. 2. 1갯수 세는법 i) n을 2진수로 바꾸는 로직을 이용하면 된다.ii) 최하위 1을 계속 지우고 cnt++ 하면된다. n이 1이상인동안 3. 전체코드i)class Solution {public: int hammingWeight(int n) { //coutii)class Solution {public: int hammingWeight(int n) { int cnt=0; while(n){ n=n&(n-1); ..