Fenwick 알고리듬(3)

 

Binary 0 과 1 - [출처] bbva.com

 

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번을 정확하게 찾아가는가"하는 논리이다.

먼저 3 번 인덱스에서 변경이 시작된다고 가정하면 그 다음은 아래 표와 같이 4가 되고, 4 이후에는 8이 된다.

최초 입력 값	3	4
idx	001 1	0100
① -idx	1 1 01      ( = 1100 + 1)	1 100   (=1011 + 1)
② idx & -idx	0001	0100
③ idx + (idx & -idx)	0100  (= 0011 + 0001)	1000 (= 0100 + 0100)
최종 출력 값	4	8

이는 아래의 추적표와 동일하다. 여기서 우리가 주목해야하는 것이 idx & -idx 의 결과가 의미하는 것이 무엇인가 하는 질문이다. 혹시라도 더 연습이 필요한 경우를 위하여 인덱스가 5번이 변경(원래 배열 4번)될 때는 어떻게  5번 -> 6번 -> 8번으로 찾아가는지 아래의 추적표를 확인할 수 있다.

 

index += index & -index 추적표 (index 3과 5번)

 

idx & -idx  - Syntax와 Semantics 관점

Syntax	Semantics
문장 구조와 문법 규칙에 대한 연구 (구문) (the study of sentence structure and the rules of grammar)	문장의 의미에 대한 연구 (의미) (the study of the meaning of sentences)

지금까지 우리는 ① 2의 보수를 구하고  ② 그 보수와 자신의 이진수를 AND 연산자(&)로 더하는 절차를 몇 가지 다른 예를 통해 살펴보았다. 이러한 절차는 프로그램 언어의 규칙에 따라 정확하게 논리를 따라가면 되는 신텍스(Syntax) 였다면, 이제 그 절차가 의미하는 바를 정확하게 이해할 필요가 있다.

지금까지 살펴 본 idx & -idx 의 결과를 자세히 관찰하면, 항상 최초 자신의 이진수에서 가장 오른쪽에 있는 1의 값만을 찾아오고 있다는 것을 알 수 있다. 만약 0110 으로 시작한다면 이 함수를 거쳤을 때 결과는 0010이 나올 것이고, 1100 은 0100 이 나올 것이다. 만약 1010 이라면 0010이 나올 것이다. (어려운 문제라고 생각하지 않지만 만약 1110 이면 어떤 값이 나올 것인가? 만약 1111 이면 어떤 값이 나올 것인가?)

이제 이 결과는 무슨 이야기를 하는 것인가?

(정확하게 트리를 보고 이야기를 한다면) ②번 (idx & -idx) 함수를 지나고 마지막 ③번 idx = idx + (idx & -idx) 계산 절차를 거쳤을 때 일어나는 일은 자신을 포함하고 있는 바로 위의 "부모 노드의 index 값"을 출력한다는 것이다. 2(0010)와 3(0011)은 각각 다른 값을 가지고 있지만, 이 절차를 통해서 같은 부모 노드에 해당하는 4(0100) 을 같이 바라볼 수 있는 것이다. (마찬가지로 4(0100), 6(0110) 그리고 7(01111)가 바라보는 부모 노드는 누구인가?)

Fenwick 알고리듬 구현 : update(index, value) / sum(index) 함수

이제 아래와 같이 소스 코드를 보고 이야기를 계속하자. 알고리듬을 구현(implementation)하는 실제의 프로그램은 모든 개발자마다 다르기 때문에 정확하게 논리를 먼저 이해하고 난 후에 소스코드를 짜는 것을 추천한다. 아래 로직 중에서 update 함수를 구현하는 핵심은 21번 라인이고 sum 함수를 구하는 핵심은 28번 라인이다. 

여기서 두 경우의 논리가 다른 것을 볼 것이다. 즉 update 함수에서는 idx += idx & -idx 이고 sum 함수에서 idx -= idx & -idx 와 같이 처음 것은 + 이고 두번째는 - 이다.  우리가 지금까지 살펴본 update 함수를 중심으로 설명을 하면, 변경이 필요한 배열의 원소부터 시작을 하여 그 변경이 반영되어야 하는 최종 부모 노드까지 트리 구조 내에서 찾아 올라가면서 update 를 해야하기 때문에 (+) 가 필요한 것이다.

마찬가지로 sum 함수의 경우 왜 (-) 가 필요한가에 대해서도 같은 논리가 적용될 수 있다. 즉 요구하는 index 까지의 합을 가져와야 하는 경우는 자신부터 시작하여 1번 배열까지 밑으로 내려가면서(-) 필요한 배열 원소들을 찾아서 더해야 한다. 그 논리가 위의 소스 코드에서 26-28 라인까지의 의미(semantics)가 된다. iㅈ += idx & -idx

 

성능 비교

처음 이 알고리듬을 논의할 때 이야기하였던 성능 향상을 살펴보자. 결과적으로 일부 원소 값을 변경해야 하는 경우가 문제였는데, 이 경우 항상 전체 배열을 다시 검색하고 변경하는 O(N)에서 O(log N)으로 성능 향상이 이루어진 것을 알 수 있다. 

	단순하게 누적 값을 배열에 보관하는 경우	Fenwick 트리를 사용하는 경우
합을 가져와야 하는 경우 (sum)	O(1)	O(log N)
일부 원소 값을 변경하는 경우 (update)	O(N)	O(log N)

알고리듬의 응용

사실 이 알고리듬으로 해결할 수 있는 많은 문제들은, 구간 트리라고도 하는 Segment Tree 알고리듬으로도 해결할 수가 있다. 단지 구간 트리에서 가능한 min/max (최소/최대) 값을 찾는 것을 이 Fenwick 알고리듬으로 구현할 수는 없다. 하지만 지속적으로 자주 변경되는 배열의 구간 합을 구해야 하는 경우는 이 알고리듬이 구간 트리보다도 매우 효율적이다. 

이 알고리듬을 한 친구와 자세히 논의하면서 그 친구로부터 응용 범위에 대한 지속적인 질문을 받았다. 우리가 동의한 응용할 수 있는 좋은 사례 중 하나는 다음과 같은 경우이다. 만약 회사의 부서 내에서 직원들 마다 개별 영업실적이 매일 변경되어야 하는 경우가 있다고 가정해보자. 언제 누구의 실적이라도 무작위로 변경될 수 있고, 전체 합이나 부서별, 또는 사원 번호별로 부분 합을 항상 구해야 하는 상황이라면 이 Fenwick 알고리듬은 어느 정도 좋은 해결 방법이 될 수 있을 것이다.

 

후기

이번 Fenwick 알고리듬 이야기는 다른 역사나 인문 이야기보다 다소 힘들었다. 세미나를 하던 사람들과 같이 지식을 공유하고 토론할 때는 다소 재미도 있고 설명이 쉽게 넘어갔던 것 같은데, 무엇보다 글로 알고리듬을 표현하려고 하는 의도는 언어의 한계에 항상 갖혀버리는 느낌이었다. 결국 프로그램이나 알고리듬과 같은 지식은 직접 손으로 짜보아야만 쉽게 이해할 수 있는 부분들이 너무 많다는 것을 다시 한번 절감했다.

처음에는 sum 함수에 대한 논리적인 흐름도 update 와 같이 자세한 절차를 도표나 다이어그램을 통해서 설명을 하려고 하였으나 (1) 너무 긴 설명은 항상 읽는 사람을 지치게 한다는 개인적인 경험과 (2) 이 부분은 읽는 사람들의 개인적인 연습으로 남겨 두어도 좋을 것이라는 생각에 sum 함수에 대한 구체적인 설명은 처음에 언급한 기본적인 논리와 바로 앞에 소스 코드를 공유하는 것으로 대신하였다. (부끄럽지만  Fenwick 알고리듬을 설명하는 이 글이 사실 너무 길어졌고 읽는 사람들을 지치게 할 것이라는 우려가 생겼다.)

혹시라도 읽는 어떤 사람이라도 지금까지의 설명에 대한 의문점이 있어 문의를 한다면, 어떠한 조언, 오탈자에 대한 질책도 감사하게 받아들이고 지속적으로 보완을 할 예정이다. 읽어주신 모든 분들께 다시 한번 감사드린다.

[1] Syntax vs. Semantics 차이

www.writersdigest.com/write-better-fiction/semantics-vs-syntax-vs-pragmatics-grammar-rules

[2] 백준 온라인 문제

www.acmicpc.net/workbook/view/4010

[]