이번 시간에는 자료구조 트라이에 대해 알아보도록 하겠습니다. 1. 트라이(Trie)란? 효율적인 문자열 저장 및 탐색이 가능하도록 만든 자료구조 형태 중 하나입니다. 코딩을 하다 보면 수많은 문자열을 저장한 후에 어떤 문자열을 입력 받았을 때, 해당 문자열이 내가 저장한 구조에 포함된 문자열인지의 여부를 알아야 할 때가 있을 것입니다. 이때 사용하는 방식은 다음과 같은 것들이 있습니다. ① 단순 비교 전체 문자열을 맨 앞부터 끝까지 각 문자를 비교 하는 방식 ②이진 탐색(Binary Search) 전체 문자열을 사전 순으로 배열 저장 후, 중간 값과 비교하여 정렬을 진행하는 방식 ③ 트라이(Trie) 이번 시간에 배울 내용 K-진 트리 구조를 통해 문자열을 저장하는 방식 English Dictionary..

이번 시간에는 그래프에 대해 알아보도록 하겠습니다. 1. Graph - 그래프란? 그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다. 먼저 그래프와 트리의 차이점을 살펴보면 다음과 같습니다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류이고 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 무방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 모두 가능 순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 ..

이번 시간에는 Heap 자료구조와 우선순위 큐 (Priority Queue)에 대해서 알아봅시다. 1. 힙 - Heap Heap 자료구조에 대해서 배워 보도록 합시다. 시작하기 앞서 Computer Science(CS) 분야에서 힙이라는 것은 두 가지의 의미를 가지고 있습니다. 자료구조 힙(Heap) Java의 메모리 영역 이 두 가지는 같은 용어를 사용하지만 엄연히 다른 의미를 갖고 있기 때문에 구분하여 알아두어야 합니다. 그렇지만 자료구조 및 알고리즘 수업이기 때문에 여기서는 자료구조 힙에 대해 먼저 보도록 하겠습니다. (CS 카테고리 중 운영체제 수업에서 Java의 메모리 영역으로써의 힙 내용이 다뤄집니다.) 1-1. 자료구조 힙 힙(heap)은 이진 힙(binary heap)이라고도 하고, 최댓값..

이번 시간에는 트리 구조에 대해서 배워보도록 하겠습니다. 1. 트리(Tree)란? 트리란 노드들이 나무 가지처럼 연결된 비선형(non-linear), 계층적 자료구조로 위 그림처럼 나무를 거꾸로 뒤집어 놓은 것과 같은 모양이어서 트리(tree)라는 이름을 가지게 된 자료구조입니다. 개요 트리는 한 노드가 여러 노드를 가르킬 수 있는 비선형적 자료구조를 일컫는 말입니다. 앞서 배웠던 리스트(List), 스택(Stack), 큐(Queue)는 이전 데이터와 다음 데이터 간의 순서가 존재했습니다. 트리도 물론 내부적으로 순서 정보를 가지도록 구현할 수도 있지만 트리 구조자체의 특성상 순서는 그렇게 중요하지 않습니다. 그래서 트리는 뒤에서 배우게 될 그래프(Graph)의 일종이며 데이터 구조의 상하 개념 계층의 ..

이번 시간에는 해시에 대해 배워보겠습니다.(내용이 상당히 많으니 정말 알찬 포스팅이 될 것 입니다 ^.^) 해시 자체는 어려운 개념이 아니나 이를 구현할 때는 노드와 LinkedList를 이용하여 구현하기 때문에 이전 과정이 복습이 잘 된 상태여야 이해가 더 잘 될 것입니다. LinkedList를 참고하기 위해서는 아래 링크를 참조하세요. [CS 지식/자료구조와 알고리즘(Java)] - [자료구조] LinkedList(연결 리스트) 이론 및 구현 [자료구조] LinkedList(연결 리스트) 이론 및 구현 이번 포스팅은 지난 포스팅에 이어 ArrayList에서 했던 것과 마찬가지로 LinkedList에서의 데이터 삽입, 데이터 삭제, 리스트 검색 등의 기능에 대해서 다뤄보도록 하겠습니다. LinkedLi..

이번 시간에 배워 볼 내용은 Queue(큐)입니다. 1. 큐(Queue)란? queue는 지난시간(링크 참조)에 배운 스택과 달리 선입선출(First-In-First-Out-FIFO)의 구조를 가지고 있습니다. 즉, 가장 먼저 들어간 것이 가장 먼저 나오게 되는 구조인 것입니다. 선입선출(FIFO)의 예로는 순서가 보장된 처리를 가지고 있는 '사용자가 몰리는 서버'와 같은 경우가 있습니다. 대학생이 수강신청을 하러 인터넷에 들어간 경우나 내가 좋아하는 가수의 티켓팅을 하기 위해 인터넷에 들어갔을 때 대기 순서와 같은 것을 본 적이 있을 것입니다. (또한 편의점에서 일을 해 보신 분들도 자주 들어본 용어일 것 입니다.) 이러한 경우 가장 먼저 들어간 사람을 우선순위로 다음 페이지로 연결이 되기 때문에 FI..

이번 시간에는 Stack 자료구조에 대해서 배워 볼 것입니다. 1. 스택(Stack)이란? stack은 후입선출(Last-In-First-Out; LIFO)의 대표적인 선형 자료구조 중의 하나입니다. 후입선출이란 'Last-In-First-Out'이라는 뜻 그대로 '나중에 들어온 데이터가 가장 먼저 나간다' 의 의미를 가지고 있습니다. 그 예로 인터넷 브라우저에서 뒤로 가기 기능같은 경우 그 버튼을 눌렀을 때 가장 최근의 페이지가 나오는데 이 역시 가장나중에 들어간 페이지가 가장 먼저 나오는 것이기 때문에 스택 구조라고 할 수 있습니다. 또한, Ctrl + z 와 같은 실행 취소 기능역시 제일 나중에 했던 동작을 취소하는 것이므로 스택 구조라고 볼 수 있습니다. 위 그림은 스택의 구조를 시각화한 자료입니..

이번 시간에는 LinkedList의 종류 중에서 Double LinkedList에 대해서 알아 보겠습니다. 1. Doubly Linked List(이중 연결 리스트)란? 이전 내용에 있는 LinkedList는 앞에 'Single'이 생략 되어있는 셈이라 생각하면 됩니다. 그럼 무엇이 single이고 무엇이 double일까요? 위 그림은 Double LinkedList의 대략적인 구조를 나타낸 그림입니다. 아래 그림을 보면, LinkedList와는 다르게 한 노드에서 다른 노드를 가리키는 pointer가 양방향으로 있습니다. 즉, 다음 노드를 가리키는 next pointer 말고도 이전노드를 가리키는 prev pointer 하나가 더 추가 된 것입니다. 이것이 LinkedList와는 구분되는 Double ..