Index 추적 예제 (2) 앞에서 설명한 이진수 계산 절차 방법이 충분히 익숙하지 않을 것이라 생각하여 조금 더 연습을 해보자. 위의 예는 각각 다른 index를 변경한 경우이다. 좌측의 트리에서는 3번 (원래 배열 원소 2번)이 6에서 10으로 바뀐 경우이고, 우측의 트리는 1번 (원래 배열 원소 0번)이 3에서 4로 변경된 경우이다. 첫번째의 예는 3번에서 시작하여 4번을 정확하게 변경하고 8번에서 끝나야 하는 경우(3번 -> 4번 -> 8번)이다. 우측의 두번째 예는 1번 -> 2번 -> 4번 -> 8번으로 변경이 완료되면 된다. 우리가 정확하게 이해를 해야하는 부분은 "(같은 부모 노드에 해당하는 4번 인덱스 아래 각각 분리되어 존재하는) 2번과 3번 인덱스가 어떻게 (동일한) 부모 노드 4번을..

Binary Indexed Tree 구조 앞에서 살펴본 테이블로 표시된 Fenwick 을 왜 Binary Indexed Tree 구조라고 부르는지 살펴볼 시간이다. 여기서도 0번 index에 해당하는 원소는 큰 의미가 없다. 살펴볼 것은 각각의 푸른 색 원소들은 모두 마지막 노드에 속해있고, (바로 앞의 원소의 값과 자신의 값의 부분합을 가지고 있는) 녹색의 원소는 그 푸른색의 원소만을 자녀 노드로 구성하고 있다. 아래의 구조 내에서 처음 언급한 2개의 Operation이 어떻게 움직이는 지 다시 한번 살펴보자. 1) 부분 합을 가져와야 하는 경우 : Sum 만약 최초 배열의 0번부터 5번까지의 합을 가져와야 하는 경우라면, Fenwick 배열에서는 1번부터 6번까지의 배열 내의 값들의 합을 가져오면 된..

Fenwick 알고리듬 (BIT Algorithm) - 시작 이 알고리듬은 다른 이름으로는 BIT(Binary Indexed Tree) 알고리듬이라고 하는데, 1994년 뉴질랜드의 Auckland 대학 교수였던 펜윅(Peter Fenwick) 교수에 의하여 발표되었다. 개인적으로 이 알고리듬을 처음 이해하는데 다른 알고리듬보다는 시간이 더 걸렸던 기억이 난다. 전체 그림을 이해하고 나면 별 문제가 없지만, 처음에는 구체적인 몇 가지 논리 흐름들은 스스로 따라가야만 쉽게 이해되는 부분이 있다. 나 역시 다른 유투버들의 설명을 10개 가량을 시청하고 그 중 한두 개는 집중적으로 보았다. 하지만 매우 좋은 내용을 가진 유투브도 일부 있었지만 어떤 것은 한 시간을 넘게 투자하고도 시간만 낭비한 느낌을 받은 것도..