CS & AI/Data Structure

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 배열이 이진 탐색 트리보다 더 낫지 않나? 배열의 성능이 O(1)인데 배열을 응용하면 이진 탐색 트리처럼 찾는 것보다 훨씬 더 빠를 수 있지 않을까 하는 생각이 들었다.배열의 O(1) 성능은 무적이다. 이걸 이용해보는거다. 상수 시간에 데이터를 찾아내는 마법의 자료구조 해싱 등 용어가 낯설 뿐 결국 배열이다.아이템의 key를 index number로 사용한다는 것. 아이템 key를 인덱스 번호로 쓰고 그 인덱스 자리에 아이템을 저장한다.해시라는 ..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 데이터를 더 많이 담고 싶은데... 노드를 더 크게 만들어 보는거야 레드 블랙 트리나 B-트리 모두 2-3트리에서 나온 개념이다. 아무래도 대용량의 데이터를 다루기 위해 나온 자료구조이기 때문에 데이터베이스 분야에서 많이 쓰이는 형태라 할 수 있겠다. B-트리 다수의 키를 가진 노드로 구성되어 다방향 탐색(Multiway Search)이 가능한 균형 트리2-3 트리는 B-트리의 일종으로 노드에 키가 2개까지 있을 수 있는 트리B-트리는 대용량..

본 게시글은 학부 강의 '자료구조' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 2-3 트리의 구현이 너무 복잡해..2-3 트리를 이진 트리처럼 만들어 보는거야!! BST에 융통성이 생긴 2-3 트리. 성능도 좋았지만 노드가 많아지면서 노드 구조가 복잡해졌다. 그러기에 경우의 수가 너무 많아지는게 문제였다.2-노드와 3-노드를 처리해야 하고삽입, 삭제 시 너무나도 다양한 케이스들이 존재했다.메모리 효율성 측면에서도 항상 3개의 자식 포인터 공간이 필요했다. 그래서 2-노드일 때 하나는 낭비가 된다. 그래서 좀 더 나은 방법은 없을까? 레드 블랙 트리노드에 색을 부여하여 트리의 균형을 유지탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(lo..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 이진 트리가 아니어도 괜찮아! 노드에 키를 2개까지 넣어보자!! 자료구조 등의 여러 컴퓨터 과학 과목을 듣다보면 모든 테크닉에는 장단점이 명확하게 존재했다. 그래서 단점을 보완한 새로운 테크닉이 등장해도 거기에는 또 다른 단점이 생겼고 보완되기 위해 지금도 새로운 방법론들이 계속 제시되고 있다. 2-3 트리도 아이디어와 함께 이전 트리의 단점을 보완하기 위해 탄생했을 것이다. 앞서 작성한 이진 탐색 트리에는 단점이 존재했다. 일반적인 BST에는 최악의 경우..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. AVL 트리(Hight Balanced Binary Trees)AVL 트리는 Adelson-Velskii & Landis Tree 라고도 한다. 만든 사람의 이름을 땄다.AVL 트리는 트리가 한쪽으로 치우치는 것을 방지하여 트리 높이의 균형을 유지균형(Balanced) 이진 트리 : 탐색, 삽입, 삭제 연산의 수행 시간 O(logn) 보장 AVL 트리는 삽입이나 삭제로 인해 균형이 어긋나면 회전 연산을 통해 트리의 균형을 유지한다. AVL 트리는 임의의 노..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 사전(Dictionary)저장된 데이터에 대해 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조어찌보면 파이썬의 딕셔너리와 일맥상통. Key와 Value가 존재한다는 것. 탐색 트리저장된 데이터에 대해 접근, 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조배열, 연결 리스트 : O(n) 시간스택, 큐 : 특정 응용에 적합한 자료구조이진 탐색 트리, AVL 트리, 2-3 트리, 2-3-4 트리, RB 트리, B-트리 이진..

보호되어 있는 글입니다.

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 트리 배열이나 연결 리스트 - 데이터를 일렬로 저장하므로 탐색을 순차적으로 수행정렬된 배열에서는 이진 탐색을 통해 효율적인 탐색이 가능하지만, 삽입 / 삭제 후 정렬 상태를 유지하기 때문에 O(n) 시간일반적인 트리(General Tree)는 트리를 거꾸로 세워놓은 형태의 자료구조HTML과 XML의 문서 트리, 자바 클래스 계층구조, 운영체제의 파일시스템, 탐색트리, 이항(Binomial) 힙, 피보나치(Fibonacci) 힙과 같은 우선순위 큐공집합도 트리..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. RemindArray, Linked List의 기능과 특성을 이해했다. 그리고 이에 대한 성능, 퍼포먼스를 Big O로 표현도 해보았다. Stack : First-In Last-Out. Top pointer 구분할 줄 알아야 한다.Queue : First와 rear를 구분할 것 큐(Queue)삽입과 삭제가 양 끝에서 각각 수행되는 자료구조일상생활의 관공서, 은행, 우체국, 병원 등에서 번호표를 이용한 줄서기선입 선출(First-In Last-Out, FIFO)..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 수식의 표기법 프로그램을 작성할 때 수식에서 +, -, * , / 와 같은 이항 연산자는 2개의 피연산자 사이에 위치 : 중위 표기(Infix Notation)컴파일러는 중위 표기 수식을 후위 표기(Postfix Notation)으로 바꾼다.그 이유는 후위 표기법 수식은 괄호 없이 중위 표기 수식을 표현할 수 있기 때문전위 표기(Prefix Notation) : 연산자를 피연산자들 앞에 두는 표기 후위 표기 수식 계산 >피연산자는 스택에 push하고, 연산..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 스택(Stack)한쪽 끝에서만 항목 삽입 / 삭제하는 자료구조새 항목을 저장하는 연산 : pushTop 항목을 삭제하는 연산 : pop후입 선출(Last-In First-Out, LIFO) 배열로 구현한 스택마지막 index를 top에 가지고 있다.A[++top;] = "망고"A[top++;] = "망고"는 틀린 문법! 주의할 것 단순 연결 리스트로 구현한 스택정의된 스택대로 사용하는게 제일 효율적이다. 배열로 구현한 ArrayStack class..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 단순 연결 리스트(Singly Linked List) 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조동적 메모리 할당을 받아 노드(Node)를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리켜 노드를 한 줄로 연결Size가 커도 Link를 가져야 하는 단점연결 리스트에서는 삽입이나 삭제 시 다른 노드들의 이동이 불필요배열의 경우 최초에 배열의 크기를 예측하여 결정해야 하므로 대부분의 경우 배열에 빈 공간이 있으나, 연결 리..