케네스로그

힙(heap)은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)입니다. Heap의 특성 트리에서 사용되었던 노드가 아닌, Array를 활용하여 데이터를 관리합니다. 노드를 삽입하면 배열(트리)의 가장 마지막에 삽입합니다. Top에 위치한 최대값/최솟값을 O(1)의 복잡도로 리턴합니다. 오직 Parent, Child의 비교 규칙만 준수합니다. 힙과 이진탐색트리의 비교 이진탐색트리는 탐색을 위한 자료구조이며, Heap은 최대/최소값을 탐색하기 위한 자료구조 이전에 이진탐색트리(Binary Search Tree)에서는 부모와 자식간의 관계를 유지하는 것이 트리 형성 규칙이었습니다. 힙에서는 기본적으로 부모가 자식보다 크기만 하면 트리를 유지할 수 있..

트리는 Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 자료구조를 말합니다. 탐색에서 주로 사용됩니다. Binary Tree: 한 노드가 최대로 가질 수 있는 자식 노드가 2개인 트리 Binary Search Tree: Binary Tree 중 왼쪽 자식 노드가 부모노드보다 작은 값, 오른쪽 자식 노드가 부모노드보다 큰 값을 가지는 트리 Terminology 용어정리 노드(Node): 데이터를 저장하는 기본 단위. 연결된 다른 Branch에 대한 정보 + 데이터로 구성됨. 루트 노드(Root node): 트리 최상단 노드 레벨, 층 (Level): 최상위 노드를 level 0, 하위로 연결된 branch의 깊이를 표현함 부모 노드(parent node): 특정 노드의 상위에 연결된 노드 ..

Hash는 키(key)와 값(value)을 쌍으로 저장되는 자료구조를 말합니다. 배열에는 여러 키(Key)들이 저장되며, 해쉬 함수를 통해 해당되는 값을 가져옵니다. 키(Key)는 중복되지 않는 유니크한 값이어야하며, 값(value)은 중복이 가능합니다. 해시 테이블에서 데이터는 유니크한 인덱스 값에 따라 배열의 형태로 저장되빈다. 해시 함수는 키값에 대응되는 해시테이블의 인덱스를 연산하는 함수를 말합니다. 사용자는 키값을 넣어서 해시 테이블에 저장된 데이터의 위치를 받아 저장된 데이터에 접근할 수 있게 됩니다. Terminology (+비유) Hash table - 주택단지 Bucket - 아파트 Entry - 호 해쉬함수 : 임의 데이터를 고정된 길이의 값으로 리턴해주는 함수 해쉬, 해쉬 값, 해쉬 ..

이전에 정적배열 Array와 동적배열 ArrayList에 대해 알아보았습니다. 이번에는 또 다른 동적배열인 LinkedList에 대해 알아보겠습니다. LinkedList 링크드리스트 LinkedList는 Node를 기반으로 구성된 자료구조를 말하며, ArrayList와 마찬가지로 List클래스를 기반으로 합니다. Node는 Data를 담을 수 있는 변수와 다른 Node를 참조하는 2개의 변수로 이루어져있습니다. LinkedList는 Node의 구성에 따라 싱글 링크드리스트(Single-LinkedList), 더블 링크드리스트(Double-LinkedList)로 구분할 수 있습니다. Single Linked List Double Linked List Single Linked List public class..

이전에 자주 사용되는 Queue(큐)에 이어 Stack(스택)에 대해 알아보겠습니다. Stack 스택 Stack(스택)은 순서를 따르는 자료구조를 말합니다. 이 자료구조에서는 위, 아래가 존재하며 후입선출(Last-in-First-out)방식을 따릅니다. 먼저 들어온 데이터가 아래에 쌓이며, 나중에 들어온 데이터가 먼저 나오게 됩니다. 동전을 쌓고, 위에서 하나씩 가져가는 방식과 같습니다. 자바 메소드 메소드 리턴 값 설명 push(E item) E 주어진 객체를 스택에 삽입한다. peak() E top에 위치한 객체를 가져온다. pop() E top에 위치한 객체를 가져오고, 해당 객체는 스택에서 제거한다. Java Stack 구현 public class MyStack { private ArrayLis..

Queue 큐 Queue(큐)는 순서를 따르는 자료구조를 말합니다. 이 자료구조에서는 앞(front)과 뒤(back)가 존재하며, 먼저 들어온 데이터가 먼저 빠져 나가는 선입선출(First-in-First-out)의 규칙을 따릅니다. 은행에서 사람들이 줄을 서서 대기하다가 먼저 온 순서대로 업무를 보는 것과 같습니다. 먼저 온 사람이 먼저 서비스를 받는 것(FIFO)이죠. 자바 메소드 Queue는 인터페이스이며, 이를 구현한 클래스는 LinkedListd입니다. 따라서, Queue를 사용하기 위해 LinkedList 객체를 Queue인터페이스 타입으로 변환합니다. Queue queue = new LinkedList(); Queue q_str = new LinkedList(); q_str.offer("H"..

이전에 정적배열 Array에 대해 포스팅을 했었습니다. 이때, 정적배열의 단점은 최초에 선언한 사이즈를 나중에 변경이 불가능하다는 것이었죠. 이를 기억하면서 동적 배열을 알아보도록 하겠습니다. 동적배열 Dynamic Array 동적배열은 정적배열과 달리 배열의 크기가 가변적입니다. 다시 말해, 공간이 더 필요하면 늘릴 수 있다는 겁니다. 크기가 가변적인 동적배열은 여러 종류가 존재하지만, 대표적으로 ArrayList와 LinkedList가 존재합니다. ArrayList ArrayList는 배열을 동적으로 변화시키는 자료구조로써, List 인터페이스를 구현한 클래스입니다. ArrayList의 선언과 사용 ArrayList arr = new ArrayList(); ArrayList를 사용하기 위해 Array..

배열이란 자료구조는 데이터를 효율적을 관리하기 위해 고안된 저장 및 관리 방식입니다. 자료구조 중 하나인 배열은 동일한 타입의 데이터를 연속적으로 나열하고, 데이터의 순서에 따른 번호(인덱스)를 통해 데이터를 제어합니다. 배열의 특성은 다음과 같습니다. 순서가 존재하며, 색인(index)를 통해 데이터에 접근할 수 있다. 같은 자료형의 데이터가 연속적으로 저장된다. 처음 배열이 선언될 때 정해진 크기를 변경할 수 없다. 예시 종이책(데이터)이라는 같은 물질적 형태의 물건들를 효율적으로 적재하기 위한 틀을 책장(배열)이라고 합니다. 처음 가구를 만들때 정해진 크기(배열의 크기)는 이후에 수정할 수 없죠. 학생들의 이름 순으로 정리된 출석부도 배열이라고 할 수 있습니다. 출석부엔 학생번호(index)가 순서..