GiYeong

Tree 트리는 비선형 구조로서, 원소들 간에 1:n 관계를 가지고 계층 관계를 가지는 자료구조이다. 상위 원소에서 하위 원소로 내려가면서 확장되는 나무 모양을 하고있다. 용어 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 라고도 부른다. 내부(internal) 노드: 단말 노드가 아닌 노드 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름) 형제(sibling): 같은 부모를 가지는 노드 노드의 크기(size): 자신을 포함한 모든 자식 노드의 개수 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 노드의 레벨(level): 트리의 특..

Heap 특정 연산을 빠르게 수행하기 위한 완전 이진 트리(Complete Binary Tree) 자료 구조로서, 여러 값(node) 중 최대값/최소값을 찾는 연산이 빠르다. Max Heap(최대 힙) 값이 가장 큰 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 값이 자식 노드의 값보다 크다. 따라서 루트 노드는 가장 큰 값을 가지게 된다. Min Heap(최소 힙) 값이 가장 작은 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 값이 자식 노드의 값보다 작다. 따라서 루트 노드는 가장 작은 값을 가지게 된다. Priority Queue(우선순위 큐) 먼저 들어오는 데이터가 먼저 나가는 형태가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 일반적으로 Heap을 사용하여 구현한다...

Stack 가장 마지막에 삽입(PUSH)된 데이터가 가장 먼저 삭제(POP)되는 자료구조이다. 즉, 후입선출(LIFO, Last In First Out) 방식의 자료구조이다. 비어있는 Stack에서 데이터를 POP 하는 경우를 'stack underflow', Stack이 꽉 찬 상태에서 데이터를 PUSH 하는 경우를 'stack overflow'라고 한다. 활용예시 웹 브라우저 방문기록(뒤로가기) 역순 문자열 만들기 실행 취소(undo) 후위 표기법 계산 수식의 괄호 검사 Queue 가장 먼저 삽입(OFFER)된 데이터가 가장 먼저 삭제(POLL)되는 자료구조이다. 즉, 선입선출(FIFO, First InFirst Out) 방식의 자료구조이다. 삭제연산이 수행되는 곳을 front, 삽입연산이 수행되는 ..

Hash Function(해시 함수) 데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑 전 기존 데이터의 값을 Key, 매핑 후 데이터 값을 Hash Value(해시 값), 매핑하는 과정을 Hashing이라고 한다. Hashing(해싱) 임의의 길이의 값을 해시 함수(Hash Function)을 사용하여 고정된 크기의 값으로 변환하는 작업 Hash Table(해시 테이블) Hashing을 사용하여 데이터를 저장하는 자료구조를 Hash Table이라고 하며, 이는 기존의 자료구조인 이진탐색트리나 배열에 비해서 굉장히 빠른 속도로 탐색, 삽입, 삭제가 가능하다. 즉, Hash Function을 사용하여 변환한 값(Hash Value)를 index로 사용..

Array Linked List 저장방식 요소들이 인접한 메모리 위치에 저장된다. 요소들이 메모리 어딘가에 저장되며, 새로운 요소의 주소는 Linked List의 이전 노드(Node)에 저장된다. 종류 일차원배열, 이차원배열, 다차원배열 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 다중 연결 리스트(Multiply Linked List), 원형 연결 리스트(Circular Linked List) 크기 Array의 크기는 반드시 배열 선언 시점에 지정되어야 한다. LinkedList의 크기는 새로운 요소가 추가될 때, runtime 시점에서 크기가 커질 수 있다. 메모리 할당 Array가 선언되자마자 Compile 시점에 Heap 영역에 메..

시간복잡도(Time Complexity)는 알고리즘의 효율성을 판단하기 위한 지표로서, 프로그램 수행에 걸리는 절대적 시간이 나닌 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다. 시간복잡도에 사용되는 표기법은 Big-O(상한 점근, 최악의 경우를 나타낸다.), Big-Omega(하한 점근, 최선의 경우를 나타낸다.), Theta(그 둘의 평균)가 있다. 가장 자주 사용되는 표기법은 Big-O 표기법으로, 최악의 경우를 고려한다. 즉, '최소한 특정 시간 이상이 걸린다'가 아닌 '이정도 시간까지 걸릴 수 있다'를 고려한다. Heap의 시간복잡도 정렬의 시간복잡도 자료구조의 시간복잡도