자료구조6 [자료구조] 트리 (Tree) 목차 트리(Tree)의 개념 트리는 노드와 간선으로 이루어진 계층적 관계를 표현하는 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 다음과 같은 특징들이 있다. 1. 트리는 하나의 루트 노드를 갖는다. 2. 루트 노드는 0개 이상의 자식 노드를 갖는다. 3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 4. 트리는 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. 5. N개의 노드를 갖는 트리는 항상 N - 1개의 간선을 갖는다. 6. 모든 자식 노드는 한 개의 부모 노드만을 갖는다. 7. 모든 노드는 서로 연결되어 있다. 8. 임의의 노드에서 다른 노드로 가는 경로(path)는 단 1개만 존재한다 추가로, 트리에는 사이클(Cycle)이 존재할 수.. 2022. 8. 3. [자료구조] 해시맵 (HashMap) 목차 HashMap 이란? 우선 Map은 키와 값으로 구성된 Entry 객체를 저장하는 구조를 가지고 있는 자료구조이다. 영어 사전을 예로 들어보겠다. person은 사람, baseball은 야구란 뜻을 가지고 있다. 따라서 맵에는 다음과 같이 저장되어 있을 수 있다. 키 값 "person" 사람 "baseball" 야구 Map은 리스트나 배열처럼 순차적으로 해당 요소의 값을 구하지 않고 키를 통해 값을 얻는다. 이게 Map의 가장 큰 특징이기도 하다. 추가로 키는 중복이 불가능하고 동일한 키 값으로 값을 넣을 시 최근에 넣은 값이 적용된다. 주어진 예로 보면 baseball의 뜻을 찾을 때, 사전의 있는 내용들을 순차적으로 검색해서 찾는 게 아닌 baseball이라는 단어가 있는 곳만 찾는다는 것이다... 2022. 4. 26. [자료구조] 덱 (Deque) 목차 덱(Deque)의 개념 덱 (Deque)은 Double-ended queue를 줄인 것으로, 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산을 모두 지원한다. 즉, 앞쪽 front와 뒤쪽 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 따라서 스택과 큐의 특성을 모두 갖는 자료구조이다. 덱이 수용할 수 있는 데이터의 크기를 넘어가는 삽입 연산을 수행할 때는 오버플로우가 (Overflow) 발생한다. 그리고 비어 있는 덱에서 삭제 연산을 수행하면 언더플로우 (Underflow)가 발생한다. 덱의 핵심 기능은 앞으로 데이터 삽입, 앞으로 데이터 제거, 뒤로 데이터 삽입, 뒤로 데이터 제거이다. 밑에서 덱의 메서드들과 사용법을 알아보겠다. 덱 (Deque) 기능 & 사용법 덱 (Deque.. 2022. 3. 17. [자료구조] 큐(Queue) 목차 큐(Queue)의 개념 큐는 FIFO 선입선출(First In First Out)의 구조를 가진다. 즉, 큐에서는 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. 한 예는 은행에 번호표가 있다. 은행에서 번호표를 먼저 뽑은 사람이 서비스를 먼저 받는다. 이러한 은행의 번호표의 체계가 큐(Queue)이다. 큐는 추가로 그래프의 넓이 우선 탐색(BFS)에서 사용된다. Enqueue : 큐 맨 뒤에 데이터 추가 Dequeue : 큐 맨 앞쪽의 데이터 삭제 위의 그림에 나온 것처럼 큐는 앞뒤가 다른 역할을 수행한다. 큐의 앞부분은 front는 삭제 연산만 수행하고 큐의 뒷부분은 rear는 삽입 연산만 수행한다. 보통 컴퓨터 버퍼에서 주로 사용되고, 여러 개가 한꺼번에 입력이 들어올 때 대기열을 만들어 순.. 2022. 3. 15. 이전 1 2 다음 반응형
