kimgusxo 님의 블로그

1. 힙(Heap)이란?- 힙은 완전 이진 트리 형태로 구성되는 자료구조로 각 노드가 특정 순서(우선순위)를 만족하도록 구성된다.- 부모 노드의 값이 자식 노드의 값보다 작거나 같아 루트 노드에 최솟값이 있는 최소 힙(Min Heap)과 부모 노드의 값이 자식 노드의 값보다 크거나 같아 루트 노드에 최댓값이 있는 최대 힙(Max Heap)으로 구성된다.- 우선순위 큐의 기본 구현체로 사용되며 삽입과 삭제 연산이 O(logN)의 복잡도를 가지며 힙 정렬과 다익스트라 알고리즘에 활용된다. 2. 자바를 활용한 힙 구현- 배열 기반의 최대 힙을 구현한 예제이다.public class MaxHeap { private int[] heap; public int size; private int capa..

1. 덱(Deque)이란?- 덱은 Double-Ended Queue로 큐와 유사한 형태지만 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.- 앞쪽과 뒤쪽 어느 쪽에서도 데이터를 추가하거나 제거할 수 있어 상황에 따라 스택과 큐로 활용가능하다.- 슬라이딩 윈도우, 브라우저 히스토리 등의 알고리즘에서 활용된다. 2. 주요 메소드- addFirst(E element): 맨 앞에 요소를 삽입한다.- addLast(E element): 맨 뒤에 요소를 삽입한다.Deque deque = new ArrayDeque();deque.addFirst("Apple"); // 맨 앞에 "Apple" 추가deque.addLast("Banana"); // 맨 뒤에 "Banana" 추가 - removeFirst(): 맨 앞의..

1. 큐(Queue)란?- 큐는 데이터를 순서대로 저장하는 자료구조로, 먼저 추가된 데이터가 먼저 제거되는 선입선출(FIFO: First In First Out) 방식을 따른다.- 큐는 주로 작업 스케줄링, 프로세스 관리, BFS 등의 알고리즘에 활용된다.- 자바에서는 Queue 인터페이스를 통해 큐를 다루며, 구현체로는 LinkedList와 ArrayDeque가 있다. 2. 주요 메소드- offer(E element): 큐의 맨 뒤에 요소를 추가한다.Queue queue = new LinkedList();queue.offer("Apple"); // 큐의 맨 뒤에 "Apple" 추가 - poll(): 큐의 맨 앞에 있는 요소를 제거한다.Queue queue = new LinkedList();queue.o..

1. 스택(Stack)이란?- 스택은 데이터를 저장하는 자료구조 중 하나로 마지막에 추가된 데이터가 가장 먼저 꺼내지는 후입선출(LIFO: Last In First Out) 방식을 사용한다.- 주로 괄호검사, 후위표기식, 재귀, 백트래킹 등의 알고리즘에 활용된다.- 자바에서는 Vector를 상속받아 구현되어 있으므로 동기화 등에서 불필요한 오버헤드가 발생할 수 있어 Deque 인터페이스를 사용하는 ArrayDeque를 스택처럼 사용할 수도 있다. 2. 주요 메소드- push(E item): 스택의 가장 위에 요소를 추가한다.Stack stack = new Stack();stack.push("Apple"); // 스택에 "Apple" 추가 - pop(): 스택의 가장 위에 있는 요소를 제거한다.Stack ..