인덱스 트리 2

[백준] 2243번: 사탕상자 (c++)

문제 수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다. 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다. 수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 ..

알고리즘/BOJ 2022.01.10

[알고리즘] 인덱스 트리(Indexed Tree)

인덱스 트리란? 포화 이진 트리 형태의 자료구조로 부모 노드가 자식 노드의 대표값을 가지는 트리이다. 리프 노드에 사용할 값들을 적어놓고, 부모 노드에 값들의 합을 모아놓은 형태이다. 글보다 아래 그림 예제를 보면 쉽게 이해할 수 있다. 언제 사용? 배열 A가 있고 아래 두 연산을 M번 수행해야 하는 문제가 있다고 하자. 1️⃣ 구간 l, r이 주어졌을 때 A[l]+A[l+1]+...+A[r-1]+A[r]을 구해라 2️⃣ i번째 수 A[i]를 X로 바꾸어라 N개의 수가 있다고 할 때 일반적인 방법으로는 1번 연산을 수행하는데는 O(N), 2번 연산을 수행하는 데에는 O(1)이 걸려 결과적으로 시간 복잡도는 O(NM)이 된다. 누적합 배열을 사용해서 풀게 되어도 1번 연산 O(1), 2번연산 O(N)으로 ..

알고리즘/공부 2022.01.05
반응형