Algorithm/비트마스킹

리트코드 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); ..

리트코드 a+b c++ // 비트연산 덧셈구현방법

https://leetcode.com/problems/sum-of-two-integers/1. 의사코드sum(합, 캐리) :기저사례 캐리가0캐리가없는경우, a^b가 a+b이다.캐리가있는경우 (a&b)가 0이아닌경우, 캐리는 (a&b)  합(a^b)에 캐리를 더해줘야한다.캐리가 없을때까지11(2진수)+11(2진수)을 코드로 돌려보면 이해가 쉬울것이다. 2. 전체코드class Solution {public: int getSum(int a, int b) { if(b==0) return a; //기저사례 : carry가 0 int sum=a^b; //10 ^ 01 == 11, 둘다1인경우를 제외하고 덧셈완성 int carry=(a&b) 10

프로그래머스 2개이하로다른비트 c++ // 비트마스킹, 관찰, 규칙성발견

https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 관찰, 규칙성발견 1. 완탐 -> 너무 빡구현 & 10^15 -> 불가능 2. 관찰을 통한 규칙성발견 1(1) 2(10) 2(10) 3(11) 3(11) 5(101) 4(100) 5(101) 5(101) 6(110) 6(110) 7(111) 에서 최초0을찾고 // num and i ==false -> 최초0의 위치 그곳을 1로바꾸고 // *or1 -> 무조건 1이됨 이전비트를 0으로 바꾸면 ..

프로그래머스 메뉴리뉴얼 c++ // 비트마스킹 조합

https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 시행착오 a~y 모든 조합을 돌리고 하는방법 X 결론 : DB설정을 잘해서 저장하자. freq[size][문자열] = 등장횟수 2. 비트 -> 문자열 만드는법 비트가켜져있는경우 해당 문자를 더하면된다. if(subset & (1 A B C F G subset : 1 0 0 0 0 0 1 0 0 0 ... 1 1 0 0 0 ... */ for(auto order : orders){ //ABCF..

백준 17471 게리멘더링 c++ // 비트마스킹, dfs

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 의사코드 노드번호 : 6 5 4 3 2 1 비트마스킹 : 0 0 0 0 1 1 //값이 1인노드는 1번구역, 값이0인 노드는 0번구역을 뜻함. dfs를 돌았는데, 미방문노드가 있다? -> 불가능 2. 시행착오 - 문제 : 연결만되있으면 모두 방문이 되버리는 문제 dfs에 구역이 다르면 탐색을 끝내도록 로직추가함. 3. 전체코드 #include using namespace std; int n, people[11],..

백준 1285 동전뒤집기 c++ // 비트마스킹 개선방법

https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 1. 비트마스킹 개선방법 행탐색(2^20) * 열탐색(2^20) -> 2^40 -> 터진다. 해결 : 행만바꾼후, 열은 최적해가 정해져있다. -> 열을 노가다로 탐색X ex) HTT 가 열인경우, 뒤집으면 THH가 된다. -> 뒤집는게 최적해다! THH가 열인경우, 안뒤집는게 최적해다! 결론 : 행만뒤집은후, t가 절반보다많으면 뒤집으면된다! 2. 전체코드 #include using names..

백준 19942 c++ //비트마스킹, 벡터사전순 정렬방법

https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 1. 벡터사전순 정렬방법 vector 에 넣고 sort 돌리고 vv[0]을 취하면 된다. if (ret == w) { vector vv; vv.push_back(tmp); vv.push_back(arr); sort(vv.begin(), vv.end()); arr = vv[0]; } 2. 전체코드 #include using namespace std; int n, m, mp, mf, ms, mv; ..

프로그래머스 양과늑대 c++ // 상태기반 dfs 방법 , 비트마스킹

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 상태기반 dfs 방법 필요데이터 : 왼쪽자식번호, 우측자식번호, vis[0000001111] 상태에 추가된 비트정보 ex) 000001 (상태1) (0번노드 있는상태) 000011(상태3) (0번노드, 1번노드 있는상태) 001011(상태8+2+1) (0번노드,1번노드,3번노드 있는 상태) * 다음상태로 넘어가기 //다음상태로 넘어가기 for(int i=0;i