트리란? 그래프의 한 종류이다. 트리는 노드로 이루어진 자료 구조이며 다음과 같은 특성을 가지고 있다. 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 가지고 있으며 그 자식들도 모두 마찬가지이다. 노드들과 노드들을 연결하는 엣지들로 구성되어 있으며 이 연결된 엣지들은 절대로 사이클이 존재하지 않는다. 사이클이 존재하지 않기 때문에 간선수는 무조건 노드의 수 - 1 을 만족한다. 루트 노드를 제외한 모든 노드들은 단 하나의 부모노드를 가진다. 루트에서 어떤 노드로 가는 경로는 Unique하다. 트리와 관련된 용어 depth : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 엣지의 수를 말한다. height : 루트노드에서 잎새노드에 이르는 가장 긴 경로의 엣지 수를 의미한다. ..

우선순위 큐란? 우선순위의 개념을 큐에 도입한 자료 구조 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다. 힙이란? 완전이진트리 구조 최댓값과 최솟값을 뽑아낼 때 사용하기 좋은 자료구조이다. 힙은 완전히 정렬된 상태를 유지하는 것이 아닌 Level에 따른 정렬만 이루어져 느슨한 정렬상태를 유지한다. (Max Heap인 경우 부모가 자식보다 큰 값을 가지고 있고, Min Heap인 경우 부모가 자식보다 작은 값을 가지고 있어야 함) 힙의 종류 Max Heap 루트 노드에는 항상 가장 큰 값이 위치하고 있으며, 부모 노드가 자식 노드들보다 무조건 값이 커야한다. M..

연결 리스트란? 배열과 다르게 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조이며, 각 노드는 포인터를 이용해 서로를 연결하여 접근한다. 연결리스트 특징 장점 배열과 다르게 요소의 수만큼 메모리를 할당받을 필요가 없다. 배열과 다르게 공간을 추가로 할당받거나 나머지 데이터들의 위치를 이동시킬 필요가 없어서 삽입 및 삭제가 용이하다. 단점 배열과 다르게 특정 인덱스의 위치에 O(1)에 접근하지 못하고 앞에서부터 순차적으로 요소를 탐색해야한다. 각 노드가 데이터만 가지고 있는 것이 아닌, 포인터 변수의 공간도 추가적으로 필요하다. 코드로 보는 연결 리스트 노드 구현 class Node { private Node left; private Node right; private final int data; ..

Stack이란? LIFO(Last in First Out, 후입 선출), 입력과 출력이 한곳으로 제한되는 자료구조 Stack 예시 일반적인 함수의 콜스택, 스택이 넘치게 되면 StackOverFlow가 발생한다. 문자열 역순 출력, 연산자 후위표기법과 같은 상황에서 사용한다. 코드로 이해하는 Stack class Stack { List list = new ArrayList(); private final int STACK_MAX_SIZE; private int top = 0; public Stack(int STACK_MAX_SIZE) { this.STACK_MAX_SIZE = STACK_MAX_SIZE; } void push(int data) { if(isFull()) return ; list.add(to..