CS - 자료구조

자료(data)를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법자료의 각 원소들이 논리저으로 정의된 일정한 규칙에 의해 나열된 집합단순 구조(Simple Structure) True/False, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는

정의같은 타입의 변수들로 이루어진 유한 집합논리적인 순서와 물리적인 순서가 같은 구조Element(요소) 배열을 구성하는 각각의 값Index(인덱스) 배열에서의 위치를 가리키는 숫자 값에 대한 유일무이한 식별자 (랜덤 엑세스 가능)특징크기가 정해져 있다. 요소

데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료 구조 이다.(배열/리스트와 유사하게) 값을 저장하는 연산과 저장된 값을 거내는 연산이 제공 된다.그러나, 매우 제한적인 규칙 (LIFO, FIFO) 등을 따른다.스택은 가장 최근에 저장된 값 다음에

정의노드(데이터)들을 간선으로 연결한 계층형 자료 구조트리 구조트리는 값을 가진 노드(Node) 와 이 노드들을 연결해주는 간선(Edge) 으로 이루어져 있다.root 노드 트리의 가장 위쪽에 있는 노드 루트는 트리에 1개만 존재leaf 노드 = 단말 노드, 외부

정의이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입, 삭제가 불가능연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)이 두

정의완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조데이터들이 우선순위를 가지고 있음. 우선순위가 높은 데이터가 먼저 나감완전 이진트리 : 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며,

이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어진다. 하지만, 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있다.정의이진트리에서 발전되어 모든

B+ Tree 정의 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 B Tree에 추가로 있음 (기존의 B Tree 와 데이터의 연결리스트로 구현된 색인 구조)

정의Trie (트라이)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 입니다.시간 복잡도제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같습니다.생성시 시간 복잡도 : O(M\*L), 모든 문자열들을 넣어야 하니

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.정의key를 고정된 길이의 Hash로 변경해주는 역할을 한다.이 과정을 hashing이라고 한다.Input : key, O

정의단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아놓은 자료구조즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조 이다.그래프와 트리의 차이정점(vertex) : 위치라는 개념. (node 라고도 부름)간선(edge)