목록PS/알고리즘 문제풀이 (157)
득이공간
[백준 C++] 10868 최솟값 - 세그먼트트리
10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net #include #include using namespace std; int Count, StartIndex; int MinTree[131072 * 2]; void SearchMinimumValue(int Start, int End) { int CurStart = StartIndex + Start; int CurEnd = StartIndex + End; int MinValue = 1000000001; while (CurStart..
[백준 C++] 2357 최솟값과 최댓값 - 세그먼트트리
2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net #include #include using namespace std; int Count, StartIndex; int MinTree[131072 * 2]; int MaxTree[131072 * 2]; void SearchTree(int N, int Start, int End) { int CurStart = StartIndex + Start; int CurEnd = StartIndex + End; int Min = 100000..
[백준 C++] 2042 구간 합 구하기 - 세그먼트트리
2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include #include using namespace std; int Count, StartIndex; long long SegmentTree[1048576 * 2]; void UpdateTree(int N, int Index, long long Value) { int Current = StartIndex + Index; SegmentTree[Current] = Value; for (int i =..
[백준 C++] 1991 트리 순회 - 이진트리
1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #include #include using namespace std; string PreorderTree; string InorderTree; string PostorderTree; char Tree[27][2]; void DFS(char Parent) { if (Parent == '.') { return; } char LeftChild = Tree[Parent - 65][0]; char RightChild = Tree[Parent - 65][1]; ..
[백준 C++] 1946 신입 사원 - 정렬
1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net #include #include #include using namespace std; vector OrderedList; void Test() { int N; cin >> N; OrderedList.reserve(N); OrderedList.clear(); pair Ranks; for (int i = 0; i > Ranks.first >> Ranks.second; OrderedList.emplace_back(R..
[백준 C++] 18870 좌표 압축 - 정렬
18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net #include #include #include using namespace std; int X[1000000]; set OrderedList; unordered_map Map; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 0; i > X[i];..
[백준 C++] 12015 가장 긴 증가하는 부분 수열 2 - 이분탐색
12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net #include #include #include using namespace std; vector LIS; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int Number; cin >> Number; LIS.emplace_back(Number); for (int i = 1; i > Number; if (Number < ..
[백준 C++] 2512 예산 - 이분탐색
2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net #include #include #include using namespace std; vector Weights; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; Weights.reserve(N); for (int i = 0; i > Weight; Weights.emplace_back(Weigh..
[백준 C++] 2110 공유기 설치 - 이분탐색
2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net #include #include #include using namespace std; vector Houses; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, C; cin >> N >> C; Houses.reserve(N); for (int i = 0; i > X; Hous..
[백준 C++] 1697 숨바꼭질 - 너비우선탐색
1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #include #include using namespace std; const int& MaxSize = 100000; int Map[MaxSize + 1]; queue SearchQueue; bool IsInSize(int Node) { return (Node >= 0 && Node > N >> K; SearchQueue.emplace(N); while (!SearchQueue.empty()) { int Current = Searc..