뜌릅

B-Tree 검색을 위한 자료구조 중에서 이진 트리는 비록 하나의 부모가 두개의 자식을 가지질 못하고 자칫 균형이 맞지 않으면 검색 효율이 선형 검색급으로 떨어지지만, 잠재력이 크다. 그렇지만 이진트리에게 한계는 있고, 이를 극복하기 위해 간결함과 균형을 유지할려는 노력이 있었다. 그중에서 B트리가 등장하였다. 많은 수의 자식을 갖을 수 있게 일반화 되었고, (보통 몇개까지 자식을 갖을 수 있는지 정해 놓는다. ex: 4kb 해당 프로그램의 default Page Size에 맞춰 설정된다.) 그 뿐만 아니라 트리의 균형을 자동으로 맞추는 로직까지 갖추었다. 이 균형 로직은 단순하면서 효율적이다. 위에서도 잠깐 언급했듯이, 블록 단위로 노드의 사이즈가 정해진다. 외부 기억장치는 블럭 단위로 입출력을 하기 ..

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 구조이다. 사용 예 : 자동완성 기능, 사전 검색 등 문자열을 탐색하는데에 특화되어있는 구조이다. 레딕스 트리 or 접두사 트리 or 탐색 트리라고도 한다. 트라이 장단점 - 문자열 검색을 빠르게 한다. (코딩 테스트, 문자열 문제에서 활용 가능 할듯) - 문자열 탐색할때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간복잡도 측면에서 훨씬 더 효율적이다. - 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다. 시간복잡도 시간복잡도는 문자열 최대 길이가 M이면 O(M)으로 문자열 검색이 가능하다. 코드 static class Trie { boolean end; boolean pass; T..

이진 탐색 트리 목적: 이진 탐색: O(logN)이다. But 삽입과 삭제가 불가능하다. 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간 복잡도가 O(N)이다. 이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리'이다. 특징: - 각 노드의 자식이 2개 이하 - 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 - 중복된 노드가 없어야 함 중복이 있다면 굳이 이진검색트리를 사용하게 할 필요가 없다. 차라리 중복개수를 저장할 수 있게 노드의 구조를 바꾸는게 효율적이다. 삽입과, 삭제가 이루어져도 위의 구조를 유지하는것이 핵심이다. 시간복잡도: 탐색, 삽입, 삭제 모두 시간복잡도가 O(h)가 된다. h = logN, worst h= N이다. 이를 해결 하기 위해..

Node와 Edge로 이루어진 자료구조이다. 정의 하자면 Cycle이 없는 그래프이다. 배열과 구조체 2가지 방법으로 만들수 있다. 배열로 만들게 되는 경우, 자식노드의 개수를 한정지어야 한다. 구조체로 만들게 되는 경우 struct Node { Node child[]; int value; } 위와 같이 구성할 수 있다. 트리의 순회 방식은: - 전위 순회: 각 부모 노드를 순차적으로 먼저 방문. (부모 -> 왼쪽 자식 -> 오른쪽 자식) - 중위 순회: 왼쪽 하위 트리를 방문 후 부모 노드를 방문하는 방식. ( 왼쪽 자식 -> 부모 -> 오른쪽 자식) - 후위 순회: 왼쪽 하위 트리부터 하위를 모두 방문 후 부모 노드를 방문하는 방식이다. ( 왼쪽 자식 -> 오른쪽 자식 -> 부모) - 레벨 순회: 부..

힙의 개념: 우선 순위 큐에 사용되는 자료구조이다. 트리로 작성된다. 힙이 제일 좋은거 같다. 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 대표적으로 최대힙과 최소힙이 존재한다. - 최대 힙: 부모 노드의 key값이 자식 노드보다 크다. - 최소 힙: 부모 노드의 key값이 자식 노드보다 작다. 힙의 구조: 일반적으로 배열로 구현이 된다. 첫번째 인덱스인 0은 사용이 되지 않으며 1이 root 노드로 사용된다. 이용사례: - 시뮬레이션 시스템 - 네트워크 트래픽 제어 (다익스트라, 병목 제어) - 운영 체제에서의 작업 스케쥴링 (동적 힙 구조 응용)

해시의 목적 해시 테이블의 가장 큰 목적은 O(1)로 찾고자 하는 데이터를 찾는 것이다. search의 시간 복잡도가 O(1)이 되는 것. 고정된 길이의 데이터로 매핑하는 것이고, 일반적으로 해싱에 쓰이는 메모리는 매우 비싸다. 해시는 index을 통해서 Random access가 가능하다. 이를 위해선 index가 어디있는지를 알아야 하며, 해당 index는 해시 함수(해시 알고리즘으로 index값을 계산해주는 알고리즘이다.)을 통해서 알 수 있다. 해시의 개념 해시함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑전 원래 데이터의 값을 Key라고 하고, 매핑 후 데이터의 값을 해시값(value)라고 한다. 매핑하는 과정 자체를 hashing한다고 한다. 해시 함수는 해시 값..

스택 입력과 출력이 한 곳(방향)으로 제한 LIFO ( Last In First Out, 후입선출): 나중에 들어온게 먼저 나감. 함수의 콜스택(Stack Trace라는 단어를 디버깅중 봤을 수도 있다. 봤다면 그게 이거다.) , 문자열 역순 출력, 연산자 후위표시법 등등에 쓰인다. 스택은 Array로 구현하는 방법과 LinkedList로 구현하는 방법 2가지가 존재한다. Array로 구현할시 최대 사이즈가 존재하며, 가득 차면 크기를 늘리든가 해야한다. 자바,코틀린에서의 stack 코틀린에서는 Stack이라는 클래스가 존재하나, Vector을 상속받아서 구현한 클래스로, arrayList으로 구현한것과 동일하다. 따라서 Stack 클래스의 경우 메모리가 가득찰 경우 가변적으로 용량을 늘려준다. 메모리 ..

특징 Array와 ArrayList는 LinkedList와 다르게 메모리가 연속적인 특징을 갖고있다. Array와 ArrayList의 차이는 할당된 메모리의 크기가 가변적인지 아닌지의 차이를 갖고있다. Array는 고정된 메모리가 할당되고, ArrayList는 메모리를 동적으로 할당할 수 있다. 자바에서는 크기가 가득찰 경우, 1.5배 증가한다. LinkedList는 단일, 다중 여러가지 종류가 존재한다. 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있다. 장단점 위와 같은 자료구조적인 특징 때문에 장단점에서의 차이가 생기게 된다. Array: 배열은 선언할 때 크기와 데이터 타입을 지정해야 한다. 따라서 최대 사이즈를 알 수 없을때는 부적합하며, 중간에 데이터를 삽입하거나 삭제할 때도 ..

쓰고싶을때 쓰는 글 이번에는 단순 연결 리스트에 대해서 공부를 하였다. 순차 자료구조인 선형리스트와 달리 단순 연결 리스트는 연결 자료구조이다. 즉 데이터의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다. 아무튼 본론으로 돌아와서 단순 연결 리스트에 대해서 설명하겠다. 연결 리스트는 선형 리스트(배열)과는 다르게 포인터를 통해서 구현 하였다. 전에 쓴 글에서 선형 리스트는 요소의 삭제와 위치 변경간에 낭비가 심하다고 하였다. 그에 따라 선형 리스트보다는 지금 보기에는 좀 불편해 보이지만, 배열의 물리적인 순서를 맞추기 위한 오버헤드 낭비측면에서는 훨씬 낫다고 볼수 있다. 연결리스트는 포인터를 통해 구현했다. 이게 무슨말이냐.... 기차를 떠올려봐라. 각 기차칸은 다음 기차칸과 연결이 되어있는데, ..

쓰고싶은 글씁니다. 이번에는 선형리스트의 응용과 구현에 대해 공부했다. 근데 사실 제목대로라면 구현은 겁나쉽다. 그냥 배열이니까. 그러니 정확히는 응용을 구현한것이다. 제목은 좀 부정확하지만, 내가 공부한 책 부제목이 저렇다. 그래서 딱히 안바꿨다. 뭐라고 제목지어야할지 생각하기 싫어서..... 암튼 공부한걸 여기다가 적으면서 이해한걸 다시한번 돌아보는 의미를 갖을려고 글을 쓰는데, 이번에는 글을 쓰기가 힘들다. 이번챕터에서는 선형리스트로 다항식과 행렬을 표현하는것을 공부했는데, 여기다가 내가 짠 코드를 올리기도 그렇고, 일일이 설명하기도 애매하다. 그래서 대충 다항식과 행렬의 추상자료형은 설명하지 않고, 그 둘을 어떻게 나타내는지만 써야겠다. 다항식의 경우 A(n)x^n +...... + A(0)x^0..