날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 2. 풀이 : Indexed Tree 3. 설명 각 부대의 군사 수 1, 4, 3, 5, 2를 구간합 트리로 표현하면 그림[1]과 같다. 그림[1]에서 6번 군인은 3번 부대에 속해 있으며, 6번 군인을 탐색하는 과정은 그림[2]와 같다. 2번 부대에서 3명의 감원이 일어나면 그림[3]과 같이 구간합 트리가 업데이트 된다. 그림[3]에서 6번 군인은 4번 부대에 속해 ..

Algorithm/Indexed Tree 2021. 9. 18. 19:27

1. 문제 : https://www.acmicpc.net/problem/1572 1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1 www.acmicpc.net 2. 풀이 : Indexed Tree 3. 시간복잡도 : O(NlogN) 4. 설명 단순하게 1부터 N까지 반복하면서 K개씩 정렬을하고 중앙값을 찾으면 풀릴 것 같지만 타임아웃이 발생하여 문제를 풀 수가 없다. 이 문제는 인덱스 트리에 K개의 입력값을 유지하면서 중앙값을 탐색하여 풀 수 있다. N=6, K=3, 입력값의 범위 0 ~ ..

Algorithm/Indexed Tree 2021. 6. 3. 23:19