인덱스드트리3

• 

  [c++] 백준 - 달리기 (인덱스드 트리) 1. 문제 2. 입출력 3. 예제 입출력 4. 문제 해설 처음에 이 문제를 읽었을 때는 왜 플래티넘 4인가 했다. 단순히 자신보다 앞에 있는 수 중 자신보다 큰 수의 숫자를 구하면 되는 것이 아닌가?라는 생각이 들었다. 그런데 문제 조건을 확인하니 선수의 수 N은 최대가 500000이고 만약 위의 방법을 적용하면 대략 O(N^2)의 시간복잡도를 갖게 된다. 500000 * 5000000 = 25000000000000 = 20조의 연산 횟수가 늘어나고 만약 break문을 통해 중간중간 가지치기를 해준다해도 시간 제한이 1초라는 것은 대략 1억번의 연산안에 결과가 나와야하는 것인데 O(N^2)알고리즘으로는 불가능하다는 생각이 들었다. 가능한 시간 복잡도는 O(NlogN)정도였다. 결국 알고리즘 분류를 봐버렸.. c++/알고리즘 2023. 2. 3.

• 

  [c++] 백준 사탕상자 - 인덱스드 트리 1. 문제 2. 입 출력 예제 입 출력 4. 문제 해설 문제의 조건을 살펴보자 사탕 상자에 수정이가 손을 댄 횟수는 n(1 = OFFSET){ //offset은 원본 배열의 시작 점 update(i-OFFSET +1, -1); // 하나씩 빼준다. return i - OFFSET + 1; // 사탕의 맛은 1부터 시작이나 원본배열은 OFFSET(짝수)부터 시작하므로 } if(Tree[i * 2] >= rank) { return query(rank, i*2); // 만약 왼쪽 자식 노드의 값이 구하고자 하는 값보다 크거나 같다면 }else { return query(rank - Tree[i*2] , i*2+1); // 왼쪽 자식 노드의 값이 구하고자 하는 값보다 부족하다면 오른쪽 자식 노드로 이동 } } .. c++/알고리즘 2023. 2. 2.

• 

  [c++] 인덱스드 트리에 관하여 1. 인덱스드 트리란? 인덱스드 트리란 어떤 수열이 존재할 때 각 구간의 대표값들로 이루어진 트리를 의미한다. 주로 부분합, 부분 곱, 부분 차 등 구간 별 값을 구해야하는 상황에서 많이 사용된다. 또한 수열의 값이 자주 변경되는 상황에서도 많이 사용된다. 누적 합 배열과 같이 처음부터 순서대로 누적되는 합의 배열을 구하는 방식의 경우 중간에 하나의 값이 변경되면 그 값의 인덱스부터 수열의 끝까지 다시 누적합을 구해야하는 치명적인 단점이 있다. 만약 제일 처음 원소가 변경되었다면 모든 누적합 배열을 처음부터 다시 계산해야한다.O(N)이 걸린다. 기본적으로 트리라는 자료구조는 O(logN)의 시간복잡도를 위한 자료구조이다. 시간복잡도를 얻는 대신 공간복잡도를 살짝 trade-off하긴 하지만 요즘 메모리는.. c++/알고리즘 2023. 2. 1.