⭐ 코딩테스트/백준
[백준 7682번 C/C++] 틱택토
[백준 7682번 C/C++] 틱택토
2024.04.20[백준 7682번 C/C++] 틱택토 https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 해결전략 구현 정답코드 #include #include using namespace std; vector v; bool isWin(int ny, int nx, char player) // 특정 플레이어가 이겼는지 확인하는 함수 { // 가로 틱택토 if (v[ny][nx] == player && v[ny][nx] == v[ny][nx + 1] && v[ny]..
[백준 15864번 C/C++] 사다리 조작
[백준 15864번 C/C++] 사다리 조작
2024.04.19[백준 15864번 C/C++] 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답 코드 #include using namespace std; int n, m, h; int ch[31][11]; bool Cal() { for (int start = 1; start > n >> m >> h; for (int i = 0; i > y >> x; ..
[백준 6087번 C/C++] 레이저 통신
[백준 6087번 C/C++] 레이저 통신
2024.04.16[백준 6087번 C/C++] 레이저 통신 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 해결전략 너비우선탐색 BFS 정답코드 #include #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int w, h;// w: 맵의 너비, h: 맵의 높이 int answer = 987654321;// 최소 거울 ..
[백준 2589번 C/C++] 보물선
[백준 2589번 C/C++] 보물선
2024.04.15[백준 2589번 C/C++] 보물선 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 해결전략 너비우선탐색 BFS 정답 코드 #include #include #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int r, c; vector v; int answer; void BFS(int startY, int startX..
[백준 3687번 C/C++] 성냥개비
[백준 3687번 C/C++] 성냥개비
2024.04.14[백준 3687번 C/C++] 성냥개비 https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 해결전략 구현 동적계획법 Dynamic Programming, DP 정답코드 #include #include #include using namespace std; int t; // 테스트 케이스의 개수 int n; // 성냥개비의 개수 // int num[10] = { 2, 5, 5, 4, 5, 6, 3, 7, 6, 6 }; // 각 숫자를 만드는데 필요한 성냥개비..
[백준 14890번 C/C++] 경사로
[백준 14890번 C/C++] 경사로
2024.04.13[백준 14890번 C/C++] 경사로 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 해결전략 구현 정답 코드 #include #include using namespace std; int n, l; // n: 지도의 크기, l: 경사로의 길이 int answer; vector v; bool RoadCheckY(int y) // y번째 행에 대해 경사로를 설치할 수 있는지 검사 { vector ch(n, vector(n, false)); for (int i = 0; ..
[백준 8980번 C/C++] 택배
[백준 8980번 C/C++] 택배
2024.04.10[백준 8980번 C/C++] 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 해결전략 그리디 Greedy Algorithm 각 택배를 가능한 한 먼저 배달해야 하는 목적지 마을 순으로 정렬. 각 마을별 남은 용량 계산 트럭이 각 마을을 방문할 때마다 특정 용량만큼의 박스를 싣고 내린다. 이를 관리하기 위해 capacity 벡터를 사용하여 각 마을별로 남은 용량을 관리한다. 초기값은 트럭의 최대 용량인 c로 설정한다. ..
[백준 24337번 C/C++] 가희와 탑
[백준 24337번 C/C++] 가희와 탑
2024.04.09[백준 24337번 C/C++] 가희와 탑 https://www.acmicpc.net/problem/24337 24337번: 가희와 탑 일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다. www.acmicpc.net 해결전략 그리디 Greedy Algorithm 가장 높은 빌딩의 높이 계산 int tallest = max(a, b); 가희와 단비 중 더 많은 건물을 볼 수 있는 사람이 볼 수 있는 가장 높은 건물의 높이를 결정한다. 이는 두 관점에서 공통적으로 보이는 가장 높은 건물이 된다. 건물 배치 가희와 단비 각각의 관점에서 볼 수 있는 건물들을 v1과 v2에 배치..
[백준 2931번 C/C++] 가스관
[백준 2931번 C/C++] 가스관
2024.04.08[백준 2931번 C/C++] 가스관 https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 해결전략 구현 정답코드 #include #include #include using namespace std; // 북서남동 int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int r, c; // r: 행 c: 열 vector v; // 격자판 pair Moscow, Zagreb; // 'M'과 'Z'의 위치 int resultY, resultX; // 누락된 파이프의 위치 struct Coor { int y, x, dir; }; void FindLostPipe() { // 누락된 파이프 부분을..
[백준 17825번 C/C++] 주사위 윷놀이
[백준 17825번 C/C++] 주사위 윷놀이
2024.04.03[백준 17825번 C/C++] 주사위 윷놀이 https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 해결전략 백트래킹 Backtracking 이 문제는 풀지 못하고 다른 사람의 풀이를 보았다. 백트래킹 문제인건 인지하였지만 문제 조건을 세팅하는게 힘들었다. 주어진 숫자들을 다소 하드코딩하여 배열로 세팅하는 과정이 필요하였다. 아래와 같이 6개의 배열을 준비하여 사용한다. 이 부분이 생각하기 힘들었다. vector dice(10); // 주사위 눈금 vector player(4); // 4개의 말이 위치한 칸의 번호 vector location(34); // 각 칸에서 다음 칸..
[백준 17136번 C/C++] 색종이 붙이기
[백준 17136번 C/C++] 색종이 붙이기
2024.03.26[백준 17136번 C/C++] 색종이 붙이기 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 해결전략 백트래킹 Backtracking 구현 처음 시도한 코드 #include #include #include using namespace std; int answer; // 색종이 최소 개수 vector result(5, 0); vector v; queue Q; bool isSquare(int y, int x, int ny, int nx)..
[백준 2623번 C/C++] 음악 프로그램
[백준 2623번 C/C++] 음악 프로그램
2024.03.21[백준 2623번 C/C++] 음악 프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 해결전략 위상 정렬 Topology Sort 정답코드 #include #include #include using namespace std; int n, m; // n: 가수의 수, m: 보조 PD의 수 vector v; // 각 가수의 진입차수 저장 벡터 vector graph; // 가수들의 순서 관계를 나타내는 그래프 bool i..