yoongrammer

목차Lower bound & Upper bound 개념 및 구현Lower bound와 Upper bound는 경곗값을 찾는 알고리즘입니다.Lower bound와 Upper bound는 이진 탐색을 기반으로 하기 때문에 데이터가 정렬되어 있어야 합니다.이진 탐색을 기반으로 하기 때문에 두 알고리즘의 시간 복잡도는 O(log n) 입니다. (n: 배열 길이) Lower boundLower bound는 특정 값의 시작 위치를 찾는 알고리즘입니다.동작 방식Lower bound의 동작 방식은 다음과 같습니다.초기에 left는 배열의 시작 위치로 right는 배열의 길이로 셋팅합니다.배열의 중간 값(mid)을 가져옵니다.중간 값과 검색 값을 비교합니다.중간 값이 검색 값보다 작다면 left 값을 mid+1로 합니다..

목차펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)펜윅 트리(Fenwick Tree)는 세그먼트 트리의 변형으로 수열의 구간 합을 빠르게 구할 수 있도록 고안된 자료 구조입니다.펜윅 트리는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. 펜윅 트리는 세그먼트 트리처럼 O(logN) 시간으로 구간 합을 구할 수 있으며 세그먼트 트리에 비해 적은 공간이 필요하고 구현하기 쉽다는 장점이 있습니다.펜윅 트리 구성배열 A를 가지고 세그먼트 트리를 만들면 다음과 같습니다. 각 노드에는 구간합 정보가 들어 있습니다.위 세그먼트 트리에서 각 층에에서 짝수 인덱스를 무시하면 아래와 트리를 얻을 수 있습니다.이러한 구조를 펜윅 트리라고 합니다.주어진 n개의 배열..

목차세그먼트 트리(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 및 범위 Updat..

목차서로소 집합(Disjoint Set) & 유니온 파인드(Union find)서로소 집합(Disjoint Set)Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. Disjoint set 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는 데에 유용하게 사용할 수 있습니다. Disjoint set 자료구조는 MakeSet, Union, Find라는 연산을 제공합니다.MakeSetMakeSet 연산은 주어진 요소만 포함하는 집합을 생성합니다. 이 연산에서 parent 배열을 생성합니다.parent 배열은 노드의 부모 노드를 저장하고 있습니다. 부모 노드가 없다면 자기 자신을 가리킵니다.이 ..

목차캐시(Cache) 란?캐시(Cache)는 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 저장소입니다.속도 향상을 위해 캐시를 사용하며, 다음과 같은 상황에서 캐시를 주로 사용합니다.원본 데이터보다 빠르게 접근 가능할 때같은 데이터에 반복적으로 접근할 때변하지 않은 데이터를 주로 사용할 때레디스(Redis)는 단순한 구조와 in-memory저장소로 인한 빠른 성능 때문에 캐시에 주로 쓰입니다. 캐싱 전략(Caching Strategies)  캐시로 사용할 때 어떻게 배치하는지가 시스템 성능에 큰 영향을 끼치는데 이를 캐싱 전략(Caching Strtegies)이라고 합니다.Look-AsideLook-Aside는 데이터를 찾을 때 우선 캐시에서 데이터를 찾고 데이터가 있다면 캐시에서 데이터를 가지..