Fenwick 알고리듬(1)

Fenwick 알고리듬 (BIT Algorithm) - 시작

이 알고리듬은 다른 이름으로는 BIT(Binary Indexed Tree) 알고리듬이라고 하는데, 1994년 뉴질랜드의 Auckland 대학 교수였던 펜윅(Peter Fenwick) 교수에 의하여 발표되었다. 개인적으로 이 알고리듬을 처음 이해하는데 다른 알고리듬보다는 시간이 더 걸렸던 기억이 난다. 전체 그림을 이해하고 나면 별 문제가 없지만, 처음에는 구체적인 몇 가지 논리 흐름들은 스스로 따라가야만 쉽게 이해되는 부분이 있다.

나 역시 다른 유투버들의 설명을 10개 가량을 시청하고 그 중 한두 개는 집중적으로 보았다. 하지만 매우 좋은 내용을 가진 유투브도 일부 있었지만 어떤 것은 한 시간을 넘게 투자하고도 시간만 낭비한 느낌을 받은 것도 한 두개가 아니었다. (앞으로도 지식 습득을 위한 이러한 시간 낭비 문제는 유투브의 큰 문제라고 생각한다)

펜윅(Fenwick) 교수

기본 상황

만약 크기가 8개의 원소를 가진 배열(array)이 주어지고, 순서(index) 별로 무작위의 값(value)들이 아래와 같이 있다고 가정하자.

주어진 배열

1) 합을 가져와야 하는 경우 (sum)

만약 이 배열에서 전체 합을 가져와야 한다면 3 + 5 + 6 + 0 + 2 + 4 + 7 + 8 = 35가 된다. (부분 합을 가져오는 경우는 전체 합을 가져올 수 있으면 손쉽게 해결된다)

2) 일부 원소 값을 변경하는 경우 (update)

예를 들어, 0번 index의 값을 4로 바꾸어야 할 경우와 같이 일부 배열의 값이 바뀌는 경우가 있다.

0번 원소 값을 4로 변경

원시적인 해결 방법

이제 합을 가져와야 하는 경우와 일부 원소 값이 바뀌는 경우를 해결하기 위한 자료구조를 살펴보자. 이 경우 제안된 해결 방식 중 하나는, 처음 주어진 배열과 같은 크기의 다른 배열을 만들어서 그 안에 누적된 값을 미리 넣어 두는 것이다. 즉 0번에는 3 자신을, 1번에는 앞의 3과 자신의 값 5를 더한 8을 넣는다. 나머지 2번,3번, 4번.. 7번까지 모든 값들은 앞에서 부터 시작한 누적된 값을 넣는 것이다.

이 경우 좋은 점은 일단 원하는 번호의 원소의 index만 알려주면, 처음부터 다시 더할 필요 없이 해당 누적값만 가져오면 된다.

단지 문제는 (변경후 도표에서 보이는 것과 같이) 하나라도 변경이 되면 그 이후의 모든 누적값도 같이 바뀌어야 한다는 것이다.

이와 같은 장단점을 고려할 때 이 해결 방식이 제공할 수 있는 성능은 다음과 같다.

1) 합을 가져와야 하는 경우 (sum) : O(1)

2) 일부 원소 값을 변경하는 경우 (update) : O(N)

정리해서 다시 이야기하면, 일단 모든 값들이 더 이상 변경되지 않는 경우는 합(또는 부분합)을 가져오는 속도가 매우 빠르다. 하지만 단 하나라도 값이 바뀌는 경우는 해당 원소 이후의 모든 원소들을 뒤져서 변경을 해주어야 하기 때문에 최악의 경우 O(N) 이 나오게 된다.

Fenwick 알고리듬의 기본 아이디어

이 Fenwick 알고리듬에 숨겨진 배열의 구조는 크게 두 가지로 나뉜다. ① 원래 자신의 값만을 보관하는 배열들과 ②자기 자신을 포함한 부분합을 보관하는 배열들, 이 두 가지 형태로 구성된 Hybrid 형이라는 것이다. 무슨 의미인가? 아래의 테이블을 다시 보면서 천천히 생각해보자.

다소 위의 테이블이 복잡해 보일 수 있으나 천천히 살펴보면 그렇게 어려운 도표는 아니다. 처음 위에 있는 3개의 index / value / 누적값은 위에서 설명한 input 값에 따른 순서와 값, 그리고 부분합들을 가지고 있는 누적값 표이다.

바로 밑에 있는 도표가 Fenwick 구조인데 처음 0번째 index 에는 특별한 값이 필요없고 다음 1번 index 부터 시작을 한다. (이유는 나중에 설명하겠지만) Fenwick의 0번은 건너뛰고, input의 0번이 Fenwick의 1번으로, input의 1번은 Fenwick의 2번으로 같이 하나씩 offset 이 되어 만들어진다.

그리고 위에서 보이는 것과 같이 푸른 색의 배열 원소들에는 원래의 자기 값만 들어간다. 예를 들어 Fenwick[1] 에는 input[0]의 값 3이 들어가고, 마찬가지로 Fenwick[3]에는 input[2]의 값 6이 그냥 들어간다. (① 원래 자신의 값만을 보관하는 배열 원소들)

그 다음이 중요한데 처음 녹색에 해당하는 Fenwick[2] 에는 앞의 Fenwick[1]의 값 3과 자신의 값 5를 더한 8을 가지게 된다.그리고 다소 이상하지만 Fenwick[4]에서는 앞의 Fenwick[2]의 부분 누적값과 Fenwick[3]의 값에 자신의 값 0을 더한 14를 가지게 된다. 마지막으로 Fenwick[8]은 아래의 도표에서 보이는 것과 같이 값이 결정된다. (②자기 자신을 포함한 부분합을 보관하는 배열 원소들)

Fenwick[1]	= 3
Fenwick[2]	= Fenwick[1] + 5 = 8
Fenwick[3]	= 6
Fenwick[4]	= Fenwick[2] + Fenwick[3] +0 = 14
Fenwick[5]	= 2
Fenwick[6]	= Fenwick[5] + 4 = 6
Fenwick[7]	= 7
Fenwick[8]	= Fenwick[4] + Fenwick[6] + Fenwick[7] + 8 = 35

처음에는 다소 이러한 방식의 값들의 저장이 이상하게 보일 지 모르겠지만, 일단 값들이 모두 결정이 되면 아래와 같이 Fenwick(또는 Binary Indexed) Tree가 만들어진다.

그럼 보다 구체적으로 각 배열별로 어떻게 값들이 채워지고 부분합을 쉽게 가져올 수 있는지 살펴보자.

(계속)

[1] 위키

en.wikipedia.org/wiki/Fenwick_tree

(모든 글은 동의 없이 전체나 부분의 무단 복제를 금지합니다. COPYRIGHT ⓒ 2020 ALL RIGHTS RESERVED.)