IT LAB

1. N-ary Tree 각 노드가 세개 이상의 자식노드를 가지는 트리입니다. 주로 데이터베이스나 파일시스템에서 인덱스용으로 사용합니다. 디스크 접근을 최소화하는데 유용합니다. 2. 종류 B-Tree B+Tree

1. 이진 탐색 트리 (Binary Search Tree, BST) 왼쪽 노드는 루트보다 작고 오른쪽 노드는 루트보다 큰 정렬된 이진 트리입니다. 검색에 특화된 이진트리 입니다. 특징 정렬되어 있어 탐색, 삽입 삭제 연산이 효율적입니다. Time Complexity $O(logN)$ 2. 종류 AVL Tree (균형 이진 트리) Red-Black Tree (균형 이진 트리)

1. Minimum spanning tree가중 + 무방향 그래프의 하위 트리 중,그래프의 모든 정점을 포함(spanning subgraph)하고, 사이클이 없으며,  가중치의 합이 최소인 하위트리를 말합니다. 2. Cut그래프의 정점들을 두 개의 분리된 집합으로 나누는 것을 의미합니다.각 집합은 비어있지 않습니다. cut-set 두 집합 사이의 cut을 이루는 간선들의 집합입니다.컷을 통해 나뉜 두 집합의 정점들 사이를 잇는 모든 간선의 집합한 집합의 정점들과 다른 집합의 정점들 사이의 연결을 나타냅니다. MSTcut-set의 간선 중, 가중치가 가장 작은 간선들은 반드시 모든 MST에 포함됩니다.가장 가벼운 간선을 선택함으로써, 최소 신장 트리를 구성하기 때문입니다.가장 가벼운 간선이 여러 개일 경우..

1. Union-Find 서로소 부분 집합들로 나눠진 원소들을 관리하는 자료구조 입니다. 서로소 집합 (disjoint) 상호 배타 집합 공통 원소가 없는 두 집합입니다. 두 집합 A와 B가 있을 때 교집합이 공집합이라면, A와 B는 서로소 관계에 있습니다. 2. 연산 Make-Set 하나의 원소만을 가지는 집합을 만듭니다. Union 두 대표 원소의 집합들을 하나로 합칩니다. 두 대표 원소를 입력 인자로 사용합니다. Find 주어진 원소의 대표원소를 반환합니다. 3. 구현 Circularly Doubly Linked List Head 대표 원소 연산 find: head 반환 union: 두 링크드리스트 병합 시간복잡도 O(N) 연산 속도가 느려 tree 방식이 고안되었습니다. Tree 노드 root: ..

1. Linked List 란?선형 자료구조 입니다.각 요소들을 연쇄적으로 연결포인터 사용 Head맨 처음 요소를 가리키는 포인터링크드리스트마다 가지고 있습니다. Node각 요소를 의미하는 자료구조 입니다. 구성값next 포인터: 다음 노드를 가리키는 포인터 장점동적 할당크기가 동적으로 조정됩니다. (생성시, 크기가 정해지지 않음)효율적인 메모리 관리가 가능합니다. (메모리) 비연속적동적 할당으로 메모리가 잡히므로 비연속적인 공간에 저장됩니다. (다른 요소에 독립적)다음 노드를 찾아가기 위해 next 포인터를 가집니다. 효율적인 연산배열과 같은 추가적인 연산이 필요하지 않습니다. (요소들이 비연속적인 공간에 저장되므로) 단점추가적인 메모리 비용각 노드는 포인터를 가져야 하므로 추가적인 메모리 비용이 발생..

1. Array 란? 같은 타입의 요소들을 보관하는 자료구조 입니다.요소들의 중복을 허용합니다. (메모리) 연속적요소들은 (물리적으로) 메모리 연속적인 공간에 저장됩니다. 기본 주소 (배열 주소)첫번째 요소의 메모리 주소 입니다. 인덱스 기반각 요소들은 특정 인덱스에 대응되어 구성되어 있습니다.Random Access가 가능합니다. 요소의 주소기본 주소로부터 현재 요소의 인덱스와 데이터 타입 크기를 곱하여 알 수 있습니다. 정적 할당생성되는 시기에 크기가 정해집니다. 초기 사이즈보다 커질 경우 (추가 연산) 2배 큰 새로운 배열을 생성하고, 새 배열에 요소들을 이주시킵니다. 중간 요소의 추가 연산삽입: 삽입할 곳의 공간을 만들기 위해 뒤 요소들을 뒤로 한칸씩 이동시킵니다. (right shift)삭제: ..

1. Trie 란?문자열 탐색에 최적화된 트리 자료구조 입니다.1959년 Edward Frendkin에 의해 처음 소개되었습니다. 2. 기능사전 검색완전한 단어나 문구를 입력하여 해당 단어를 찾아냅니다. 접두사 검색뿌리부터 시작해서 각각의 가지가 알파벳 문자를 표현합니다.표시된 노드까지 문자열을 이루고 있음을 마크해둡니다. (각 단어가 끝나는 지점에 표시)자동완성 기능을 구현할 수 있습니다. 3. 구현더보기public class MyTrie { class Node { Map children; boolean endOfWord; Node() { this.children = new HashMap(); this...

1. Graph 란?비선형 다대다 자료구조 입니다. vertex와 edge로 객체간의 관계를 표현합니다.명확한 부모-자식 관계가 존재하지 않습니다.현실세계의 다양한 문제를 효과적으로 모델링하기에 적합합니다. 용어Vertex(정점)정점Edge(간선)정점과 정점을 연결하는 간선을 의미합니다.Adjacent(인접)두 정점이 간선으로 연결되어 있을 경우, 두 정점은 "인접하다" 표현합니다.Incident(부속)정점간의 연결을 담당하는 간선을 "부속되었다" 표현합니다.Degree(차수)한 정점에 부속된 간선의 개수를 그 정점의 "차수"라 표현합니다.Path(경로)출발지에서 목적지로 이어지는 일련의 간선들을 의미합니다.Cycle(사이클)시작노드와 종료노드가 동일한 경로를 의미합니다. (경로 상의 노드는 중복 허용 ..

1. Tree 란? 그래프의 일종 노드들과 이 노드들을 연결하는 엣지들로 구성된 일종의 그래프 순환이 없는 연결 그래프 모든 노드가 연결되어 있는 구조 어떤 두 노드를 선택해도 경로는 항상 단 하나만 존재 계층형 구조 루트노드부터 시작해서 여러 개의 하위 노드로 분기됩니다. 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다. 예시 파일 시스템 (디렉토리) 용어 A (Root, Depth: 0, Height: 2, Level: 1) / \ / \ B C (Node, Depth: 1, Height: 1, Level: 2) / \ / \ D E F G (Leaf, Depth: 2, Height: 0, Level: 3) Node 트리를 구성하는 기본단위 입니다. Root 트리의 최상위 노드입니다. Leaf..

1. HashTable 이란?매핑할 수 있는 자료구조 입니다. (key-value)key를 사용하여 해당되는 value를 빠르게 찾을 수 있습니다. Hash Function임의 크기의 데이터를 고정된 크기의 데이터로 매핑하는 함수Key를 입력받아 HashCode를 출력합니다. HashCode정수값HashTable의 인덱스로 사용됩니다.총 버킷 갯수로 나머지 연산을 수행합니다.  (인덱스 값으로 사용하기 위함)h(x) = M % m 좋은 해시함수의 특징일관성같은 키 값으로 항상 동일한 해시 코드를 생성해야 합니다.빠른 계산효율적이며 빠르게 해시 코드를 생성해야 합니다.테이블 크기를 2의 거듭제곱으로 설정하면 모듈러 연산을 빠르게 할 수 있습니다.균등성가능한 한 모든 버킷에 균등하게 데이터를 분산시켜야 합니..