목록전체 글 (578)
전자공학 및 알고리즘
백준 31845 - 카드 교환(C++)
문제 링크입니다. https://www.acmicpc.net/problem/31845 딜러와 카드를 주고 받을 때 얻을 수 있는 최고 점수를 구하는 문제입니다. 플레이어는 원하는 카드를 주고 받을 수 있기 때문에 항상 최고 점수 카드를 받고 최저 점수 카드를 주는 것이 최고입니다.따라서 먼저 정렬을 통해 카드의 점수를 정렬해줍니다. 순서대로 최고 점수 카드를 더하고, 최저 점수 카드를 없애면서, 각 턴들의 최고 점수들을 저장합니다. 마지막에 저장된 점수들 중에서 가장 큰 점수를 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include usin..
백준 31844 - 창고지기(C++)
문제 링크입니다. https://www.acmicpc.net/problem/31844 박스를 옮길 수 있는 조건을 찾아서 해결하는 문제입니다. 박스를 옮길 수 있는 조건은 2가지입니다. 1. 로봇 -> 박스 -> 도착점2. 도착점 해당의 경우가 아니라면 전부 -1을 출력해주면 되고해당 경우를 만족한다면 로봇과 도착점까지의 거리를 구해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;string arr;int st, fin, box;void solve() { if (st > arr; for (int i ..
백준 14438 - 수열과 쿼리 17 (C++)
문제 링크입니다. https://www.acmicpc.net/problem/14438 세그먼트 트리를 이용한 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #include #define INF LLONG_MAXusing namespace std;int N, M;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node) { if (st == fin) return Tree[node] = st; int mid = (st + fin) /..
백준 14428 - 수열과 쿼리 16(C++)
문제 링크입니다. https://www.acmicpc.net/problem/14428 세그먼트 트리를 이용한 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #include #define INF LLONG_MAXusing namespace std;int N, M;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node) { if (st == fin) return Tree[node] = st; int mid = (st + fin) /..
백준 1725 - 히스토그램(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1725 세그먼트 트리를 이용해 풀었습니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의 위치..
백준 6549 - 히스토그램에서 가장 큰 직사각형(C++)
문제 링크입니다. https://www.acmicpc.net/problem/6549 세그먼트 트리를 이용해 푸는 문제입니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의..
백준 12837 - 가게부(Hard) (C++)
문제 링크입니다. https://www.acmicpc.net/problem/12837 세그먼트 트리를 이용한 문제입니다.세그먼트 트리를 이용해 푸는 문제입니다. p일에 수입/지출이 계속 주어졌을 때, 원하는 날까지의 합을 구하는 문제입니다. N의 범위가 10^6까지이기에 일반적인 방법으로 더한다면 시간 초과가 생깁니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #define INF 987654321using namespace std;int N, Q;long long Index[1000001];vector Tree;long lon..
백준 2268 - 수들의 합 7 (C++)
문제 링크입니다. https://www.acmicpc.net/problem/2268 세그먼트 트리를 이용한 문제입니다. 더해야 하는 수들의 범위가 매우 크기에 일반적인 계산을 하면 시간초과가 생깁니다.따라서, 세그먼트 트리를 이용해 값을 더해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #define INF 987654321using namespace std;int N, M;long long Index[1000001];vector Tree;long long segment_tree(int st, int fin, int nod..
백준 1275 - 커피숍2(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1275 세그먼트 트리를 이용한 문제입니다. 세그먼트 트리를 이용해 푸는 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #define INF 987654321using namespace std;int N, Q;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node){ if (st == fin) return Tree[node] = Index[st]; in..
백준 11505 - 구간 곱 곱하기(C++)
문제 링크입니다. https://www.acmicpc.net/problem/11505 세그먼트 트리를 이용한 문제입니다. 세그먼트 트리를 통해 원하는 구간의 곱을 구하는 문제입니다. 먼저, 주어진 값을 통해서 세그먼트 트리를 만드는 과정이 필요합니다. 세그먼트 트리를 만들었다면, 주어진 a의 값을 통해서 트리를 변경하거나, 구간의 곱을 구하는 코드를 만들어야합니다. 1. 주어진 값으로 트리 변경하기-> 원하는 위치에 원하는 값으로 트리를 변경해야합니다. 1-1. 원하는 위치와 현재 탐색하는 범위가 맞는지를 확인해야 합니다. -> 위치가 다르다면, 값을 바꾸지 않고 현재 값을 그대로 return 해줍니다. 1-2. 탐색할 범위가 하나라면(시작범위와 끝 범위가 같다면) 해당 위치가 바꾸길 ..
백준 10868 - 최솟값(C++)
문제 링크입니다. https://www.acmicpc.net/problem/10868 10868번: 최솟값N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는www.acmicpc.net세그먼트 트리를 이용한 문제입니다.주어진 범위 안에서 가장 작은 값을 찾는 문제입니다. 일반적인 방법으로는, 배열을 for문으로 탐색 후 범위 안에 속한 값을 전부 비교해주게 됩니다. 하지만, 배열의 크기가 10^5이며, 주어지는 정수 쌍이 10^5이기에 시간 초과가 됩니다. 따라서, 세그먼트 트리를 이용해 일정 범위에서의 최솟값을 저장해주는 방법을..
백준 2357 - 최솟값과 최댓값(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100www.acmicpc.net세그먼트 트리를 이용해 푸는 문제입니다.주어진 N개의 값이 있을 때, M개만큼 (a, b)의 쌍이 주어집니다.이때, (a, b) 범위 안의 값의 최솟값과 최댓값을 구하는 문제입니다.N, M의 범위가 100,000까지 이기에 단순히 탐색을 한다면 시간 초과가 생길 것입니다.따라서, 세그먼트 트리를 이용해 탐색 횟수를 줄여 답을 구할 것입니다.하지만,..