yoongrammer
목차 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 펜윅 트리(Fenwick Tree)는 세그먼트 트리의 변형으로 수열의 구간 합을 빠르게 구할 수 있도록 고안된 자료 구조입니다. 펜윅 트리는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. 펜윅 트리는 세그먼트 트리처럼 O(logN) 시간으로 구간 합을 구할 수 있으며 세그먼트 트리에 비해 적은 공간이 필요하고 구현하기 쉽다는 장점이 있습니다. 펜윅 트리 구성 배열 A를 가지고 세그먼트 트리를 만들면 다음과 같습니다. 각 노드에는 구간합 정보가 들어 있습니다. 위 세그먼트 트리에서 각 층에에서 짝수 인덱스를 무시하면 아래와 트리를 얻을 수 있습니다. 이러한 구조를 펜윅 트리라고 합니다. 주어..
목차 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. 다음 예를 보겠습니다. A = {1, 2, 3, 4, 5 … ,N} 라는 배열에 아래 연산을 M번 수행한다고 생각해봅시다. 배열의 범위 합을 구하는 Query 연산 A[0] + A[1] + A[2] + … + A[N-1] i번째 배열 값을 v로 변경하는 Update 연산 A[i] = v 단순한 방법으로는 각각 배열에 접근하여 연산을 한다면 시간 복잡도는 1번 연산 O(N), 2번 연산 O(1)이 됩니다. 이 두 연산을 M번 수행한다면 총 시간 복잡도는 O(MN)+O(M) = O(MN)이 됩니다. 세그먼트 트리를 사용하면 범위 최소/최대 및 합계 Query 및..
목차 서로소 집합(Disjoint Set) & 유니온 파인드(Union find) 서로소 집합(Disjoint Set) Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. Disjoint set 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는 데에 유용하게 사용할 수 있습니다. Disjoint set 자료구조는 MakeSet, Union, Find라는 연산을 제공합니다. MakeSet MakeSet 연산은 주어진 요소만 포함하는 집합을 생성합니다. 이 연산에서 parent 배열을 생성합니다. parent 배열은 노드의 부모 노드를 저장하고 있습니다. 부모 노드가 없다면 자기 자신을 가리..
목차 캐시(Cache) 란? 캐시(Cache)는 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 저장소입니다. 속도 향상을 위해 캐시를 사용하며, 다음과 같은 상황에서 캐시를 주로 사용합니다. 원본 데이터보다 빠르게 접근 가능할 때 같은 데이터에 반복적으로 접근할 때 변하지 않은 데이터를 주로 사용할 때 레디스(Redis)는 단순한 구조와 in-memory저장소로 인한 빠른 성능 때문에 캐시에 주로 쓰입니다. 캐싱 전략(Caching Strategies) 캐시로 사용할 때 어떻게 배치하는지가 시스템 성능에 큰 영향을 끼치는데 이를 캐싱 전략(Caching Strtegies)이라고 합니다. Look-Aside Look-Aside는 데이터를 찾을 때 우선 캐시에서 데이터를 찾고 데이터가 있다면 캐시에서..
목차 의존성 역전 원칙 (DIP: Dependency Inversion Principle) 1. 상위 모듈은 하위 모듈에 의존해서는 안 되고 둘 다 추상화에 의존해야 한다. 2. 추상화는 세부 사항에 의존해서는 안 되고 세부사항(구체적인 구현)은 추상화에 의존해야 한다. 로버트 C. 마틴 의존성 역전 원칙(DIP)은 변화하기 쉬운 것에 의존하지 말라는 원칙입니다. DIP를 지킴으로써 하위 모듈(or 클래스)에 대한 상위 모듈(or 클래스)의 종속성을 줄일 수 있습니다. 상위 모듈(or 클래스): 도구로 작업을 실행하는 클래스 하위 모듈(or 클래스): 작업을 실행하는데 필요한 도구 DIP 적용 전 다음 예를 보겠습니다. Calculator 클래스가 Add클래스를 사용하여 덧셈을 하는 예입니다. 여기서 C..