menuhwang

힙(Heap) 특징 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 최댓값이나 최솟값을 빠르게 찾아낼 수 있는 자료구조 반정렬 상태 힙 트리에서는 중복된 값을 허용. 구조 종류 최소 힙 부모 노드의 값이 자식 노드의 값보다 작거나 같은 이진트리. 최대 힙 부모 노드의 값이 자식 노드의 값보다 크거나 같은 이진트리. 동작 원리 최소 힙을 예시로 설명합니다. 노드 추가 O(logN) 1. 가장 마지막 위치에 노드를 추가 2. 부모 노드와 비교하여 작은 노드가 상위 레벨에 있도록 swap! (완전한 구조가 될 때까지 반복) poll 최솟값 추출 (root 노드 추출) O(logN) 1. 루트 노드 제거 2. 비어있는 루트 노드에 마지막 노드 이동 3. 자식 노드 중 작은 노드와 swap (완전..

스택 특징 후입선출 Last in First out [LIFO] 마지막에 들어온 것이 먼저 나간다. 티슈, 프링글스 [JVM 함수 호출 스택, Stack Overflow 에러] 에서의 스택 선언(자바) public class StackPrac { public static void main(String[] args) { Stack stack new Stack(); } } 주요 동작 push 가장 마지막 위치에 값을 넣는다. public class StackPrac { public static void main(String[] args) { Stack stack new Stack(); stack.push(1); } } pop 가장 마지막의 값을 제거하고 반환한다. public class StackPrac {..

배열과 리스트 개요 처음으로 공부한 자료구조는 배열과 리스트다. 자료구조 공부는 처음이라 어떻게 공부하면 좋을지 어떤것을 공부하면 좋은지 고민해보았다. 각 자료구조들의 특징, 동작원리 등을 알아보고 구현해보는 방향으로 공부를 진행했다. 배열과 리스트는 선형적으로 데이터를 저장하는 자료구조이다. 비슷한 두 자료구조 각각의 특징과 동작원리를 알아보고 차이점을 찾아보자. 배열 용어 인덱스 (index) : 배열에 담긴 요소, 위치에 접근하기 위한 키 요소(element) : 배열에 담긴 단위 데이터 특징 순서 보장, 중복 가능 배열은 메모리 공간을 예약/할당하기 위해 길이를 미리 알려줘야만 한다. 크기 변경에 유연하지 못 하다. Random Access 선언 public class DataStructure {..