목록Study/Data Structure (2)
이지선의 블로그
[Data Structure] 비선형 구조 - 힙 (Heap), 우선순위 큐(Priority Queue)
01. 힙 (Heap)힙은 완전 이진 트리의 일종으로, 우선순위 큐를 구현하기 위해 사용되는 자료구조이다. 시간복잡도는 O(log N) 최대값 또는 최소값 일 경우 O(1) - 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 01-1. 힙의 특성힙은 각 노드가 하위 노드보다 큰(또는 작은) 우선순위를 가진다.최대 힙(Max Heap)에서는 부모 노드가 자식 노드보다 항상 크고, 최소 힙(Min Heap)에서는 부모 노드가 자식 노드보다 항상 작다. 01-2. 힙 구현 방법 왼쪽 자식 인덱스 = (부모 인덱스 *2) + 1오른쪽 자식 인덱스 = (부모 인덱스*2) + 2부모 인덱스 = (자식 인덱스-1) / 2 02...
[Data Structure] 선형 구조 - 스택(Stack)과 큐(Queue), 덱(Deque)
01. 스택 (Stack)스택은 후입선출(LIFO, Last In First Out)의 특성을 가진 자료구조이다. 시간 복잡도는 O(1) push : 스택의 맨 위에 요소를 추가pop : 스택의 맨 위 요소를 제거하고 그 값을 반환peek : 스택의 맨 위 요소를 조회 배열로 만드는 것이 유리하다.import java.util.Stack;Stack stack = new Stack();stack.push(1); // 스택에 1 추가stack.push(2); // 스택에 2 추가System.out.println(stack.peek()); // 스택의 맨 위 요소 조회: 2stack.pop(); // 스택의 맨 위 요소 제거System.out.println(stack.peek()); // 스택의 맨 위 요소 ..