비트마스킹비트마스킹은 비트 연산을 사용하여 특정 비트의 값을 설정, 지우기, 반전, 확인하는 기법이다. 비트마스크는 비트 연산을 수행할 때 사용되는 이진수 패턴을 의미한다. 비트마스킹은 시스템 프로그래밍, 임베디드 시스템, 저수준 하드웨어 제어 등에서 자주 사용된다. 주요 비트 연산자AND (&): 두 비트가 모두 1일 때만 1이 된다.OR (|): 두 비트 중 하나라도 1이면 1이 된다.XOR (^): 두 비트가 다르면 1이 된다.NOT (~): 비트를 반전시킨다.비트 쉬프트 (>): 비트를 왼쪽 또는 오른쪽으로 이동시킨다.비트마스킹의 주요 용도1. 특정 비트 설정#include using namespace std;int setBit(int num, int bitPosition) { int mask =..
전체 글
Hello World소수점 고정 출력cout C++에서는 숫자를 출력할 때 기본적으로 정수와 부동 소수점 형식을 제공한다. 부동 소수점 숫자를 출력할 때 과학적 표기법(ex: 1.23e+02)이나 일반 표기법을 사용할 수 있다. fixed 조작자는 부동 소수점 숫자를 고정 소수점 형식으로 출력하도록 지정한다. 사용법 fixed 조작자는 iostream 헤더에 정의되어 있으며 다음과 같이 사용할 수 있다.#include #include // setprecisionusing namespace std;int main() { double num = 123.456789; cout 기본 출력:기본적으로 cout은 부동 소수점 숫자를 출력할 때 가끔 과학적 표기법을 사용한다.fixed 사용cout 예를 들어, 123.4..
cin과 getline(), 그리고 cin.ignore()cin 객체 헤더파일에 포함된 입력 스트림 객체이다.공백, 탭, 엔텉와 같은 화이트 스페이스 문자를 무시하고 입력 받지만, 이 문자들은 버퍼에 그대로 남아있다는 점을 유의한다. #include using namespace std;int n;string s;int main() { cin >> n; cout > s; cout cin은 공백 이전까지만 입력을 받기 때문에, 공백을 포함해서 입력 받을 수 없다. 공백을 포함해서 입력을 받으려면 getline함수를 사용하면 된다. getline() getline()은 기본적으로 개행 문자 ('\n')를 줄의 끝으로 인식하고 개행 문자 직전까지 입력을 받는다. 만약 다른 종결 문자를 사용하고 싶다면, 이를 세..
배낭 문제(Knapsack)배낭문제는 여러 물건이 있을 때, 특정 조건을 만족하는 조합을 구하는 문제이다. 이를테면, 물건 n개가 있고 배낭에 m 만큼 채울 수 있을 때, 최대 무게를 초과하지 않는 범위 내에서 아이템들을 담을 수 있다. 각 아이템은 1개만 사용할 수 있고, 배낭의 무게 제한을 초과하지 않도록 아이템을 선택하여 배낭에 담아야 한다. 목표는 배낭에 담은 아이템들의 가치를 최대화하는 것이다. 문제 정의입력N: 아이템의 개수W: 배낭의 최대 무게각 아이템에 대해w_i: 아이템 i의 무게v_i: 아이템 i의 가치출력배낭의 최대 무게를 초과하지 않으면서 담을 수 있는 아이템들의 가치를 최대화한 값해결 방법0/1 배낭 문제를 해결하는 일반적인 방법은 동적계획법을 사용하는 것이다. DP 테이블을 사용..
코드#include #include #include using namespace std;typedef long long ll;int n,m,s,x,y;vector tree;vector a;void init(int node, int start, int end) { if (start == end) { tree[node] = a[start]; return; } else { int mid = (start + end) / 2; init(node*2, start, mid); init(node*2 + 1, mid + 1, end); tree[node] = tree[node*2] + tree[node*2 + 1]; }}ll query(int node, int start, int e..
코드#include #include #include using namespace std;int n,k,w,v, a[100003][103];vector> itm;int go(int weight, int idx) { if(weight > k) return -987654321; // 무게 제한을 벗어나면 무효 if(idx == n) return 0; // 모든 물건을 확인한 경우 종료 if(a[weight][idx] != -1) return a[weight][idx]; // 이미 계산된 값 // 배낭을 선택하는 경우와 선택하지 않는 경우 비교 int include = go(weight + itm[idx].first, idx + 1) + itm[idx].second; int exclude = go(..
코드#include #include #include #include using namespace std;typedef long long ll;int n,m,cnt, indegree[1003], input[1003];vector adj[1003];vector res;int main() { cin >> n >> m; for(int i = 0; i > cnt; for(int j = 0; j > input[j]; } for(int j = 0; j q; for(int i = 1; i 풀이유향 비순환 그래프이고, 조건에 맞는 순서 구하기이기 때문에 위상정렬 알고리즘을 선택했다. 문제에서 주어진 입력 마지막에서 2 3을 3 2로 바꾸면 정할 수 없다고 했는데 이..
코드#include #include #include using namespace std;int n,r,q,u,v,k,res, visited[100003],dp[100003];vector adj[100003];// dfs로 그래프를 순회하면서, dp 배열에 값 저장 => 서브트리에 속한 정점의 수 저장int dfs(int x) { if(dp[x] != 0) return dp[x]; // 메모이제이션 visited[x] = 1; int ret = 1; for(int i : adj[x]) { if(!visited[i]) { ret += dfs(i); } } dp[x] = ret; return ret;}int main() { ..
코드#include #include using namespace std;typedef long long ll;ll n, a[5003],res, sol = 20000000009;int solution[4]; // 결과 저장int main() { cin >> n; for(int i = 0; i > a[i]; sort(a, a + n); // 하나는 고정을 위해 for문으로 전부 순회 for(int i = 0; i 절대값 if(abs(tmp) 0) { e--; } // 0보다 용액이 작으면, 더 큰 값을 찾아야하므로 s++ else { s++; ..
코드#include using namespace std;int n, s, a[100003], psum[100003], st = 1, en = 1, res = 200004;int main() { cin >> n >> s; for (int i = 1; i > a[i]; for (int i = 1; i = s) { res = min(res, en - st + 1); st++; } else { en++; } } if (res == 200004) res = 0; cout 풀이처음에는 dp인가 했다가, 연속된 구간이고, 구간합을 구하는 문제였기 때문에 투포인터를 떠올렸다. 구간합 배열을 만들어주고 포..