Programming/Data Structures7 B-트리에 대해서 알아보기 요즘에는 데이터베이스 관련 공부를 하고 있는데 습득한 지식을 기록해두는 것이 좋다고 생각해 글을 작성한다. 소개 데이터베이스에서는 데이터를 저장하는 방식이 다르다. 크게 봐서는 온메모리와 디스크로 나뉘는데 온메모리는 쉽게 말해 RAM 같은 곳에서 상주하는 것이고 디스크는 HDD, SSD 과 같은 것이다. B-트리는 이 중에서 디스크 저장할 때 사용되는 알고리즘이고 페이지-블럭-플레인-다이 등의 구조에서 효율적인 관리에 대한 방법을 제시한다. 실제로도 사용이 되고 있는 B-트리 구조의 정확한 표기는 B+-트리 이다. 여기에서는 편의를 위해 B-트리로 표기한다. B-트리란? (feat. Binary Tree) Binary 트리의 약자로 혼돈할 수 있지만 그것은 맞지 않다. 쉽게 말해 B-트리는 self-ba.. 2022. 5. 31. Merge Sort 선결론 : Merge Sort는 최악의 시나리오에는 O(n log n)이지만 메모리를 너무 사용할 수도 있다는 점 오늘은 sorting 알고리즘 중 하나인 merge sort 에 관한 글을 써보고자 한다. Merge Sort (???) Merge Sort은 간단하게만 보자면 데이터를 정리할 때 사용되는 방법 중 하나이다. 데이터를 정리할 때 어떤 방법을 사용하느냐에 따라 매우 다른 효율성을 보여줄 수 있는데, merge sort 의 시간 복잡도는 최악의 경우에 O(log n)으로 나쁘지 않다고 판단이 되는 것 같다. 일단 간단한 소개는 역시 GIF가 최고라고 생각하기 때문에 아래에 우연히 찾아낸 이미지를 삽입했다. 위 그림에서 보이는 것처럼 사실 작동하는 방식은 매우 단순하다. - 주어진 배열을 각각 따.. 2022. 5. 31. Graphs in Data 선결론 : Graph는 데이터 간 관계를 파악하는데 많은 도움을 줄 수 있다 Graph 란? 구조화 되어 있지 않은 것이 때로는 큰 장점이 될 수도 있다 이번이 그런 경우라고 할 수 있다 트리 구조나 관계형 데이터베이스처럼 갖춰진 형식에 따라야 하는 것이 아니기 때문에 그만큼의 자유도를 얻을 수 있다 그래프는 이해하는데 그다지 어렵지 않다 일단 노드라는 것들이 존재하는데 각 노드마다 데이터를 가지고 있다고 보면 된다 그리고 노드끼리 관계가 있을 수도 있는데, 이 때에는 그 관계를 edge나 relationship이라고도 부른다 물론 이 관계의 방향은 한 방향이거나 양 방향일 수도 있다. 그리고 그에 따라 symmetrical 혹은 asymmetrical 이라고도 부른다 그냥 떠다니는 노드들이 존재하며 만.. 2022. 5. 31. Tree and Binary Search Tree 선결론 : 나무 구조와 BST의 활용도는 많지만 구조에 따라 효율성이 정해진다 Tree 란? 데이터 구조에서 tree란 나무 구조를 말한다 나무의 특징인 가지치는 현상과 비슷해 이름이 붙여졌는데 누가 붙였는지 참 잘 붙였다는 생각이 일단 든다 나무에서 가지들이 새로 자랄려면 시작하는 기둥이나 가지가 있고 새로 자라는 가지에 또 가지가 있을 수도 있듯이 Tree와 같은 Abstract Data Type (ADT)에서도 마찬가지로 같은 현상들이 존재한다 딱히 어려울 건 없다. 데이터에서는 node라고 불리는 것들이 잎사귀 대신에 가지에 붙어있다고 생각하는게 편리할 수도 있다. 다만 각 노드는 굳이 잎사귀가 될 필요는 없고 가지도 될 수도 있다는 점. 일단 시작하는 기둥을 root라고 부른다 여기서부터 가지들.. 2022. 5. 31. Hash Tables 선결론 : Hashing의 목적을 이루는 것이 중요! Hash Table 이란 ? 해쉬 테이블은 쉽게 말해 time complexity를 O(1)으로 만들려는 목적을 지니고 있다 (정 안되면 O(n)). 배열에 있는 요소를 꺼내기 위해서는 여러가지 방법이 존재한다 그 중 하나는 각 배열의 요소를 순차적으로 확인하는 brute force 방법도 있다. 하지만 그러면 배열의 길이에 따라 시간과 성능도 낮아진다. 많은 요소들을 포함한 배열을 접근할 때 만약에 배열의 인덱스를 알고 있다면 수월하다는 말이다. 즉 반복문을 돌려 각 요소를 확인할 수 있지만 어느 위치에 있는지 알고만 있다면 배열의 길이가 어떻든, 크기나 위치가 어떻든 간에 그저 배열의 특정 인덱스의 요소값을 가지고 올 수 있다는 것이다. 그러면 어.. 2022. 5. 30. Linked List 선결론 : 데이터의 크기가 작고 미리 알 수 있다면 일반 배열을 사용하고 아니면 linked list 사용 Linked List 란? 쉽게 말해 연결되어 있는 배열들이다. 일반적으로 배열에는 값들이 들어간다. let exampleArray = [1, 2, 3, 'a', 'b'] 하지만 linked list 에서는 각 값마다 값과 다른 값으로 이동하는 링크가 담겨져 있다. 그렇기 때문에 배열들의 요소는 Node라고도 불리기도 하는데 이러한 이유에서 그런거다. 시작하는 node를 head라고 부르고 끝나는 지점, 즉 마지막 node는 tail이라고도 한다. 이미 눈치챘겠지만, 영원한 뫼비우스의 띠의 세계로 컴퓨터를 보내고 싶지 않다면 tail의 주소는 null, 즉, 비었다. head에서부터 tail까지 계.. 2022. 5. 30. Queues and Stacks 선결론: 어떻게 데이터 구조를 구축할지는 코드 성능과도 연관이 없지 않다 Queue Queue 라는 데이터 구조는 마치 빨대와 같이 작동을 한다고 생각한다. 아래와 같은 그림에 보면 알겠지만 빨대에 먼저 들어가면 먼저 나오게 된다. 데이터 구조에서 queue는 First In First Out (FIFO)라는 개념이라고 생각할 수 있다. 제일 먼저 들어간 것이 나온다는 개념인데 큐는 몇가지 중요한 속성과 메소드가 있다. 속성 : - 첫 요소는 곧 제일 처음에 들어간 요소이다 - 첫 번째 요소와 마지막 요소가 어디 있는지 알기 위한 두 개의 지점이 존재한다 메소드 : - enqueue : 큐에 추가할 수 있어야 한다 - dequeue : 큐에서 뺄 수 있어야 한다 Stack Stack은 queue와는 달리.. 2022. 5. 30. 이전 1 다음
