프로 공부를 하면서 처음으로 시작한 자료구조는 Indexed Tree(Segment Tree)이다.
부분 결과(합,곱,최대,최소 등)에 대한 것을 Tree 자료 구조 안에 저장하여 빠른 query( O(log n)) 및 update( O(log n)) 를 가능케 하는 자료구조이다.
삼성 Pro의 경우 최적화가 많이 나오기에 빠른 자료구조를 찾는 것이 우선일테니, 그럼 이 자료구조가 첫 자료구조로 최적일지도 모른다고 생각했다.
입력 값들은 모두 leafNode에 존재하며, 만약 값이 없더라도 초기화 값(0이든 뭐든) 으로 라도 2^n 개의 형태를 유지하게 된다.
depth는 그러므로 (올림연산)(log(초기값의 길이)/log(2)) 로, 이 depth 값이 앞서 말한 leaf 개수 연산의 n이 된다.
tree의 총 size는 leafSize*2-1 이 될 것이고.
이 경우 TopDown이든 BottomUp이든 상관은 없지만 재귀 함수가 필요한 자료구조라는 것을 알게 될 것이다.
잡설은 그만두고, 구현을 해보자.(부분 합으로 하겠다. 다 응용 가능하게 짜놨다.)
public IndexedTree(long[] numbers){
values = numbers;
depth = (int)Math.ceil(Math.log(numbers.length)/Math.log(2));
leafSize = (int)Math.pow(2,depth);
tree = new long[leafSize*2];
makeTree(1,0,leafSize);
}
public long makeTree(int index, int start, int end){
if(start == end){
tree[index] = (start < values.length)? values[start] : 0;
}
int mid = (start+end)/2;
tree[index] = makeTree(index*2, start, mid);
tree[index] += makeTree(index*2+1, mid+1, end);
return tree[index];
}tree,values,depth,leafSize는 Class의 전역 변수로 남겼다.
뭐 암튼. tree의 구조 상, leftChild는 now*2 index, rightChild는 now*2+1 임을 까먹지 않으면 된다.
if(start==end) 이 부분은 leaf에 다다랐을 때, 값을 집어넣기 위한 뭐.. 그런거다.
이 부분은 BottomUp이 효율적일 것이라고 생각해 구현하였다.
query
(여기선 부분합)
public long query(int index, int start, int end, int q_s, int q_e){
if(q_e < start || end < q_s){
return 0;
}
if(q_s <= start || end <= q_e){
return tree[index];
}
int mid = (start+end)/2;
return query(index*2, start, mid, q_s, q_e) + query(index*2+1, mid+1, end, q_s,q_e);
}이는 BottomUp이다. 쿼리 밖으로 나가면 0을 return.
leafNode/포함Node 로 가게 된다면 자신의 값을 return
나머지는 leftChild, rightChild의 합을 가져오게 했다.
쓸 때는(1,1,leafSize, 쿼리 시작(몇번째 수? 1부터 시작), 쿼리 끝) 으로 쓰면 된다.
update(TopDown , BottomUp)
두개의 구현법이 조금 많이 다르다. 분명 써야할 곳과 쓰지 않는 것이 좋은 곳이 둘 다 있다.(인덱스 기준으로 우선순위가 정해져 있다거나...). 일반적인 기준에서 설명하자면 BottomUp이 좀 더 효율적인 것 같다.(이해하기 쉬운 것도 BottomUp이다.)
public void updateTopDown(int index, int start, int end, int valueIndex, long diff){
if(valueIndex < start || end < valueIndex){
return;
}
tree[index] += diff;
if(start != end){
int mid = (start+end)/2;
updateTopDown(index*2, start, mid, valueIndex, diff);
updateTopDown(index*2+1, mid+1, end, valueIndex, diff);
}
}
public void updateBottomUp(int valueIndex, long newValue){
int startIndex = (int)Math.pow(2,depth)+valueIndex-1;
int nowIndex = startIndex;
while(nowIndex > 0){
if(nowIndex == startIndex){
tree[nowIndex] = newValue;
}else{
tree[nowIndex] = tree[nowIndex*2]+tree[nowIndex*2+1];
}
nowIndex = (nowIndex%2 == 1) ? (nowIndex-1)/2 : nowIndex/2;
}
}둘 다 그냥 tree의 기본 특성을 이해하고 있으면 쉽게 이해할 수 있는 코드이다. TopDown 코드의 경우, 새로운 값이 아닌 원래 값과의 차이를 넣는 파라미터가 있기에 부분 곱 혹은 최솟값 구하기에 취약하다. 부분합 할 때는 그냥저냥 쓸만한 편. BottomUp 시간 복잡도 괜찮다. BottomUp 쓰자.
printTree
내가 디버깅 하기 힘들어서 만들었다. 상태 체크할 때 좋으니까 그냥 갖다 쓰면 구조를 볼 수 있다.
public void printTree() {
int nowDepth = 0;
List<Integer> goTo = new ArrayList<>();
goTo.add(1);
while (!goTo.isEmpty() && nowDepth <= depth) {
nowDepth++;
for (int i : goTo) {
try {
System.out.printf("%d ", tree[i]);
} catch (Exception e) {
break;
}
}
List<Integer> newGoTo = new ArrayList<>();
int goToLen = goTo.size();
for (int i = 0; i < goToLen; i++) {
int tmp = goTo.get(0);
goTo.remove(0);
newGoTo.add(tmp * 2);
newGoTo.add(tmp * 2 + 1);
}
goTo = newGoTo;
System.out.println("");
}
}
전체 코드(부분합 트리 객체 구현만, main 작성 안 함.)
import java.util.ArrayList;
import java.util.List;
public class IndexedTreeFinal {
static class IndexedTree{
long[] tree;
long[] values;
int depth;
int leafSize;
public IndexedTree(long[] numbers){
values = numbers;
depth = (int)Math.ceil(Math.log(numbers.length)/Math.log(2));
leafSize = (int)Math.pow(2,depth);
tree = new long[leafSize*2];
makeTree(1,0,leafSize);
}
public long makeTree(int index, int start, int end){
if(start == end){
tree[index] = (start < values.length)? values[start] : 0;
}
int mid = (start+end)/2;
tree[index] = makeTree(index*2, start, mid);
tree[index] += makeTree(index*2+1, mid+1, end);
return tree[index];
}
public long query(int index, int start, int end, int q_s, int q_e){
if(q_e < start || end < q_s){
return 0;
}
if(q_s <= start || end <= q_e){
return tree[index];
}
int mid = (start+end)/2;
return query(index*2, start, mid, q_s, q_e) + query(index*2+1, mid+1, end, q_s,q_e);
}
public void updateTopDown(int index, int start, int end, int valueIndex, long diff){
if(valueIndex < start || end < valueIndex){
return;
}
tree[index] += diff;
if(start != end){
int mid = (start+end)/2;
updateTopDown(index*2, start, mid, valueIndex, diff);
updateTopDown(index*2+1, mid+1, end, valueIndex, diff);
}
}
public void updateBottomUp(int valueIndex, long newValue){
int startIndex = (int)Math.pow(2,depth)+valueIndex-1;
int nowIndex = startIndex;
while(nowIndex > 0){
if(nowIndex == startIndex){
tree[nowIndex] = newValue;
}else{
tree[nowIndex] = tree[nowIndex*2]+tree[nowIndex*2+1];
}
nowIndex = (nowIndex%2 == 1) ? (nowIndex-1)/2 : nowIndex/2;
}
}
public void printTree() {
int nowDepth = 0;
List<Integer> goTo = new ArrayList<>();
goTo.add(1);
while (!goTo.isEmpty() && nowDepth <= depth) {
nowDepth++;
for (int i : goTo) {
try {
System.out.printf("%d ", tree[i]);
} catch (Exception e) {
break;
}
}
List<Integer> newGoTo = new ArrayList<>();
int goToLen = goTo.size();
for (int i = 0; i < goToLen; i++) {
int tmp = goTo.get(0);
goTo.remove(0);
newGoTo.add(tmp * 2);
newGoTo.add(tmp * 2 + 1);
}
goTo = newGoTo;
System.out.println("");
}
}
}
}
'vidigummy was Advenced' 카테고리의 다른 글
| Pro 취득에 대한 후기 (3) | 2023.09.09 |
|---|