1. 문제 크기가 N인 정수의 배열 A가 주어지며 구간의 합을 구하는 문제를 M번 수행하는 문제에서 중간에 index번째 수를 value로 바꾸는 문제는 세그먼트 트리를 이용하여 해결했다. 이번엔 단순히 i번째 수를 value로 바꾸는 것이 아니라, i번째 수부터 j번째 수에 v를 더하는 경우를 생각해보자. 세그먼트 트리에서 index번째 수를 value로 바꾸는 연산은 O(logN)인데, i번째수부터 j번째 수를 모두 v로 바꾼다면 최대 O(NlogN)이다. 하지만 그냥 i번째 수부터 j번째 수를 순회해서 바꾸면 O(N)이다. 세그먼트 트리를 사용했더니 오히려 더 느리게 된다 2. 구간을 변경하는 update함수 [left,right]의 모든 수에 value를 더하는 작업을 수행해야한다면? [left,..
1. 세그먼트 트리의 표현 배열의 크기 N이 2의 거듭제곱꼴이면 Perfect binary tree이므로 트리의 높이 h는 각 높이의 노드의 수가 x개이면 $$h=log_{2} x$$ full binary tree라면 어떨까? 어떤식으로 구성되어 있느냐에 따라 조금 달라진다..... $h= \left \lceil log_{2} x \right \rceil $이기도 하고.. $H= \left \lceil log_{2} x \right \rceil +1 $ 이기도 하고... 따라서 세그먼트 트리를 표현할 때, 배열을 이용해서 표현할 수 있고 세그먼트 트리 배열의 크기는 항상 그 크기가 일정한 높이 h인 perfect binary tree의 노드 수로 나타낼 수 있다 비어있는 부분은 0으로 채우든지 하면 되니..
1. 배열을 이용한 이진 트리 표현 루트의 번호를 1로 하고 레벨 n에 대하여 왼쪽부터 오른쪽으로 $2^{n}$부터 시작하여 번호를 부여 노드 번호를 index로 해서 배열에 노드 정보를 저장 완전 이진트리일때만 가능할듯 아니라면 빈 부분은 0으로 채우고 데이터를 넣으면 될것 같은데 조금 복잡해질것 같고 높이 h가 주어진다면.. h의 노드 최대개수는 $2^{h+1}-1$개니까 [0]*$2^{h+1}-1$으로 초기화 노드 개수 n개가 주어진다면 뭐 [0]*(n+1)로 초기화하면 될듯 라고 생각했는데.. 이게 아니야 왜 그런지는 뒤에 쓴다 1-1) 노드 번호의 특징 완전이진트리처럼 번호를 붙이는 방식인 1번부터 n번까지를 왼쪽부터 오른쪽으로 차례대로 붙일때만 성립함 1)레벨 n의 시작 노드 번호는 $2^{n..
1. 이진트리 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 모든 노드들이 자식 노드를 "최대" 2개까지만 가질 수 있는 트리 각 자식 노드를 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node) 이진 트리 예시 4가지.. 모든 노드가 자식 노드를 "최대" 2개만 가지면 이진 트리가 된다 자식 노드가 아예 없어도 된다는 소리 2. 특징 레벨 i에서(높이 i에서) 노드의 최대 개수는 $2^{i}$개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개 최대 개수는 $2^{h+1}-1$개 3. 종류 이진트리의 종류에 따라 저장, 표현, 알고리즘 등이 달라질 수 있으므로 잘 구분해야한다 3-1) 포화 이진 트리(full binary tree..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
