본문 바로가기

c++

 (15)
[C++] 백준 2042 구간 합 구하기 [!NOTE]세그먼트 트리 자료 구조에 대한 설명을 보려면 다음 포스트 참조: 세그먼트 트리 (Segment Tree) - C/C++로 설명세그먼트 트리는 구간 합이나 최소값, 최대값을 구하는 데 유용한 자료구조이다. 특히 데이터가 자주 업데이트되면서도 특정 구간의 값을 빠르게 조회해야 하는 문제에서 큰 효율성을 제공한다. 이번 글에서는 백준 온라인 저지의 2042번 문제, 구간 합 구하기를 통해 세그먼트 트리를 구현하고 문제를 해결하는 과정을 설명한다.문제 설명N개의 수가 주어질 때, 중간에 특정 수를 변경하면서 주어진 구간의 합을 빠르게 구하는 문제이다.예제 입력 설명1부터 5까지의 수가 주어지고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지의 합을 구하라고 한다면 결과는 17이 된다. 그 상태에..
[C++] 백준 6603 로또 6603 로또 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net (1) 일반적 풀이 C++ // // Created by SangWon Kang on 2020/09/04. // Copyright © 2020 SangWon Kang. All rights reserved. // #include using namespace std; typedef long long ll; typedef vector vi; typedef pair pii; typedef vector vpii; #define INF 987654..
[C++] 백준 15650 N과 M (2) 15650 N과 M (2) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net C++ // // Created by SangWon Kang on 2020/09/04. // Copyright © 2020 SangWon Kang. All rights reserved. // #include using namespace std; typedef long long ll; typedef vector vi; typedef pair pii; typedef vector vpii; #define INF 987654321 #defin..
세그먼트 트리 (Segment Tree) - C/C++로 설명 세그먼트 트리(Segment Tree)는 효율적으로 구간합이나 최소값, 최대값을 구하는 데 매우 유용한 자료구조이다. 특히, 데이터가 자주 업데이트되면서도 특정 구간의 값을 빠르게 조회해야 하는 상황에서 효과적이다. 다음은 세그먼트 트리의 기본 개념과 사용법을 예제를 통해 정리한 내용이다.세그먼트 트리 - 쓰임새세그먼트 트리는 연속적인 데이터가 있을 때, 특정 범위의 합/ 최소, 최대값 등을 구할 때 유용하게 활용될 수 있다.특정 구간의 합을 구하는 방법에 대해 살펴보자면, 일반적으로 다음과 같은 방법이 떠오른다..   1. $arr[l] + arr[l+1] + ... + arr[r-1] + arr[r]$을 일일히 더해 구하는 방법  2. $i$번째까지의 합을 저장하는 배열을 하나 더 만들어서, 조금 더..
[C/C++] 백준 11092 Safe Passage 11092 Safe Passage 11092번: Safe Passage A group of friends snuck away from their school campus, but now they must return from the main campus gate to their dorm while remaining undetected by the many teachers who patrol the campus. Fortunately, they have an invisibility cloak, but it is only lar www.acmicpc.net C++ #include #include #include using namespace std; vector list; int DP (int e) { if(..
[C/C++] 백준 14501 퇴사 14501 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 마지막 날부터 거꾸로 생각하면 풀기 쉬워진다. DP[i]: n 번째 날부터 i 번째 날까지 일했을 때 얻는 최대 이익. DP[i]는 두 가지 경우로 나눌 수 있는데, i 번째 날에 잡힌 상담을 하는 경우와 그렇지 않은 경우이다. i 번째 날에 잡힌 상담을 하지 않는 경우: DP[i] = DP[i + 1]과 같다 할 수 있다. i 번째 날에 잡힌 상담을 하는 경우: DP[i] = DP[ i + (i 번째 날에 잡힌 상담 일수)] + (i 번째 날에 잡힌 상담의 금액) 이때 i + (i 번째 잡힌 상담 일수)가 n+1을 넘으면 일을 할 수 없으므로 예외 처리를 해준다. C #include..
[C/C++] 백준 12865 평범한 배낭 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 C #include #define MAX(a, b) (((a) > (b)) ? (a) : (b)) int DP[103][100003]; int w[103]; int v[103]; int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 1; i n >> k; for (int i = 1; i > w[i] >> v[i]; for ..
[C++] 백준 2482 색상환 2482 색상환 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net C++ #include #include #include using namespace std; #define MOD 1000000003 int DP[1003][1003]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; for (int i = 0; i
[C++] 백준 11054 가장 긴 바이토닉 부분 수열 11054 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net C++ #include #include #include using namespace std; vector per; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, input; cin >> n; vector memo(n); // 거기까지의 최대 길이 vector memo2(n); // 거기서부터의 최대 길이 for (int i = 0; i > input; per...
[C++] 백준 1937 욕심쟁이 판다 1937 욕심쟁이 판다 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net C++ #include #include using namespace std; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int n; int DAE[503][503]; // 대나무 숲의 정보 int DP[503][503]; // Dynamic Programming int DPP(int x, int y) { if (DP[x][y]) return DP[x][y]; DP[x][y] =..
[C++] 백준 11066 파일 합치기 11066 파일 합치기 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 �� www.acmicpc.net C++ #include #include #include #define INF 987654321 using namespace std; typedef long long ll; int w[503]; int sum[503]; int DP[503][503]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int k; cin >> k;..
[C++] 백준 1699 제곱수의 합 1699 제곱수의 합 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net C++ #include #include #include using namespace std; typedef long long ll; int DP[100003] = {0, }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int t=1; t

티스토리툴바