⭐ 코딩테스트/백준
[백준 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; //..
[백준 12851번 C/C++] 숨바꼭질2
[백준 12851번 C/C++] 숨바꼭질2
2024.01.08[백준 12851번 C/C++] 숨바꼭질2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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: 동생이 있는 위치 int minTime = 2147000000, num; // 최소 시간, 방법의 수 vector ch(100001, -1)..
[백준 17144번 C/C++] 미세먼지 안녕!
[백준 17144번 C/C++] 미세먼지 안녕!
2024.01.05[백준 17144번 C/C++] 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 해결전략 브루트포스 Brute Force, 구현 정답코드 #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int r, c, t; vector v; int airLocY, airLocX; void Spread(int y..
[백준 2096번 C/C++] 내려가기
[백준 2096번 C/C++] 내려가기
2024.01.04[백준 2096번 C/C++] 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 해결전략 동적계획법 Dynamic Programming, DP 슬라이딩 윈도우 알고리즘 Sliding Window Algorithm 처음 시도한 코드 - 메모리 초과 #include #include using namespace std; int n; vector v; vector dp, dpMax; int minValue = 2147000000, maxValue = 0; i..
[백준 15486번 C/C++] 퇴사2
[백준 15486번 C/C++] 퇴사2
2024.01.03[백준 15486번 C/C++] 퇴사2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 해결전략 동적계획법 Dynamic Programming, DP 처음 시도한 코드 - 시간초과 #include #include using namespace std; int n; int total; vector T, P; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(..