⭐ 코딩테스트/백준
[백준 17179번 C/C++] 케이크 자르기
[백준 17179번 C/C++] 케이크 자르기
2023.08.11[백준 17179번 C/C++] 케이크 자르기 https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 해결전략 이분탐색, 매개변수 탐색 코드 #include #include #include using namespace std; // n: 자르는 횟수, m: 자를 수 있는 위치 개수, l: 롤 케이크의 길이를 저장 int n, m, l; // v: 자르는 위치를 저장할 벡터 vector v; // 목표한 크..
[백준 26069번 C/C++] 붙임성 좋은 총총이
[백준 26069번 C/C++] 붙임성 좋은 총총이
2023.08.10[백준 26069번 C/C++] 붙임성 좋은 총총이 https://www.acmicpc.net/problem/26069 26069번: 붙임성 좋은 총총이 첫번째 줄에는 사람들이 만난 기록의 수 $N\ (1 \le N \le 1\ 000)$이 주어진다. 두번째 줄부터 $N$개의 줄에 걸쳐 사람들이 만난 기록이 주어진다. $i + 1$번째 줄에는 $i$번째로 만난 사람들의 이름 $A_i$ www.acmicpc.net 해결전략 map map은 key와 value를 가지는데 key값을 검색할 수 있기 때문에 다른 자료형보다 검색이 편리하다. if (myMap.find("KeyName") != myMap.end()) 으로 검색하면 된다. map은 중복을 허용하지 않는다. 이 문제처럼 사람 이름에 중복이 없다면, ..
[백준 2178번 C/C++] 미로 탐색
[백준 2178번 C/C++] 미로 탐색
2023.08.09[백준 2178번 C/C++] 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해결전략 너비 우선 탐색 (BFS) BFS (Breadth-First Search, 너비 우선 탐색) 알고리즘이 최단 거리를 찾는데 사용한다. 그렇기 때문에 중간에 거리의 최솟값을 min으로 체크할 필요가 없다. BFS 알고리즘은 시작점에서 어떤 정점까지의 최단 경로를 찾을 때 사용한다. 그 이유는 BFS가 넓이 우선으로 탐색하기 때문에, 현재 정점에서 인접한 모든 정점들을 먼저 처리한 ..
[백준 16493번 C/C++] 최대 페이지 수
[백준 16493번 C/C++] 최대 페이지 수
2023.08.08[백준 16493번 C/C++] 최대 페이지 수 https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net 해결전략 Dynamic Programming 다이나믹 프로그래밍, 동적 계획법 배낭 코드 #include #include using namespace std; int n, m;//n 일수, m 챕터의 수 vector day, chapter; vector dp; int main(){ ios::sync_with_stdio..
[백준 9084번 C/C++] 동전
[백준 9084번 C/C++] 동전
2023.08.03[백준 9084번 C/C++] 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 해결전략 Dynamic Programming 다이나믹 프로그래밍, 동적계획법 배낭 문제 해설 dp[ i ][ j ] 코드 #include #include using namespace std; int t, n, m; //t 테스트 케이스 수, n 동전의 가지 수, m 목표 금액 int main() { ios_base::sync_with_stdio(..
[백준 7579번 C/C++] 앱
[백준 7579번 C/C++] 앱
2023.08.02[백준 7579번 C/C++] 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 해결전략 Dynamic Programming 다이나믹 프로그래밍, 동적 계획법 배낭 해설 dp[ i ][ j ] dp[ i ][ j ] = i개 이하의 메모리 앱을 사용하고, j 이하의 비용으로 확보할 수 있는 최대 메모리 크기 i \ j 1 0 0 30 30 30 30 30 30 30 30 30 30 30 30 30 2 10 10 40 40 40 40 40 40 40 ..
[백준 12865번 C/C++] 평범한 배낭
[백준 12865번 C/C++] 평범한 배낭
2023.08.01[백준 12865번 C/C++] 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 해결전략 Dynamic Programming 다이나막 프로그래밍 배낭 문제 풀이 int n, k; n 물품의 수, k 배낭의 최대 수용 무게 vector w, v; w[ i ] 각 물건의 무게 v[ i ] 각 물건의 가치 if (j >= w[i]) dp[i][j] = max(dp[i - ..
[백준 1629번 C/C++] 곱셈
[백준 1629번 C/C++] 곱셈
2023.07.31[백준 1629번 C/C++] 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 해결전략 병합 정렬 (Merge Sort), 분할정복 long long mod_pow(long long base, long long exponent, long long mod) base^exponent를 mod로 나눈 나머지를 반환한다. 지수가 0인 경우: base^0 = 1 다. 따라서 1을 반환한다. 지수가 홀수인 경우: base^(2 * k + 1) = (base^k) * (base^k) * base이므로 base를 한 ..
[백준 13305번 C/C++] 주유소
[백준 13305번 C/C++] 주유소
2023.07.28[백준 13305번 C/C++] 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 해결전략 Greedy Algorithm 탐욕 알고리즘 코드 #include #include using namespace std; int n, tmp; long long minCost; vector r; vector c; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)..
[백준 16234번 C/C++] 인구 이동
[백준 16234번 C/C++] 인구 이동
2023.07.26[백준 16234번 C/C++] 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 해결전략 너비 우선 탐색 BFS 코드 #include #include #include #include #include using namespace std; const int dy[4] = {-1, 1, 0, 0}; // 선언: 상, 하 이동 const int dx[4] = {0, 0, -1, 1}; // 선언: 좌, 우 이동 int n, l..
[백준 11404번 C/C++] 플로이드
[백준 11404번 C/C++] 플로이드
2023.07.25[백준 11404번 C/C++] 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해결전략 플로이드 워셜 Floyd-Warshall Algorithm 코드 #include #include #include using namespace std; int n, m; vectordist; const int INF = 2147000000 / 2;//최댓값 설정 int main() { ios::sync_with_stdio(false); cin.tie..
[백준 2293번 C/C++] 동전 1
[백준 2293번 C/C++] 동전 1
2023.07.24[백준 2293번 C/C++] 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 해결방안 Dynamic Programming (DP) 동적계획법 시도 코드 - 시간초과 #include #include using namespace std; int n, k; vector v; vector dp; int coin[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); c..