분류 전체보기
[백준 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..
[프로그래머스 C++] 숫자 카드 나누기
[프로그래머스 C++] 숫자 카드 나누기
2023.12.21[프로그래머스 C++] 숫자 카드 나누기 https://school.programmers.co.kr/learn/courses/30/lessons/135807 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 최대 공약수 GCD 수학, 구현 정답코드 #include #include #include using namespace std; // 유클리드 호제법을 사용하여 GCD를 찾음 int gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b); } int solution(vector arrA, ve..
[백준 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); // 각 마을 간의 도로 정보를 저장하는..
[백준 1043번 C/C++] 거짓말
[백준 1043번 C/C++] 거짓말
2023.12.13[백준 1043번 C/C++] 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 해결전략 Set 처음 시도한 코드 - 테스트 케이스 모두 통과 #include #include #include using namespace std; int n, m; // n: 사람의 수, m: 파티의 수 int k; // k: 진실을 아는 사람의 수 set truth; // 진실을 아는 사람들을 담는 배열 int nVisiters; // nVisiters: 파티에 오는..