전체 글41 [PS를 위한 자료구조 10강] 펜윅 트리로 머지 소트 트리 구현하기 PS를 위한 자료구조 10강 # 펜윅 트리를 이용한 머지 소트 트리 # 에 대해 알아보겠습니다. 펜윅 트리로도 머지 소트 트리를 구현할 수 있습니다. 펜윅 트리의 치명적 단점에 대해 전달드렸듯이, 펜윅 트리는 [1, R] 구간의 쿼리만 처리가 가능합니다. 따라서 제한적 상황에서만 사용할 수 있습니다. [수열과 쿼리1] https://www.acmicpc.net/problem/13537 하지만 이 문제에서는 사용할 수 있습니다. [1, R] 구간의 K보다 큰 수 - [1, L-1] 구간의 K보다 큰 수 = [L, R] 구간의 K보다 큰 수 가 성립하기 때문이죠. 구현은 다음과 같습니다. i번 노드에 i&-i개의 자료가 정렬이 되어있으면 됩니다. 다만 세그먼트 트리로서 이용할 때와는 달리 자료를 직접 정렬해.. 2022. 3. 25. [PS를 위한 자료구조 9강] 머지 소트 트리의 개념과 구현 PS를 위한 자료구조 1-9강 # 머지 소트 트리 # 에 대해 알아보겠습니다. 다음의 문제를 봅시다. [수열과 쿼리1] https://www.acmicpc.net/problem/13537 이 문제를 해결하기 위해 다음과 같은 자료구조를 생각하면 어떨까요? 우리가 흔히 합병 정렬(merge sort)를 하는 과정은 다음과 같습니다. 1 2 3 4 5 6 7 8 | | 1 4 6 8|2 3 5 7 | | | | 1 8|4 6|2 7|3 5 | | | | | | | | 1 8 6 4 7 2 3 5 // 아래에서 위 순서로 진행 그런데 이 모습.. 어쩐지 눈에 익지 않나요? 그렇죠. 우리가 지금까지 공부한게 뭡니까. 세그먼트 트리입니다. 루트에서부터 분할해 나가고, 리프 노드부터 두 노.. 2022. 3. 24. [PS를 위한 자료구조 8강] 펜윅 트리의 개념과 구현 (Orderstatic Tree) PS를 위한 자료구조 1-8강 # 펜윅 트리의 개념과 구현 # 에 대해 알아보겠습니다. 지금까지 세그먼트 트리에 대해 배웠고 잘 따라온 여러분들에게 감사할 따름입니다. 이번 시간에 배워볼 자료구조는 "펜윅 트리"입니다. 펜윅 트리는 세그먼트 트리의 일종으로, 비재귀 세그먼트 트리에 분류할 수 있습니다. 역시 비재귀 세그먼트 트리답게 이해하는게 쉽지는 않지만, 구현 난이도는 비재귀 세그먼트 트리보다도 쉽습니다. 아래의 세그먼트 트리의 구조를 다시 봅시다. 그런데 이 중에 필요없는 구간이 있지 않을까요? 생각해보면 [1 8] 노드와 [1 4] 노드가 있으면 [5 8] 노드는 필요없는게 아닐까요? [1 8] 노드의 값에서 [1 4] 노드의 값을 빼준다면 [5 8] 노드의 값을 구할 수 있을 것입.. 2022. 3. 24. [PS를 위한 자료구조 7강] 세그먼트 트리의 응용 (금광 세그) PS를 위한 자료구조 1-7강 # 다양한 세그먼트 트리 테크닉, 금광 세그 # 에 대해 알아보겠습니다. 아래의 문제를 한 번 보겠습니다. [연속합과 쿼리] https://www.acmicpc.net/problem/16993 구간 합 구하기 4를 풀어보신 분들이라면 다음과 같은 생각을 할 수 있을 것 같습니다. 배열을 누적합으로 만든 다음, 구간 내 최댓값에서 최솟값을 빼면 되지 않을까요? 아쉽게도 해결하기 어려운 반례가 존재합니다. 최댓값이 최솟값보다 앞서서 나오는 경우에는 해결이 불가능하기 때문이죠. 위의 문제를 해결하기 위해 만들어진 테크닉이 바로 "금광 세그"라고 불리는 테크닉입니다. 금광이 나오는게 좀 뜬금없는데, 금광은 2014년 중등부 정보올림피아드에서 출제된 문제의 .. 2022. 3. 24. 이전 1 2 3 4 ··· 11 다음
