본문 바로가기

Algorithm/BOJ (백준)

 (19)
[C++] 백준 2042 구간 합 구하기 [!NOTE]세그먼트 트리 자료 구조에 대한 설명을 보려면 다음 포스트 참조: 세그먼트 트리 (Segment Tree) - C/C++로 설명세그먼트 트리는 구간 합이나 최소값, 최대값을 구하는 데 유용한 자료구조이다. 특히 데이터가 자주 업데이트되면서도 특정 구간의 값을 빠르게 조회해야 하는 문제에서 큰 효율성을 제공한다. 이번 글에서는 백준 온라인 저지의 2042번 문제, 구간 합 구하기를 통해 세그먼트 트리를 구현하고 문제를 해결하는 과정을 설명한다.문제 설명N개의 수가 주어질 때, 중간에 특정 수를 변경하면서 주어진 구간의 합을 빠르게 구하는 문제이다.예제 입력 설명1부터 5까지의 수가 주어지고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지의 합을 구하라고 한다면 결과는 17이 된다. 그 상태에..
[C] 백준 2268 수들의 합 7 https://www.acmicpc.net/problem/2268문제 분석 및 접근 방식문제에서 요구하는 것은 배열 A에 대해 두 가지 연산을 효율적으로 처리하는 것이다:Sum(i, j): 배열의 A[i]부터 A[j]까지의 합을 구하는 연산.Modify(i, k): 배열의 A[i]를 k로 업데이트하는 연산.제약 조건에 따르면 배열의 크기(N)와 연산 횟수(M) 모두 최대 1,000,000으로, 최악의 경우 Sum과 Modify 연산을 모두 포함하여 최대 백만 번의 연산을 수행해야 한다. 단순히 모든 구간을 반복하며 합을 구하거나, 각 Modify 연산에 대해 배열을 새로 갱신하면 시간 초과가 발생할 가능성이 높다.따라서 구간 합과 부분 배열 업데이트를 모두 빠르게 수행할 수 있는 자료 구조가 필요하다. ..
[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..
[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

티스토리툴바