Computer Science/Data Structure
-
Tree(트리)Computer Science/Data Structure 2022. 3. 27. 17:18
Tree(트리)의 개념과 특징 트리 자료구조란? 트리는 그래프의 한 종류로, 한개 이상의 node(노드)들이 나무가지처럼 연결된 자료구조를 의미한다. 하나의 루트 노드와 0개 이상의 자식 노드를 가진 방향성 있는 그래프를 트리라고 한다. 트리의 특징 하나의 root node(루트 노드)를 가진다 루트 노드는 0개 이상의 자식 노드를 가진다 자식 노드는 또 각자 0개 이상의 자식 노드를 가지고 있고 이는 반복적으로 정의된다 즉, 트리는 재귀적인 구조를 가지고 있다 트리는 노드와, 노드를 연결하는 edge(간선)으로 구성된다. 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류다. 때문에 트리에는 cycle(사이클)이 존재하지 않는다. 즉, 같은 노드를 거치지..
-
Stack(스택)과 Queue(큐)Computer Science/Data Structure 2022. 3. 22. 00:40
Stack Stack이란? 단어 그대로 생각해보자. stack을 동사로 사용하면 '쌓다', '(쌓아서) 채우다'라는 뜻을 가지고 있다. 그렇다. 너무 당연하게도 스택은 데이터를 쌓아 올린 구조다. 흔히들 스택을 '바닥이 막힌 상자'로 비유하곤 한다. 우리가 바닥이 막힌 상자 위에 물건들을 하나씩 쌓아 올린다고 생각해보자. 이제 그 물건들을 다시 꺼낼 때에는 맨 위에 올라와있는 물건부터 역순으로 꺼내야 할 것이다. 바닥이 막혀있으니 맨 아래에서부터 꺼낼 수 없고, 중간에서 꺼내면 무너져 내리기 때문이다. 조금 전문적인 말을 통해 설명하자면, 스택은 LIFO(Last In First Out, 후입 선출) 구조를 가지고 있다. 즉, 나중에 들어온 데이터가 먼저 빠져나가는 자료구조다. 예시 위 그림은 스택 구조..
-
ArrayList와 LinkedListComputer Science/Data Structure 2022. 3. 20. 23:45
ArrayList ArrayList란? Java의 Collection Framework에서 가장 많이 사용되는 Collection Class 배열같이 인덱스를 통해 인자를 관리한다는 특징이 있지만 배열과는 다르게 크기가 동적으로 할당됨 기본 저장용량은 10이며, 10을 넘어가면 1.5배씩 증가 정확히 설명하자면, 기존 ArrayList의 크기가 동적으로 변하는 것이 아니라 기존 저장용량을 넘어서면 기존 ArrayList의 저장용량보다 1.5배 큰 ArrayList를 만들고, 이 리스트에 기존 ArrayList의 값들을 복사하는 것 값이 하나 삭제되면 해당 인덱스 뒤의 모든 인자가 한 칸씩 당겨지고, 값이 하나 추가되면 해당 인덱스 뒤의 모든 인자가 한 칸씩 밀림 Generic을 이용해 타입 안정성을 제공..
-
Array(배열)와 List(리스트)Computer Science/Data Structure 2022. 3. 19. 16:27
Array(배열) Array(배열)이란? 여러 데이터를 그룹으로 관리하기 위하여 사용하는 자료구조 데이터들은 메모리 상에 연속적(논리적인 저장 순서와 물리적 저장 순서가 같음)으로 배치됨 즉, 연속된 메모리 공간에 순서대로 저장된 데이터 그룹을 배열이라고 함 배열 내의 각 원소들은 유일무이한 고유의 인덱스 번호를 가지고 있음 -> 원소의 인덱스 번호를 통해 해당 원소에 접근할 수 있음 처음 배열을 생성할 때 배열의 크기를 정해줌(pre-allocation). 이 크기는 고정적이기 때문에 데이터를 몇 개를 집어넣느냐와 상관없이 처음 생성할 때 크기를 그대로 유지 Cache Hit Ratio가 높음 (※ Cache Hit Ratio: CPU가 요청한 데이터가 캐시 메모리에 있는 경우 캐시 적중(Cache H..