문제 https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 Inversion Counting 문제를 세그먼트 트리를 이용해 해결하는 문제. 해결법은 다음과 같다. 한 기계의 쌍의 A라인의 위치를 a_idx, B라인에서의 위치를 b_idx라고하자. 이 기계의 케이블과 교차되기 위해서는 해당 기계의 A라인에서의 위치(a_new)가 a_idx보다 앞에 있고 B라인에서의 위치(b_new)가 b_idx보다..

문제 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 세그먼트 트리(구간 트리)를 이용해야 제한시간 안에 풀 수 있는 문제. 세그먼트 트리를 모른다면 간단한 풀이로는 이해하기 힘드므로 백준님의 깔끔한 설명을 보고 오자. 세그먼트 트리 (Segment Tree) - Baekjoon Online Judge 세그먼트 트리는 이름처럼 노드마다 자..

문제 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 세그먼트 트리를 응용하여 해결하는 문제. 기존의 세그먼트 트리는 구간의 합을 트리의 부모 노드에 저장했다면 본 문제에 적용하는 세그먼트 트리는 구간의 최솟값과 최댓값을 저장한다. 세그먼트 트리에 대해서 잘 모르겠다면 백준님의 게시글을 참조하자. 세그먼트 트리 (Segment Tree) - Baekjoon Onl..

문제 https://www.acmicpc.net/problem/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 풀이 solved.ac 난이도: Gold 1 부분합을 구하는 문제이지만 단순한 부분합 구현으로는 중간에 배열의 값이 바뀌면 다시 연속합을 구해줘야 하는 문제가 생긴다. 배열의 길이가 n이라면 중간에 바뀐 값으로 다시 연속합을 구하면 O(n)의 시간 복잡도가 소요된다. 해당 문제에서는 중간에 배열의 값 변경이 빈번히 일어나, 단순한 부..