BAEKJOON/자료 구조 (59) 썸네일형 리스트형 백준 1777번 [순열복원](C++)-yes6686- 티스토리 백준 문제 풀이: 1777 [순열복원]문제 링크: https://www.acmicpc.net/problem/1777문제 설명:길이가 n인 순열이 주어질 때, 순열을 복원하는 문제입니다. 주어진 입력은 각 순열의 원소가 올바른 위치에 들어가기 위해 필요한 남은 빈자리의 개수를 의미합니다. 세그먼트 트리를 사용하여 효율적으로 순열을 복원합니다.문제 해결 코드#include using namespace std;int arr[100001];int ans[100001];int tree[400001];int init(int n, int s, int e) { if (s == e) { return tree[n] = 1; } return tree[n] = init(2 * n, s, (s + .. 백준 1517번 [버블 소트](C++)-yes6686- 티스토리 백준 문제 풀이: 1517 [버블 소트]문제 링크: https://www.acmicpc.net/problem/1517문제 설명:버블 소트 알고리즘으로 주어진 배열을 정렬할 때, 몇 번의 swap이 발생하는지 계산하는 문제입니다. 단순히 O(n²)의 버블 소트를 구현하는 대신, 세그먼트 트리를 사용해 효율적으로 해결합니다.문제 해결 코드#include #include #include using namespace std;vector> arr;int tree[2000001];int init(int n, int s, int e) { if (s == e) { return tree[n] = 1; } return tree[n] = init(2 * n, s, (s + e) / 2) + in.. 백준 2243번 [사탕상자](C++)-yes6686- 티스토리 백준 문제 풀이: 2243 [사탕상자]문제 링크: https://www.acmicpc.net/problem/2243문제 설명:사탕 상자에 여러 가지 맛의 사탕이 있으며, 이 사탕들을 꺼내거나 추가할 수 있는 기능을 제공합니다. 사탕 상자는 총 1,000,000개의 칸으로 이루어져 있으며, 각 칸에 사탕이 들어 있습니다. 두 가지 작업을 수행합니다:맛의 순서에 따라 사탕을 꺼내는 작업특정 맛의 사탕을 추가하는 작업문제 해결 코드#include using namespace std;int arr[1000001];int tree[4000001];int query(int n, int s, int e, int d) { if (s == e) return e; if (tree[2 * n] >= d) { .. 백준 5676번 [음주 코딩](C++)-yes6686- 티스토리 백준 문제 풀이: 5676 [음주 코딩]문제 링크: https://www.acmicpc.net/problem/5676문제 설명:양수, 음수, 또는 0으로 이루어진 배열에 대해 주어진 구간의 곱의 부호를 구하거나, 특정 인덱스의 값을 변경하는 작업을 효율적으로 처리하는 문제입니다. 세그먼트 트리를 이용하여 O(log n) 시간 안에 구간 곱 계산과 값 변경을 처리합니다.문제 해결 코드#include using namespace std;int arr[100001];int t[400001];int init(int n, int s, int e) { if (s == e) { return t[n] = arr[s]; } else { return t[n] = init(2 * n, s.. 백준 12837번 [가계부 (Hard)](C++)-yes6686- 티스토리 백준 문제 풀이: 12837 [가계부 (Hard)]문제 링크: https://www.acmicpc.net/problem/12837문제 설명:1부터 N까지 번호가 매겨진 계좌의 금액을 관리하며, 다음 두 가지 작업을 효율적으로 수행하는 문제입니다:타겟 계좌에 금액 추가특정 구간의 계좌 합을 계산각 작업에 대해 효율적인 시간 복잡도를 유지해야 하므로 세그먼트 트리를 사용합니다.문제 해결 코드#include using namespace std;long long int arr[1000001];long long int t[4000001];long long int sum(int n, int s, int e, int l, int r) { if (r e) return 0; if (l > n >> m; .. 백준 2268번 [수들의 합 7](C++)-yes6686- 티스토리 백준 문제 풀이: 2268 [수들의 합 7]문제 링크: https://www.acmicpc.net/problem/2268문제 설명:1부터 N까지 번호가 매겨진 배열의 값을 갱신하거나, 특정 구간의 합을 구하는 작업을 효율적으로 수행하는 문제입니다. 세그먼트 트리를 사용하여 O(log n) 시간 복잡도로 각 작업을 처리합니다.문제 해결 코드#include using namespace std;int arr[1000001];long long int t[3000001];long long int sum(int n, int s, int e, int l, int r) { if (r e) return 0; if (l > n >> m; int a, b, c; for (int i = 0; i > a.. 백준 1275번 [커피숍2](C++)-yes6686- 티스토리 백준 문제 풀이: 1275 [커피숍2]문제 링크: https://www.acmicpc.net/problem/1275문제 설명:주어진 배열에서 구간 합을 빠르게 구하고, 특정 위치의 값을 변경할 수 있는 세그먼트 트리를 구현하여 질의에 응답하는 문제입니다.문제 해결 코드#include #include using namespace std;long long int arr[1000001];long long int seg[4000001];long long int go(int n, int s, int e) { if (s == e) { return seg[n] = arr[s]; } else { int mid = (s + e) / 2; long long int le.. 백준 6218번 [Balanced Lineup](C++)-yes6686- 티스토리 백준 문제 풀이: 6218 [Balanced Lineup]문제 링크: https://www.acmicpc.net/problem/6218문제 설명:주어진 소 구간에 대해 최대 값과 최소 값의 차이를 구하는 문제입니다. 이를 빠르게 계산하기 위해 세그먼트 트리를 사용합니다.문제 해결 코드#include #include using namespace std;int arr[100001];struct Seg { int ma; int mi;};Seg seg[400001];Seg go(int n, int s, int e) { if (s == e) { seg[n].ma = arr[s]; seg[n].mi = arr[s]; return seg[n]; } el.. 이전 1 2 3 4 5 6 7 8 다음
