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-Set에 속한 간선들을 제거하면, 그래프는 두 개의 연결되지 않은 부분 그래프로 나뉘게 됩니다. Cut Propertycut-set의 간선 중, 가중치가 가장 작은 간선들은 반드시 모든 MST에 포함됩니다.가장 가벼운 간선을 선택함으로써, 최..

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

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

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

1. Heap 이란?최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조 입니다.완전 이진트리 기반 입니다.우선순위 큐 구현에 사용됩니다. 완전 이진트리마지막 레벨을 제외한 모든 노드가 채워져 있는 이진트리 자료구조 입니다.마지막 레벨은 왼쪽부터 채워져 있어야 합니다. 인덱스모든 노드를 배열로 표현할 수 있습니다.노드 간 관계를 배열 인덱스를 통해 접근할 수 있습니다.왼쪽 자식 노드 indexindex*2 + 1오른쪽 자식 노드 index index*2 + 2부모 노드 index(index-1) / 2 2. 종류최대 힙부모 노드가 자식 노드보다 크거나 같은 값을 가집니다. 최소 힙부모 노드가 자식 노드보다 작거나 같은 값을 가집니다. 3. 연산Heapify전체 배열을 힙 구조로 만드는 연산입니다.리..

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로 객체간의 관계를 표현합니다.계층적 또는 네트워크 형식으로 연결되어 있습니다.명확한 부모-자식 관계가 존재 X1:n or n:n현실세계의 다양한 문제를 효과적으로 모델링하기에 적합합니다. 용어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트리를 구성하는 기본단위 입니다...