⭐ 코딩테스트/백준
[백준 9935번 C/C++] 문자열 폭발
[백준 9935번 C/C++] 문자열 폭발
2024.01.02[백준 9935번 C/C++] 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 해결전략 문자열 처음 시도한 코드 - 메모리 초과 #include #include using namespace std; string input, boom; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> input >> boom; while(true) { ve..
[백준 5639번 C/C++] 이진 검색 트리
[백준 5639번 C/C++] 이진 검색 트리
2023.12.28[백준 5639번 C/C++] 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 해결전략 깊이 우선 탐색 DFS 트리 후위 순회 정답 코드 #include #include using namespace std; vector v; void DFS(int start, int end) { if (start >= end) { return; } if (start == end - 1) { cout
[백준 1967번 C/C++] 트리의 지름
[백준 1967번 C/C++] 트리의 지름
2023.12.26[백준 1967번 C/C++] 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 해결전략 깊이우선탐색 DFS 정답코드 #include #include using namespace std; struct Node { int next; int cost; }; int n; int maxCost, maxNode; // maxCost: 최대 비용, maxNode: 최대 비용을 가지는 노드 번호 vector v; //vecto..
[백준 15655번 C/C++] N과 M (6)
[백준 15655번 C/C++] N과 M (6)
2023.12.25[백준 15655번 C/C++] N과 M (6) https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답코드 #include #include #include using namespace std; int n, m; vector v; vector result; int ch[9]; // 선택된 숫자의 사용 여부를 체크하는 배열 void BackT(int idx, int cnt) { if(cnt == m)..
[백준 15654번 C/C++] N과 M (5)
[백준 15654번 C/C++] N과 M (5)
2023.12.24[백준 15654번 C/C++] N과 M (5) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답코드 #include #include #include using namespace std; int n, m; vector v; vector result; int ch[9]; // 선택된 숫자의 사용 여부를 체크하는 배열 void BackT(int cnt) { if(cnt == m){ for(int..
[백준 9465번 C/C++] 스티커
[백준 9465번 C/C++] 스티커
2023.12.239465번 C/C++] 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 해결전략 동적구현법, 다이나믹 프로그래밍 Dynamic Programming (DP) 정답 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { ..
[백준 1799번 C/C++] 비숍
[백준 1799번 C/C++] 비숍
2023.12.22[백준 1799번 C/C++] 비숍 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 해결전략 백트랙킹 Backtracking 처음 시도한 코드 #include #include #include using namespace std; int n; // 체스판의 크기 n x n vector v; vector place; int answer; // 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수 bool CheckDiagonals(int y, int x, v..
[백준 13549번 C/C++] 숨박꼭질 3
[백준 13549번 C/C++] 숨박꼭질 3
2023.12.20[백준 13549번 C/C++] 숨박꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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는 목표 위치 vector dist(100001, 2147000000); // dist 벡터는 각 위치에 도달하는 데 필요한 최소 시간을 저장 int..
[백준 11725번 C/C++] 트리의 부모 찾기
[백준 11725번 C/C++] 트리의 부모 찾기
2023.12.19[백준 11725번 C/C++] 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해결전략 트리 Tree 너비우선탐색 BFS vector v[ ] v[1] 6, 4 v[2] 4 v[3] 6, 5 v[4] 1, 2, 7 v[5] 3 v[6] 1, 3 v[7] 7 Q 1 6 4 3 2 7 ... 정답 코드 #include #include #include using namespace std; int n; vector v(100001); // 각 노드의 연결정보를 저장할 2차원 벡터 // vecto..
[백준 15650번 C/C++] N과 M(2)
[백준 15650번 C/C++] N과 M(2)
2023.12.18[백준 15650번 C/C++] N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 해결전략 조합 Combination, 백트랙킹 Backtracking 정답 코드 #include #include using namespace std; int n, m; int arr[9], ch[9]; // arr는 선택된 수를 저장하는 배열, ch는 해당 수가 선택되었는지를 확인하는 체크 배열 void DFS(int idx, int cnt) // ..
[백준 9251번 C/C++] LCS (Longest Common Subsequence, 최장 공통 부분 수열)
[백준 9251번 C/C++] LCS (Longest Common Subsequence, 최장 공통 부분 수열)
2023.12.15[백준 9251번 C/C++] LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결방안 다이나믹 프로그래밍 Dynamic Programming, DP LCS (Longest Common Subsequence, 최장 공통 부분 수열) 정답 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(fal..
[백준 1238번 C/C++] 파티
[백준 1238번 C/C++] 파티
2023.12.14[백준 1238번 C/C++] 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해결전략 Dijkskra 다익스트라 정답 코드 #include #include #include using namespace std; int n, m, x; // n: 마을의 수(각각의 마을에 1명의 학생이 거주), m: 단방향 도로 수, x: 파티가 벌어지는 마을 vector v(1001); // 각 마을 간의 도로 정보를 저장하는..