-
2024 - 10- 22 C++ 코딩테스트 10주완성 D+49Language Grammar/C++ 2024. 10. 22. 20:55
비트마스킹 경우의 수
idx번째 비트끄기 S &= -(1 << idx) idx번째 비트 XOR 연산 S ^= ( 1 << idx) 최하위 켜져있는 비트 찾기 idx = (S & -S) 크기가 n인 집합의 모든 비트를 켜기 (1 << n) -1 idx번째 비트를 켜기 S |= ( 1 << idx) idx번째 비트가 켜져 있는지 확인하기 if(S & (1 << idx)) "idx 번째 비트가 켜져 있는지 확인하기" 를 활용하여 배열에 나오는 모든 경우의 수를 나열할 수 있다.
이 코드를 한번 보자
#include <bits/stdc++.h> using namespace std; const int n = 4; int main() { string a[n] = {"사과","딸기","포도","배"}; for(int i =0; i < (1 <<n); i++) { string ret = ""; for(int j =0; j < n; j++) { if(i & (1 << j)) { ret += (a[j] + " "); } } cout << ret << '\n'; } }먼저 a[n] 의 조합의 경우의 수는 2^n 으로 계산하면 되므로, 2^n 이 모든 경우의 수이다.
모든 경우의 수를 출력시키는 것이 목표이므로 이중 반복문의 상위 반복문의 조건은 i = 0 부터 1 << n 까지이다.
1 << n 을 십진법으로 표현하면 2^n 이기때문이다.
그리고 그안에 a[n] 의 크기만큼 반복문을 돌려서 만약 i & (1 << j ) 가 성립되면
결과물을 저장하는 String 형 변수 ret 안에 더하는 방식이다.
i & ( 1 << j ) 는 1 << j 의 예를 들어보자.
i 가 13이라는 십진수를 가지고 이를 이진법으로 나타내면 1101 이다.
j 는 0 ~ 4 까지 검사하므로 처음 1101 & 0001 을 하면 0001 이 되므로 true이다.
a[0] (사과)이 ret안에 저장된다.
1일때, 1101 & 0010 은 0 이므로 false이다. 넘어간다.
2일때, 1101 & 0100 은 true이고 a[2] (포도) 가 저장된다.
3일떄 1101 & 1000 은 true이고 a[3] (배) 가 저장된다.
따라서 i 가 13일때 "사과 포도 배" 순으로 출력된다!
이렇게 순차적으로 모든 경우의 수가 출력된다
비트마스킹 매개변수 전달
예전 DFS 탐색을 할때 썼던 탐색코드가 있다.
visited[ny][nx] = 1; dfs(ny,nx); visited[ny][nx] = 0;여기서 dfs(int ny,int nx) 는 재귀함수이다.
이때 탐색을 하다가 겹치는 부분이 있으면 무한탐색을 하기때문에
visited[ny][nx] = 1; 로 해주고 해당 탐색이 끝났을 때, visited[ny][nx] = 0 을 해주어 탐색 부분이 겹치지 않게 해결하였다.
근데 비트마스킹을 활용하면 이를 안쓰고도 간단하게 코드를 짤 수 있다.
#include <bits/stdc++.h> using namespace std; const int n = 4; string a[4] = {"사과", "딸기", "포도", "배"}; void go(int num) { string ret = ""; for(int i =0; i < n; i++) { if(num & (1 << i)) ret += a[i] + " "; } cout << ret << '\n'; return; } int main() { for(int i = 1; i <n; i++) { go(1 | (1 << i)); } }메인 함수인 go( 1 | 1 < i)) 부분에서 의도하는 바는 "사과" 에서 출발하여 "딸기" "포도" "배" 순으로 탐색을 하려고 하는 것이다.
원래 DFS 탐색으로 풀려면 "사과" "딸기" 에 해당하는 visited 배열의 값을 1로 변경한후 탐색을 이어가야하지만,
비트마스킹을 이용하면 해당되는 비트수만 이용하면 되므로, 더욱 더 간단하게 코드를 짤 수 있다.
하지만 이 비트마스킹을 이용한 코딩에도 문제가 있는데..
바로 검사하려는 배열의 범위가 31이 넘어갈 경우 2^30은 10억이 넘어가기 때문에 걸리는 시간이 너무 오래걸린다..!
따라서 배열의 범위가 30이하일 경우에 쓰는게 가급적으로 좋다.
백준 19942 문제 - 다이어트
식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다.
아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자.
이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.
재료 단백질 지방 탄수화물 비타민 가격 1 30 55 10 8 100 2 60 10 10 2 70 3 10 80 50 0 50 4 40 30 30 8 60 5 60 10 70 2 120 6 20 70 50 4 40 예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다.
대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.
입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.
입력
첫 줄에 식재료의 개수 N이 주어진다.
다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수(mp,mf,ms,mw)가 주어진다.
이어지는 N$N$개의 각 줄에는 i$i$번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이
5개의 정수 (pi,fi,si,vi,ci)와 같이 주어진다.
식재료의 번호는 1부터 시작한다.출력
첫 번째 줄에 최소 비용을 출력하고,
두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다.
같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.
조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.#include <bits/stdc++.h> using namespace std; //배열의 최대범위를 정의할 const int 형 변수 max_n = 18 //영양성분의 정보를 입력받을 정수형 2차원 배열 a[][] //식재료의 개수(세로)의 개수를 입력받을 정수형 변수 N //최소 비용을 저장할 정수형 변수 ret //조건을 만족하는 식재료의 번호를 저장할 1차원 vector desc_a //최소 영양성분의 정보를 입력받을 정수형 변수 mp,mf,ms,mw const int max_n = 18; int a[max_n][5],N,ret = 987654321,mp,mf,ms,mw; vector<int> desc_a; int main() { cin >> N; cin >> mp >> mf >> ms >> mw; for(int i =0; i < N; i++) { for(int j =0; j < 5; j++) cin >> a[i][j]; } for(int i =0; i <(1 << N); i++) { int min_a[1][5] = {0,}; vector<int> min_num; for(int j =0; j <N; j++) { if(i & (1 << j)) { for(int c =0; c <5; c++) { min_a[0][c] += a[j][c]; } min_num.push_back(j+1); if(min_a[0][0] >= mp && min_a[0][1] >= mf && min_a[0][2] >= ms && min_a[0][3] >= mw && min_a[0][4] <= ret) { if(desc_a.size() == 0) desc_a = min_num; if(min_a[0][4] < ret) { ret = min_a[0][4]; desc_a = min_num; } else if(min_a[0][4] == ret) { if(min_num.size() < desc_a.size()) { desc_a.clear(); desc_a = min_num; } else if(min_num.size() == desc_a.size()) { for(int i=0; i < min_num.size(); i++) { if(min_num[i] < desc_a[i]) { desc_a.clear(); desc_a = min_num; break; } else if(min_num[i] > desc_a[i]) break; } } } } } } } cout << (ret == 987654321 ? -1 : ret) << endl; if(desc_a.size() > 0) for(int i =0; i < desc_a.size(); i++) cout << desc_a[i] << " "; }예제는 통과하였지만 백준에서는 어김없이..
이라는 결과가 나온다!
아마 같은 집합이 1개이상 나오면 사전순으로 빠른걸 출력하는 조건문이 있어야하는데...
아무리 작성하고 테스트를 해보아도 결과물이 제대로 나오질 않는다..!!ㅠ
강의 실습코드를 보자
강의실습코드
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 987654321; int n, mp, mf, ms, mv; int b, c, d, e, ret = INF, sum; struct A{ int mp, mf, ms, mv, cost; }a[16]; map<int, vector<vector<int>>> ret_v; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; cin >> mp >> mf >> ms >> mv; for(int i = 0; i < n; i++){ cin >> a[i].mp >> a[i].mf >> a[i].ms >> a[i].mv >> a[i].cost; } for(int i = 1; i < (1 << n); i++){ b = c = d = e = sum = 0; vector<int> v; for(int j = 0; j < n; j++){ if(i & (1 << j)){ v.push_back(j + 1); b += a[j].mp; c += a[j].mf; d += a[j].ms; e += a[j].mv; sum += a[j].cost; } } if(b >= mp && c >= mf && d >= ms && e >= mv){ if(ret >= sum){ ret = sum; ret_v[ret].push_back(v); } } } if(ret == INF) cout << -1 << '\n'; else{ sort(ret_v[ret].begin(), ret_v[ret].end()); cout << ret << "\n"; for(int a : ret_v[ret][0]){ cout << a << " "; } } return 0; }이 코드의 로직을 살펴보자면 영양성분의 정보를 받기위해서 구조체를 이용하였고,
만약 같은 가격을 입력받으면 가격에 해당하는 인덱스번호에 접근하여 저장하는 방식이다.
그렇게 하여서 해당되는 인덱스번호가 ret이라고 하면 ret_v[ret] 안에 들어있는 vector의 값을 오름차순으로 정렬시키면
사전 순으로 빠른 것부터 정렬하는 것이 되는 것이다.
따라서 사전에서 제일 빠른 인덱스는 0이므로 ret_v[ret][0] 을 출력시키면 원하는 조건에 해당하는 집합이 나온다!
해당 코드의 실행순서를 보자!
1. 영양성분의 개수 N을 입력받는다.
2. N만큼 반복문을 돌려 영양성분 리스트를 입력받는다.
3. 영양성분의 최소조건 mp,mf,ms,mv 를 입력받는다.
4. i =0 부터 i < (1 << N) 까지 반복문을 돌린다.( 2^n 만큼 반복문 )
4-1. j =0 부터 j < N 까지 반복문을 돌린다. ( N 만큼 반복문 )
ㄴ 내부변수 : int b,c,d,e,sum , vector<int> v
4-1-1. i & (1 << j ) 가 참일 경우, i의 비트값중에 해당하는 것이므로 v 에 j값을 push_back 해주고
a[j]에 해당하는 값을 내부 변수 b,c,d,e,sum 에순서대로 더해준다.
4-1-2. 만약 영양성분의 최소조건 mp,mf,ms,mv 를 전부 만족시키고 sum의 값이 ret 보다 작거나 같을 경우
ret 의 값을 sum 의 값으로 대입시켜주고, ret_v에서 인덱스번호가 ret인 배열에 해당 v를 push_back 하여준다.
5. 위 과정이 끝난뒤, ret의 값이 그대로면 -1을 출력해주고 아니면 최솟값이 존재하는 것이므로 ret의 값 그대로 출력하여준다.
6. 만약 같은 최솟값을 가진 집합이 여러개 있을 경우를 대비하여,
ret_v[ret] 안에 값을 오름 차순으로 정렬시켜주고 ( sort(ret_v[ret].begin(),ret_v[ret].end() )
제일 앞의 값을 출력시켜준다(for(int a : ret_v[ret][0] ) cout << a << " ";)map<int, vector<vector<int>>> 를 이용하여
같은 결과물일 시, 결과물의 번호에 해당하는 인덱스의 번호에 저장하고 그 값을 정렬하여 출력한다는 로직을 생각지도 못하였다..!
앞으로 이 조건이 나올 경우에 참고하여 문제를 풀어봐야겠다
백준 1285 문제 - 동전 뒤집기
N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다.
그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다.
<그림 1>은 N이 3일 때의 예이다.
이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다.
예를 들어
<그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고,
<그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.
<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다.
<그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.
N2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다.
이때의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 20이하의 자연수 N이 주어진다.
둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다.
각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어진다.
(앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.)출력
첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.
실습코드
#include<bits/stdc++.h> #define maxn 200005 typedef long long ll; using namespace std; const int INF = 987654321; const int dy[] = {-1, 0, 1, 0}; const int dx[] = {0, 1, 0, -1}; int n, a[44], ret = INF; string s; void go(int here){ if(here == n + 1){ int sum = 0; for(int i = 1; i <= (1 << (n - 1)); i *= 2){ int cnt = 0; for(int j = 1; j <= n; j++) if(a[j] & i)cnt++; sum += min(cnt, n - cnt); } ret = min(ret, sum); return; } go(here + 1); a[here] = ~a[here]; go(here + 1); } int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> s; int value = 1; for(int j = 0; j < s.size(); j++){ if(s[j] == 'T')a[i] |= value; value *= 2; } } go(1); cout << ret << "\n"; return 0; }모든 경우의 수부터 막혀서 강의실습코드를 보고 이해하였다.
코드를 보고 설명을 들었는데도 세번정도 들어볼 정도로 나한테는 어려운 문제였다..!!
이 문제의 핵심로직은 행과 열을 전부 검사하는 것이 아닌,
행의 경우의 수를 모두 구한뒤, 그 뒤에 차례대로 열을 반전시켜비교하여서 "T"의 개수가 적은 열을 합쳐서
행의 경우의 수마다 생기는 최솟값을 도출해낸뒤, 최종 결과값과 비교하여 더 적은 수를 저장하는 방식이다.
이 코드의 실행순서를 확인해보자!
1. 행과 열의 개수 N을 입력받는다.
2. N만큼 반복문을 돌린다.
ㄴ2-1. 문자열 S를 입력받는다.(a[i] 행의 정보)
ㄴ2-2. 내부 정수형 변수 value 를 선언하고 초깃값을 1로 설정한다.(Value = 행을 십진수로 표현할 정수)
ㄴ2-3. 문자열 S의 크기만큼 반복문을 돌린다.
ㄴ 2-3-1. 만약 S[j] 가 "T"일 경우 a[i] = a[i] | value 를 하여, value값에 해당하는 비트를 켜준다.
ㄴ 2-3-2. 반복문이 증가될수록 비트값이 높아지는 것이므로 2를 곱하여준다.
3. void go(int here) 함수에 매개변수 1을 주어 호출한다.
ㄴ 3-1. go(here+1) 를 호출하여 다음 행으로 탐색시켜준다.
ㄴ 3-2. a[here] = ~a[here]; a의 행을 반전시킨다.
ㄴ 3-3. go(here+1) 를 호출하여 a행을 반전시킨 상태에서 다음행으로 넘어가준다.
이렇게 하면 모든 행을 반전 또는 반전되지않은 상태 모두 탐색할 수 있다.
ㄴ 3-4. 이렇게 재귀함수를 통하여 here == n + 1 이 될 경우 모든 행을 탐색한 경우이므로
ㄴ 3-4-1.반복문( i = 1; i <= ( 1 << (n-1)); i *= 2 ) =
비트의 처음부터 N-1까지 탐색할것이므로 2를 곱하여 탐색한다.
ㄴ 3-4-2. 반복문 ( j = 1; j <= n; j++ ) if ( a[j] & i ) cnt ++; =
행마다 탐색하는 비트부분과 비교하여 있을 시 "T" 가 있는 것이므로 Cnt++를 하여준다.
ㄴ 3-4-2-1. Cnt 와 n - Cnt를 비교하여(n - Cnt는 해당 열을 반전시킨 것) 적은 값을 Sum에 저장해준다.
ㄴ 3-4-3. Sum과 ret을 비교하여 더 적은 수를 ret에 저장해준다.
4. 최솟값인 ret을 출력시켜준다더럽게 어렵다.. 마치 dfs 탐색과 bfs 탐색문제를 처음 봤을 때 느낌..
나혼자로서는 일주일을 고민했어도 이 코드는 절대 안나왔을 꺼 같은 느낌이다..
비트마스킹도 절대 쉽지않음을 뼈저리게 느끼고 간다!
'Language Grammar > C++' 카테고리의 다른 글
2024 - 10- 28 C++ 코딩테스트 10주완성 D+52 (0) 2024.10.29 2024 - 10- 25 C++ 코딩테스트 10주완성 D+51 (2) 2024.10.25 2024 - 10- 18 C++ 코딩테스트 10주완성 D+48 (0) 2024.10.18 2024 - 10- 16 C++ 코딩테스트 10주완성 D+46 (0) 2024.10.16 2024 - 10- 09 C++ 코딩테스트 10주완성 D+45 (2) 2024.10.10