⭐ 코딩테스트/백준
[백준 2573번 C/C++] 빙산
[백준 2573번 C/C++] 빙산
2024.08.26[백준 2573번 C/C++] 빙산 https://www.acmicpc.net/problem/2573 해결전략 너비우선탐색 BFS 정답코드 #include #include #include using namespace std;int dirY[4] = { -1, 0, 1, 0 };int dirX[4] = { 0, -1, 0, 1 };struct Info { int y, x;};int n, m;vector> v;queue Q;void GlacierMelting(){ vector> temp = v; queue nextQ; while(!Q.empty()) { int y = Q.front().y; int x = Q.front().x; Q.pop(); int adjOceans = 0; for (int i..
[백준 20055번 C/C++] 컨베이어 벨트 위의 로봇
[백준 20055번 C/C++] 컨베이어 벨트 위의 로봇
2024.08.23[백준 20055번 C/C++] 컨베이어 벨트 위의 로봇 https://www.acmicpc.net/problem/20055 해결전략 구현, 브루트 포스 Brute Force 정답코드 #include #include #include using namespace std;int n, k; // n: 컨베이어 길이, k: 내구도가 0인 칸의 개수 한계수int answer; // 몇 번째 단계인가deque> dQ; // 내구도, 로봇 배치 여부int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 0; i > input; dQ.push_back({ inp..
[백준 1062번 C/C++] 가르침
[백준 1062번 C/C++] 가르침
2024.08.19[백준 1062번 C/C++] 가르침 https://www.acmicpc.net/problem/1062 해결전략 비트마스킹 Bitmasking백트래킹 정답 코드 #include #include #include #include #include using namespace std;int n, k; // n: 단어의 수, k: 배울 수 있는 알파벳의 수int answer; // 최대 읽을 수 있는 단어의 수를 저장하는 변수int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; vector words(n); // 단어들을 저장할 벡터 for (int i = 0; i >..
[백준 2098번 C/C++] 외판원 순회
[백준 2098번 C/C++] 외판원 순회
2024.08.08[백준 2098번 C/C++] 외판원 순회 https://www.acmicpc.net/problem/2098 해결전략 비트마스킹 Bitmasking동적계획법 Dynamic Programming, DP비트필드를 이용한 다이나믹 프로그래밍 외판원 순회 문제 정답 코드 #include #include #include using namespace std;int n; // 도시의 수vector> W; vector> dp;const int INF = 2147000000;int TSP(int cur, int visited){ // visited의 모든 비트가 1이라면(즉, 모든 도시를 방문했다면), 현재 도시에서 시작 도시로 돌아가는 비용을 반환 if (visited == (1 > n; W.res..
[백준 14391번 C/C++] 종이 조각
[백준 14391번 C/C++] 종이 조각
2024.08.07[백준 14391번 C/C++] 종이 조각 https://www.acmicpc.net/problem/14391 해결전략 비트마스킹 Bitmasking 정답코드 #include #include #include using namespace std;int n, m;int answer = 0;vector> v;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; v.resize(n, vector(m)); for (int y = 0; y > c; v[y][x] = c - '0'; // 문자를 숫자로 변환 } } // Rule 정하기: 0이면 세로, 1이..
[백준 15661번 C++] 링크와 스타트
[백준 15661번 C++] 링크와 스타트
2024.08.06[백준 15661번 C++] 링크와 스타트 https://www.acmicpc.net/problem/15661 해결전략비트마스킹 Bitmasking백트래킹 Backtracking 정답코드 - 비트 마스킹 #include #include #include using namespace std;int n; // 팀의 인원 수int answer = 987654321;vector> v;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; v.resize(n, vector(n)); for (int y = 0; y > v[y][x]; } } // 모든 가능한 팀 조합을 비트마스크로 생성 for (unsigned int bitmask..
[백준 11723번 C/C++] 집합
[백준 11723번 C/C++] 집합
2024.08.05[백준 11723번 C/C++] 집합 https://www.acmicpc.net/problem/11723 해결전략 비트마스킹 Bitmasking 정답 코드 #include using namespace std;int m;int answer;int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> m; string input, int x; for (int i = 0; i > input; if (input == "add"){ cin >> x; answer |= (1 > x; answer &= ~(1 > x; if (answer & (1 > x; answer ^= (1
[백준 1052번 C/C++] 물병
[백준 1052번 C/C++] 물병
2024.08.05[백준 1052번 C/C++] 물병 https://www.acmicpc.net/problem/1052 해결전 수학 그리디 알고리즘 비트마스킹 각 물병은 서로 다른 물병과 합쳐질 수 있다. 이 합치는 과정은 물병의 2진수로 표현한다.예를 들어, 물병 3개(2진수로 11)를 2개씩 합치면 2진수 100이 되어 물병 1개가 된다. 물병을 모두 합쳐서 k개의 물병 이하로 만들어야 한다.n이 k보다 작거나 같으면 추가 물병이 필요 없으므로 0을 반환합니다.비트마스킹n의 2진수 표현에서 1의 개수는 현재 물병의 수가 어떻게 조합될 수 있는지를 나타낸다.int BitCnt(int x)n의 2진수 표현에서 1의 개수가 k보다 많으면, 물병을 추가하여 이 개수를 줄여야 한다. 이를 위해 n을 하나씩 증가시키면서 1의 ..
[백준 16938번 C/C++] 캠프 준비
[백준 16938번 C/C++] 캠프 준비
2024.08.02[백준 16938번 C/C++] 캠프 준비 https://www.acmicpc.net/problem/16938 해결전략 비트마스킹 Bitmasking백트래킹 Backtacking 정답코드 #include #include using namespace std;int n, l, r, x; // 문제의 개수, 난이도 합의 최소값, 난이도 합의 최대값, 가장 어려운 문제와 쉬운 문제의 난이도 차이 최소값vector A; // 각 문제의 난이도int answer; // 조건을 만족하는 경우의 수int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> l >> r >> x; A.resize(n); for (int i ..
[백준 2961번 C/C++] 도영이가 만든 맛있는 음식
[백준 2961번 C/C++] 도영이가 만든 맛있는 음식
2024.08.01[백준 2961번 C/C++] 도영이가 만든 맛있는 음식 https://www.acmicpc.net/problem/2961 해결전략 비트마스킹 Bitmasking 처음 시도한 코드 - 시간초과 #include #include #include using namespace std;int n;long long answer = 987654321;vector sour, bitter;vector> taste;void DFS(int idx, vector& ch, set& foods){ if (idx == n){ long long sour = 1, bitter = 0; for (auto& iter : foods){ sour *= taste[iter].first; bitter += taste[iter].s..
[백준 2800번 C/C++] 괄호 제거
[백준 2800번 C/C++] 괄호 제거
2024.07.31[백준 2800번 C/C++] 괄호 제거 https://www.acmicpc.net/problem/2800 해결전략 문자열재귀비트마스킹 Bitmasking 정답코드 1 - 비트마스킹 사용 #include #include #include #include using namespace std;string input; // 문제에서 주어진 문자열int n;vector> brackets; // 괄호 한 쌍의 위치를 저장set results; // 만들 수 있는 문자열을 기록// 괄호 쌍의 위치를 찾는 함수void FindBrackets(){ stack bracketLocation; // 문자열을 순회하며 괄호 쌍을 찾음 for (int i = 0; i ch){ if (idx == n){ resul..
[백준 15787번 C/C++] 기차가 어둠을 헤치고 은하수를
[백준 15787번 C/C++] 기차가 어둠을 헤치고 은하수를
2024.07.30[백준 15787번 C/C++] 기차가 어둠을 헤치고 은하수를 https://www.acmicpc.net/problem/15787 해결전략 비트마스킹 BitMasking 정답코드 #include #include #include using namespace std;int n, m; // n: 기차의 수, m: 명령의 수int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; vector v(n, 0); for (int i = 0; i > orderIdx >> train; train--; // 0-based index로 변환 if (orderIdx == 1 || o..