⭐ 코딩테스트/백준
[백준 14569번 C/C++] 시간표 짜기
[백준 14569번 C/C++] 시간표 짜기
2024.07.29[백준 14569번 C/C++] 시간표 짜기 https://www.acmicpc.net/problem/14569 해결전략 비트마스킹 Bitmasking 정답코드 #include #include using namespace std;int n; // 총 과목의 수int m; // 학생의 수vector lectures; // 각 과목의 시간표를 비트마스크로 저장할 벡터// 시간표를 비트마스크로 변환하는 함수unsigned long long ConvertToBitmask(const vector& times){ unsigned long long binary = 0; for (int i = 0; i > n; lectures.resize(n); for (int i = 0; i > k; ..
[백준 14503번 C/C++] 로봇 청소기
[백준 14503번 C/C++] 로봇 청소기
2024.07.28[백준 14503번 C/C++] 로봇 청소기 https://www.acmicpc.net/problem/14503 해결전략 구현 정답코드 #include #include using namespace std;int dirY[4] = { -1, 0, 1, 0 };int dirX[4] = { 0, 1, 0, -1 };int n, m;int currY, currX, currDir;vector> v;int answer; // 청소하는 칸의 개수bool Move(int y, int x, int dir){ // 4 방향 체크 for (int i = 0; i > n >> m; v.resize(n, vector(m)); cin >> currY >> currX >> currDir; for (int y = 0;..
[백준 17135번 C/C++] 캐슬 디펜스
[백준 17135번 C/C++] 캐슬 디펜스
2024.07.25[백준 17135번 C/C++] 캐슬 디펜스 https://www.acmicpc.net/problem/17135 해결전략 구현 Brute Force, 너비우선탐색 BFS시뮬레이션 Simulation 정답 코드 #include #include #include #include #include using namespace std;// 방향 벡터 (좌, 상, 우)int dirY[3] = { 0, -1, 0 };int dirX[3] = { -1, 0, 1 };int n, m, d; // 행, 열, 궁수의 공격 거리int answer; // 제거할 수 있는 적의 최대 수vector archers; // 궁수의 위치vector> v; // 초기 적..
[백준 13335번 C/C++] 트럭
[백준 13335번 C/C++] 트럭
2024.07.24[백준 13335번 C/C++] 트럭 https://www.acmicpc.net/problem/17070 해결전략 동적 계획법 Dynamic Programming, DP 정답코드 #include #include using namespace std;int n;vector> v, result;int dp[16][16][3]; // 0: 가로, 1: 세로, 2: 대각선int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; v.resize(n, vector(n)); result.resize(n, vector(n)); for (int y = 0; y > v[y][x]; } } dp[0][1][0] = 1; // 시작 위치(문..
[백준 13335번 C/C++] 트럭
[백준 13335번 C/C++] 트럭
2024.07.21[백준 13335번 C/C++] 트럭 https://www.acmicpc.net/problem/13335 해결전략 큐 Queue 정답코드 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, w, l; cin >> n >> w >> l; vector v(n); for (int i = 0; i > v[i]; } queue> Q; // (트럭 무게, 다리 위에서의 시간) int time = 0, totalWeight = 0, i = 0; while (i
[백준 16287번 C/C++] Parcel
[백준 16287번 C/C++] Parcel
2024.07.17[백준 16287번 C/C++] Parcel https://www.acmicpc.net/problem/16287 해결전략 조합 탐색 (Combination Search), 부분 합 (Subset Sum Problem), 정렬 (Sorting) 여러 숫자 중 특정 개수(이 경우에는 4개)의 숫자를 선택하여 그 합이 특정 값이 되는지 찾는다.네 숫자의 합이 목표값 w가 되는지를 찾는 것이므로 부분합 문제의 변형으로 볼 수 있다. 정답코드 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int w, n; // ..
[백준 11401번 C/C++] 이항 계수 3
[백준 11401번 C/C++] 이항 계수 3
2024.06.02[백준 11401번 C/C++] 이항 계수 3 https://www.acmicpc.net/problem/11401 해결전략 분할 정복을 이용한 거듭제곱 모듈로 곱셈 역원 페르마의 소정리 사실상 수학문제다. 모듈로 곱셈 역원과 페르마의 소정리를 찾아본 후 풀었다. 정답코드 #include using namespace std;const int MOD = 1000000007; long long n, k; long long answer; // 팩토리얼 계산 함수 (start부터 end까지의 곱을 계산)long long fact(long long start, long long end) { long long ret = 1; // 반환 값 초기화 for (int i = start; i >..
[백준 2138번 C/C++] 전구와 스위치
[백준 2138번 C/C++] 전구와 스위치
2024.05.20[백준 2138번 C/C++] 전구와 스위치 https://www.acmicpc.net/problem/2138 해결전략 그리디 알고리즘 Greedy Algorithm 정답코드 #include #include #include using namespace std; int n; // 스위치의 개수를 저장할 변수string initial; // 초기 문자열string target; // 목표 문자열void ToggleSwitch(int k, string& v) // 스위치를 조작하는 함수, k번째 스위치를 누르면 k-1, k, k+1의 상태가 변경됨{ if (0 > n; cin >> initial; // 초기 문자열 입력 cin >> target; // 목표 문자열 ..
[백준 15685번 C/C++] 드래곤 커브
[백준 15685번 C/C++] 드래곤 커브
2024.05.07[백준 15685번 C/C++] 드래곤 커브 https://www.acmicpc.net/problem/15685 해결전략 구현 처음 시도할 때, 그려지는 모든 좌표를 기록한 후 재귀를 돌려 90도 회전시켰다. 좋지 않은 방법이고 재귀이기 때문에 시간초과가 나온다. 핵심 아이디어vector dots;꼭지점의 좌표가 아닌 방향을 저장한다생성되는 꼭지점을 dots 배열에 담는다. 이 때, 배열의 값은 방향이다.배열의 값(=방향)을 회전시킬 때 업데이트한다. 정답 코드 #include #include using namespace std;int dirY[4] = { 0, -1, 0, 1 };int dirX[4] = { 1, 0, -1, 0 };int n; // 커브의 개수vector> v(101, vect..
[백준 16236번 C/C++] 아기 상어
[백준 16236번 C/C++] 아기 상어
2024.05.04[백준 16236번 C/C++] 아기 상어 https://www.acmicpc.net/problem/16236 해결전략 너비우선탐색 BFS 아기 상어가 물고기를 먹은 시점에 BFS를 다시 돌려야 한다. 처음 시도한 코드 #include #include #include using namespace std;int dirY[4] = { -1, 0, 1, 0 };int dirX[4] = { 0, -1, 0, 1 };int n;vector> v;int answer;bool success = false;struct Info{ int y, x, feed, sharkSize;};void BFS(int startY, int startX, int feed, int size, int time){ int timeSpe..
[백준 14499번 C/C++] 주사위 굴리기
[백준 14499번 C/C++] 주사위 굴리기
2024.05.04[백준 14499번 C/C++] 주사위 굴리기 https://www.acmicpc.net/problem/14499 해결전략 구현 x, y 좌표가 대다수의 코딩테스트 문제의 반대여서 헷갈렸다. 문제를 이해하는데 많은 시간이 걸렸다.이동할 때마다 주사위가 구른다. ' 북 >> 남 >> 서 >> 동' 순서로 주사위는 굴러간다. 정답코드 #include #include using namespace std;int n, m;int startX, startY;int k; // 명령의 개수vector> v;vector dice(6);// [0]// [4][1][5]// [2]// [3]void Roll(int dir){ vector tmp(6); if (dir == 1){ // 동 tmp[..
[백준 1520번 C/C++] 내리막 길
[백준 1520번 C/C++] 내리막 길
2024.04.23[백준 1520번 C/C++] 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해결전략 깊이우선탐색 + 다이나믹 프로그래밍, Dynamic Programming DFS + DP (= 메모이제이션) DFS로만 풀면 시간초과가 나온다. DFS 풀이: 시간초과 #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int..