⭐ 코딩테스트/백준
[백준 1269번 C/C++] 대칭 차집합
[백준 1269번 C/C++] 대칭 차집합
2023.10.25[백준 1269번 C/C++] 대칭 차집합 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 해결전략 map 코드 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int a, b, sum = 0; cin >> a >> b; map m; for (int i = 0..
[백준 1929번 C/C++] 소수 구하기
[백준 1929번 C/C++] 소수 구하기
2023.10.22[백준 1929번 C/C++] 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 해결전략 소수 구하기 코드 #include using namespace std; int arr[1000001]; int main() { int m, n; cin >> m >> n; for (int i = 2; i
[백준 12100번 C/C++] 2048 (Easy)
[백준 12100번 C/C++] 2048 (Easy)
2023.10.16[백준 12100번 C/C++] 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 해결전략 구현 재귀적인 깊이 우선 탐색(DFS) 시뮬레이션 그리드 회전 정답 코드 #include #include #include using namespace std; int n; // nxn 격자 크기 vector v; // v: 원본 격자 int maxBlock; // 게임판에 존재하는 가장 큰 블록의 값 voi..
[백준 1946번 C/C++] 신입 사원
[백준 1946번 C/C++] 신입 사원
2023.10.11[백준 1946번 C/C++] 신입 사원 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 해결방법 탐욕 알고리즘 Greedy Algorithm 처음 시도한 코드 - 시간초과 #include #include #include using namespace std; int t, n; // t: 테스트 케이스 개수, n: 지원자 수 int answer; // 선발할 수 있는 신입사원의 최대 인원수 struct Stat { int d..
[백준 2667번 C/C++] 단지 번호 붙이기
[백준 2667번 C/C++] 단지 번호 붙이기
2023.09.24[백준 2667번 C/C++] 단지 번호 붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 해결전략 Breadth First Search (BFS), 너비우선탐색 코드 #include #include #include #include using namespace std; int n, cnt; // n: 맵의 크기, cnt: 단지의 크기 vector v, ch; // v: 입력받은 맵, ch: 방문 여부를 체크 vector house; // 단..
[백준 2206번 C/C++] 벽 부수고 이동하기
[백준 2206번 C/C++] 벽 부수고 이동하기
2023.09.20[백준 2206번 C/C++] 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 해결전략 너비우선탐색, Breadth-First Search (BFS) 코드 #include #include #include using namespace std; int n, m; //n: 세로, m: 가로 vector v; // nxm 맵 int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = {..
[백준 7562번 C/C++] 나이트의 이동
[백준 7562번 C/C++] 나이트의 이동
2023.09.01[백준 7562번 C/C++] 나이트의 이동 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 해결전략 너비우선 탐색, BFS 코드 #include #include #include #include // 메모리를 설정하는 함수들을 사용하기 위한 라이브러리 (예: memset) using namespace std; int t, n; // t: 테스트 케이스의 수, n: 체스판 한 변의 길이 int c, d; // 도착 위치 (c,d) int ch[30..
[백준 1697번 C/C++] 숨바꼭질
[백준 1697번 C/C++] 숨바꼭질
2023.08.31[백준 1697번 C/C++] 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해결전략 너비우선탐색, BFS 코드 #include #include #include using namespace std; int n, k; //n: 수빈 현재 점, k: 동생 점 queue Q; // 첫 번째 원소는 위치, 두 번째 원소는 해당 위치에 도달하기까지 걸린 시간 vector ch; //해당 위치를 방문했는지 여부를 체크..
[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2
[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2
2023.08.29[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해결 전략 최대 증가길이 수열, 이분 탐색 Longest Increasing Subsequence, LIS 처음 시도한 코드 - 시간 초과 #include #include using namespace std; int n, result; vector v, LIS; int main() { ios::sync_with_stdio(false)..
[백준 2580번 C/C++] 스도쿠
[백준 2580번 C/C++] 스도쿠
2023.08.20[백준 2580번 C/C++] 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 해결전략 재귀 백트랙킹 Backtracking DFS 코드 #include #include using namespace std; vector v(9, vector(9)); // 현재 위치 (y, x)에 newNum을 놓았을 때 유효한지 행, 열, 3x3 작은 사각형을 검사하는 함수 bool isSafe(int y, int x, int newNum) { // 행..
[백준 1012번 C/C++] 유기농 배추
[백준 1012번 C/C++] 유기농 배추
2023.08.18[백준 1012번 C/C++] 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결전략 깊이 우선 탐색 DFS 너비 우선 탐색 BFS 둘 다 가능하다 DFS 풀이 #include #include #include using namespace std; int t; //t 테스트 케이스의 개수 int m, n, k; //m 가로길이, n 세로길이, k 위치의 개수 int cnt; vector v; map myMap; int dirY[4] = { -1..
[백준 11660번 C/C++] 구간 합 구하기 5
[백준 11660번 C/C++] 구간 합 구하기 5
2023.08.16[백준 11660번 C/C++] 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 해결전략 Dynamic Programming (DP) 다이나믹 프로그래밍 누적 합 코드 #include #include using namespace std; int n, m; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >>..