남남서의 블로그

이것이 Binary Indexed Tree이다. Binary - 이진의 Indexed - 인덱스가 매겨진 Tree - 트리 (용어의 정의에는 사람마다 차이가 있다.) 위의 BIT 그림에서, 가장 밑의 줄에 7개의 원소를 쓰려고 한다면? 8부터 14까지의 원소를 각각 첫번째부터 7번째까지로 사용하면 된다. 그리고, 7보다 크면서 가장 작은 2의 제곱수는 8이다. 즉 n개의 원소를 가장 밑줄에 쓰려고 한다면, n 이상이면서 가장 작은 2의 제곱수를 m이라고 하고, m부터 m+n-1까지의 원소를 사용하면 된다. 그렇다면 배열로 선언할때는 m+n-1까지의 배열을 선언하면 된다. 일반적으로는 2m-1까지의 배열을 잡는다. 각 노드의 부모와 자식의 관계를 살펴보면 부모 2 5n 왼쪽 자식 4 102n 오른쪽 자식 ..

Fenwick tree, 펜윅 트리라고 불리는 자료구조가 있다. binary indexed tree (BIT) 라고도 불린다.옛날에는 이 BIT라는 이름이, 펜윅 트리 말고 top-down 혹은 bottom-up 형식의 세그먼트 트리를 가리키기도 한 것 같은데, 요즘은 다들 이 펜윅 트리만 지칭하는 것 같다. 각각의 숫자는 인덱스(첨자)를 의미하고, 그 숫자와 연결된 흑색 사각형과 그 밑의 흰색 직사각형이 전부 해당 인덱스가 들고 있는 영역이다. 각각의 숫자가 나타내는 구간이 어떻게 결정되는지 알아보자. 12의 경우 이진수로 나타내면 1100 이다. 여기서 밑(제일 오른쪽)부터 쭉 올라가면서 가장 먼저(즉, 가장 오른쪽에서) 나타나는 1의 위치는 100 이다. 이를 LNZB(lowest nonzero b..

트리(tree)는 그래프의 일종이다.그래프란 정점(vertex)들이 간선(edge)들로 연결되어있는 구조를 뜻한다. 정점은 node, 노드라고도 부른다.지하철 노선도에서 각 역이 정점, 이웃한 역을 잇는 노선이 간선이 될 수 있다. 도로와 도로가 만나는 교차로들을 정점, 교차로 사이의 도로를 간선이라고도 말할 수 있다. 그럼 트리는 뭘까? 어떤 조건을 만족하는 그래프를 트리라고 부른다. 이 조건을 더 쉽게 이해하려면... 일단 그림을 보자.나무에서 가지가 뻗어나가는 모양을 상상하자. 이 그래프는 정점이 6개, 간선이 5개이다. 그리고 이 그래프는 트리이다. 트리의 조건은 다음 중 한 가지만 만족하면 트리이다. 왜냐하면 모두 서로 동치인 조건이기 때문이다.1. 간선의 갯수가 정점의 갯수보다 하나 적으며(E..

190616. 제 블로그 조회수의 상당수를 차지하는 글입니다. 특히 대학교 시험 기간인 6월에 많이들 찾아주시더라구요. 그런 것 치고는 글이 너무 오래 되어서, 글을 완전히 다시 쓰고 연습문제를 몇 개 추가했습니다. 위상정렬은 방향 그래프(directed graph) 문제에서 쓰입니다. 또는 직접 그래프가 주어지지 않는 경우에도, 문제에 나타난 요소들을 점으로 나타내고 그 사이에 화살표를 그렸을 때 방향 그래프가 나타나는데, 문제를 푸는 과정에서 위상 정렬이 꼭 필요한 경우도 있습니다. 먼저 위상 정렬을 대강의 느낌으로 설명해 보려고 합니다. a → b를 "a가 충족되어야만 b를 할 수 있다"는 뜻으로 생각해봅니다. 예를들어 a가 세탁기를 돌리기, b가 건조기 사용하기라면, 세탁기를 돌리는 일을 마쳐야 ..

$N$개의 숫자가 늘어서 있다. L번째 숫자부터 R번째 숫자까지의 합을 구하라는 질문이 여러 개 들어올 때, 각각을 모두 빠르게 구할 수 있을까? 2018/07/27 - [알고리즘 문제풀기/# 자료구조] - 구간의 합 구하기prefix sum 기법을 사용하면 이 "구간의 합 구하기" 문제를 빠르게 풀 수 있다. 또한, 어떤 문제에서는 prefix sum을 구해보면 생각하지 못했던 성질이 나타나서, 그게 문제를 푸는 열쇠가 되기도 한다. 아예 prefix sum 값에 관한 문제가 나오기도 한다. prefix sum은 간단하지만 중요한 개념이다. 그래서 도대체 그 prefix sum이란게 무엇인가 하면, 다음과 같다. $a_1$부터 $a_n$까지의 $n$개의 숫자가 늘어서 있을 때, prefix sum 배열..