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개 가량을 시청하고 그 중 한두 개는 집중적으로 보았다. 하지만 매우 좋은 내용을 가진 유투브도 일부 있었지만 어떤 것은 한 시간을 넘게 투자하고도 시간만 낭비한 느낌을 받은 것도..

고등학교 때 이과를 택한 사람들은 수학 시간에 한번은 log에 대해서 배운다. 여기서는 로그를 계산하는 수학 원리나 계산 방법에 대해서 논의할 생각은 없다. 단지 컴퓨터에서 알고리듬의 성능(Performance)을 측정하는 방법으로서 로그에 대한 이야기를 하려고 한다. 존 네이피어 (John Napier, 1550-1617) 로그 계산법을 최초로 창안한 사람은 스코틀랜드의 존 네이피어이다. 그는 수학자이자 천문학자로서 (지금과 같은 계산기나 컴퓨터가 없던 시기에) 잦은 천문학 계산 작업을 편하게 하기 위하여 로그를 만들었다. 이 원리는 당연히 지수들을 수학적으로 처리하는 논리이지만, 로그라는 log 수식 기호 자체는 발견이라기 보다는 발명에 더 가깝다고 - 개인적으로 - 이해한다. 로그의 활용은 매우 광..

현재 내가 하는 일은 북미의 IT 컨설팅 회사에서 시스템 개발 및 지원을 해주는 업무이다. 최초 업무 경력 지금 20년 째 이 업종에 종사를 하기 전에는 92년부터 97년 사이에 대한민국의 중부전선과 서부전선의 최전방에서 직업 군인으로 5년간 생활을 했다. 강원도 철원에서 포병 장교로 시작하여 경기도 포천 임진강 지역의 XX 사단의 포병 대대에서 전역을 하기 까지 포병 사격 지휘 장교와 포대장 업무를 수행하였는데 실제로 그 업무들은 수학과 공학 지식이 상당히 많이 필요한 일들이었다. 나는 컴퓨터 일을 하던 탓에 원치 않게 일하면서 학교에 적을 오래 두고 살게 되었는데, 학교보다는 항상 실무에서 더 많이 배운다는 것을 경험을 통해 알고 있다. 고등학교때 그렇게 수학을 좋아하고, 학부에서 물리를 전공하였지만..