⭐ 코딩테스트
[백준 9466번 C/C++] 텀 프로젝트
[백준 9466번 C/C++] 텀 프로젝트
2024.01.22[백준 9466번 C/C++] 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 해결전략 깊이우선탐색 DFS 정답코드 #include #include using namespace std; int T; // 테스트 케이스의 수 int n; // 노드의 수 vector v; // 각 노드에서 다른 노드로의 링크를 저장하는 벡터 vector visited; // 각 노드의 방문 여부를 저장하는 벡터 vector done; // 각 노드가 처리되..
[백준 9252번 C/C++] LCS 2
[백준 9252번 C/C++] LCS 2
2024.01.20[백준 9252번 C/C++] LCS 2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결전략 LCS Longest 다이나믹 프로그래밍 Dynamic Programming 슬라이딩 윈도우 알고리즘 Sliding Window Algorithm 처음 시도한 코드 - 시간초과 #include #include using namespace std; string a, b; string answer; in..
[백준 2166번 C/C++] 다각형의 면적
[백준 2166번 C/C++] 다각형의 면적
2024.01.19[백준 2166번 C/C++] 다각형의 면적 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 해결전략 기하학. 다각형의 넓이 실수한 부분 - 주어진 점들의 순서를 조작하면 안 된다 #include #include #include #include // 소수점 자리 설정을 위한 헤더. setprecision() 사용가능 using namespace std; struct Coor{ double x; double y; }; bool Compare(Coor& a, Coor& b)..
[백준 2252번 C/C++] 줄 세우기
[백준 2252번 C/C++] 줄 세우기
2024.01.18[백준 2252번 C/C++] 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 해결 전략 위상 정렬 Topological Sort Algorithm 정답 코드 #include #include #include using namespace std; int n, m; // n은 학생의 수, m은 키를 비교한 횟수 vector graph; // 각 학생의 키를 비교한 결과를 나타내는 그래프 vect..
[백준 1202번 C/C++] 보석 도둑
[백준 1202번 C/C++] 보석 도둑
2024.01.17[백준 1202번 C/C++] 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 해결전략 그리디 알고리즘 Greedy Algorithm 우선순위 큐 Priority Queue 멀티 셋 Multi Set 그리디 알고리즘 (1~2를 반복) 1. 가방의 용량이 작은 것부터 채운다. 2. 가격이 높은 보석부터 담는다. 1. 가방의 용량이 작은 것부터 채운다. - 입력받은 가방 정보를..
[백준 1005번 C/C++] ACM Craft
[백준 1005번 C/C++] ACM Craft
2024.01.16[백준 1005번 C/C++] ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 해결전략 위상 정렬 Toplogical Sort 처음 시도한 코드 - 시간초과 #include #include using namespace std; int T; // T: 테스트케이스 개수 int n, k; // n: 건물의 개수, k: 건물간의 건설순서 규칙의 총 개수 int w; // 승리하기 위해 건설해야 할 건물의 번호 int answe..
[백준 2239번 C/C++] 스도쿠
[백준 2239번 C/C++] 스도쿠
2024.01.15[백준 2239번 C/C++] 스도쿠 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답코드 #include #include using namespace std; vector v(9, vector(9)); vector zero; // 빈 칸의 위치를 저장하는 벡터 bool isPossible(int y, int x, int select) { // (y, x)에 select 숫자를 놓을때 해당 행과..
[백준 2473번 C/C++] 세 용액
[백준 2473번 C/C++] 세 용액
2024.01.14[백준 2473번 C/C++] 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 해결전략 Two Pointer 투 포인터 세 포인터를 사용하여 가능한 모든 용액의 조합을 검사하며, 그 중 합이 0에 가장 가까운 조합을 찾는다. i를 중앙 포인터로 사용하여 p1과 p2를 양쪽으로 이동시키는 방식을 사용하였다. p1, i, p2가 각각 다른 용액을 가리키도록 유지하면서 가능한 모든 조합을 검사한다. 합이 0보다 작으면 ..
[백준 11049번 C/C++] 행렬 곱셈 순서
[백준 11049번 C/C++] 행렬 곱셈 순서
2024.01.13[백준 11049번 C/C++] 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 해결전략 동적계획법 Dynamic Programming DP 정답코드 #include #include #include using namespace std; int n; vector v; vector dp; int Cal(int start, int end) // start에서 end까지의 행렬 곱의 최소 연산 수를 계산 { if(start..
[백준 2467번 C/C++] 용액
[백준 2467번 C/C++] 용액
2024.01.12[백준 2467번 C/C++] 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 해결전략 투포인터 알고리즘 two pointer algorithm 정답코드 #include #include #include using namespace std; int n; vector v; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; int input; for (..
[백준 1987번 C/C++] 알파벳
[백준 1987번 C/C++] 알파벳
2024.01.10[백준 1987번 C/C++] 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 해결전략 백트래킹, Backtracking 처음 시도한 코드 - set 써서 시간초과 #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; set alphabet; int..
[백준 2448번 C/C++] 별 찍기 - 11
[백준 2448번 C/C++] 별 찍기 - 11
2024.01.09[백준 2448번 C/C++] 별 찍기 - 11 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 해결전략 Recursion, 재귀 fractal, 프랙탈 삼각형 정답 코드 #include #include using namespace std; int n; vector v; char blank = ' '; char star = '*'; void Tree(int y, int x) // 별 그리기, (y, x)는 별의 꼭짓점 위치 { // 첫번째 줄 (꼭직점에 * 1개) v[y][x] = star; //..