공영재의 개발일지

B-tree란? B-tree는 Self-balanced Tree 중 가장 유명한 자료구조입니다. Balanced-tree를 의미하며, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다. 즉, 하나의 노드에 하나의 데이터를 저장하는 다른 Self-Balanced Tree와 달리, 하나의 노드에 여러개의 데이터를 저장하는 방식으로 Tree의 height를 줄여 탐색 시간을 더 획기적으로 줄이도록 고안된 트리입니다. (B-tree와 B+tree, B*tree가 있지만 일반적으로 B tree라 함은 B-tree를 의미합니다.) 이렇게 고안된 트리를 유지하기 위한 몇가지 규칙이 있습니다. 1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다. 첫..

Red-Black tree란? Red-Black tree(R-B tree)는 AVL tree, Splay tree와 같은 Self-balanced Binary Search Tree입니다. Red-Black tree는 말그대로 모든 노드가 빨간색과 검정색으로 표현됩니다. 이러한 R-B tree는 균형을 유지하기 위해 아래 다섯가지 조건을 만족해야 합니다. 1. 모든 노드는 빨간색 혹은 검은색이어야 합니다. 2. 루트 노드는 검은색이다. 3. 모든 NIL은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 리프 노드) 4. 빨간색 노드의 자식은 반드시 검은색이다. 5. NIL에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. Red-Black tree의 원..

Splay tree란? Splay tree는 이진검색트리(Binary Search Tree)의 한 종류로, 다른 BST(AVL tree, R-B tree 등)보다 구현이 쉽고, 연산을 amortized O(logn)의 시간복잡도로 수행할 수 있습니다. amortized O notation은 일반적으로 사용되는 big-O notation과 달리, 시간 복잡도를 실행 시간의 상한 점근이 아닌, 최악의 경우에 대한 해당 연산의 평균 시간복잡도를 나타냅니다. 따라서 최악의 경우에서 연산 시간복잡도가 O(logn)임을 보장한다는 의미라고 생각하시면 됩니다. Splay tree는 삽입, 삭제, 검색의 연산을 수행한 뒤, splay를 통해 최근에 접근한 노드를 루트에 위치시켜 트리를 재구성합니다. 즉, 자주 탐색하는..

AVL Tree란? AVL 트리란 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)의 한 유형입니다. Adelson-Velsky와 Landis가 1962년에 발명하였으며, 이들의 앞글자를 따서 이름을 붙였습니다. AVL 트리는 각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리인데, 이 서브트리의 높이 차이를 균형 계수(Balance Factor, BF)라 합니다. 그렇기에 삽입과 삭제 연산을 수행할 때마다 트리의 균형 계수를 체크하고, 균형 계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지합니다. Binary Search Tree는 불균형할 때 탐색 성능이 O(logn)에서 O(n)으로 떨어지는 문제가 있었는데, ..

안녕하세요. 저는 전역을 앞두고 복학을 준비하고 있는 대학생입니다. 쿠팡 5월 빅스마일데이를 맞아 노트북을 맞추려는데, 너무 괜찮은 노트북이 아주 싼 가격에 나와 추천드리려합니다. 제품명은 hp 2023 omen 16-n0094AX, HP사의 게이밍노트북입니다. 기존 HP 사의 디자인은 악평이 많았는데, 이번에 탈바꿈하며 알루미늄 재질의 외관과 메탈릭한 실버 심볼의 디자인이 매력적이게 바뀌었습니다. 내부 디자인은 우측 키패드가 없는 텐키리스 디자인입니다. 화면비는 게이밍노트북에 맞춘 16:9 입니다. 제품 스펙은 아래와 같습니다. 대부분 가장 중요하게 생각하시는 CPU와 GPU부터 보면, CPU는 Ryzen 7-6800H, GPU는 RTX 3070ti 입니다. FreeDos가 아닌 Window 11이 탑..

React와 Next.js의 차이 React는 Javascript 기반의 SPA 웹 프레임워크입니다. 컴포넌트를 활용하여 UI를 쉽고 효율적으로 만들 수 있습니다. 이 글에서 강조하고자 하는 내용은 리액트는 CSR(Client Side Rendering), 즉 화면을 그리는 렌더링이 클라이언트에게서 발생합니다. 서버에서 보내주는 HTML과 Javascript 파일을 서버가 아닌, 클라이언트의 브라우저에서 페이지를 만들어줍니다. 이러한 방식은 페이지 간 전환이 부드러워지는 장점이 있습니다. 하지만 HTML과 JS를 다운로드 받는동안 클라이언트는 렌더링이 불가능한, 즉 첫 페이지의 로딩속도가 느리다는 단점이 있습니다. 또한 CSR의 특성상 빈 HTML과 JS를 보낸 뒤 클라이언트의 브라우저에서 JS를 실행시..

Graph란? 그래프란 정점(Vertex)와 간선(Edge)을 모아놓은 자료구조입니다. 그래프는 사이클이 가능하고, 방향 그래프와 무방향 그래프가 모두 존재합니다. 이러한 점에서 그래프가 트리 구조의 상위 집합 개념이라 볼 수 있습니다. 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 차수(degree)라고 하며, 간선에 의해 직접 연결된 정점을 인접 정점(adjacent vertex)라고 합니다. 이러한 정점들을 지나는 경로가 같은 간선을 지나지 않을 때, 단순 경로(simple path)라고 합니다.(0 > 1 > 2 > 3) 그래프는 방향 그래프/무방향 그래프 외에도 간선에 가중치를 넣어 정점 이동 시 비용을 부과하는 가중치 그래프, 모든 정점에 경로가 존재하는 연결 그래프와 특정 정점에 경로가..

Hashing이란? Hash Table을 알기 전에 Hashing의 개념부터 이해해야 합니다. Hashing이란 임의의 값을 Hash함수를 이용해서 고정된 크기의 값으로 변환시키는 작업을 의미합니다. Hash함수는 아래와 같은 종류가 있습니다. Division Method: 인풋값을 테이블의 크기로 나누어 모듈러 연산을 통한 나머지를 사용. 이때 테이블의 크기는 소수(Prime Number)여야 나머지 비트를 고려하여 효율적으로 해싱할 수 있음. Digit Folding: 키의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용 Multiplication Method: 키값 K와 0과 1사이의 실수 A, 임의의 수 m을 사용하여 kAmod1의 연산을 통해 kA의 소수점 이하 부..

Heap이란? 힙은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리의 일종입니다. 완전이진트리란, 왼쪽부터 차례로 마지막 레벨의 노드를 제외한 모든 노드가 채워져있는 트리입니다. 최솟값이나 최댓값을 찾기 위해 배열은 O(n)의 시간이 걸리는 반면, 힙은 O(log2n)의 시간이 걸리기에 효율적입니다. 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 고안되었습니다. 힙의 형태는 다음과 같습니다. 1. 왼쪽부터 채워진 완전 이진 트리이며 2. 자식보다 부모 노드의 값이 큰 최대힙과 자식보다 부모노드의 값이 작은 최소힙이 있다. 탐색을 위한 이진탐색트리(BST)와 다르게, 힙은 최솟값과 최댓값을 찾기 위함입니다. 이때 두 자료구조의 차이점은 BST는 왼쪽 자식 노드 - 부모 ..

Tree란? Tree란 노드와 브랜치를 이용하는 비선형의 자료구조로, 계층적인 구조를 표현하는데 사용됩니다. 예로 컴퓨터에서의 디렉토리 경로도 Tree 구조를 가지고 있습니다. 위 그림의 A, B 등을 각각 노드라 칭하고, 상위 계층의 노드가 없는 A 노드를 루트 노드라 합니다. A-B / B-E와 같이 수직 관계를 가지는 노드를 각각 부모 노드, 자식 노드라 하며 같은 부모를 가지는 B-C / E-F 등을 형제 노드라 부릅니다. 각 노드를 연결하는 선을 브랜치(혹은 엣지)라고 부릅니다. Tree에서 노드 Depth는 루트에서 해당 노드까지 거치는 edge의 수를 의미합니다. 노드 Level은 특정 Depth를 가지는 집합 (Level 1 = {B, C})을 의미합니다. 노드 Degree는 자식 노드의 ..