[Java] 비선형 자료구조 - 트리

트리 (Tree) Tree란? 트리는 영어 단어 그대로 가지가 뻗어 있는 모양으로 노드와 간선으로 구성된 그래프의 일종이다. 그래프와 다른 점은 하나의 노드에서 다른 노드로 이동하는 경로가 유일하다는 점이다. 이를 Acycle이라고 한다. 트리는 폴더 구조, 조직도, 가계도 등 계층적 구조를 나타날 때 사용 한다. 트리의 구조 트리 구조의 자료 값을 담고 있는 단위를 노드(Node)라고 한다. 그리고 노드 간의 연결선을 에지(Edge)라고 한다. 이렇게 연결된 두 노드 중 상위의 노드를 부모(Parent) 노드, 하위의 노드를 자식(Child) 노드라고 한다. 그리고 같은 부모를 가지는 노드를 형제(Sibling) 노드라고 한다. 자신을 포함한 자식 노드의 개수를 크기(Size)라고 하며, 각 노드가 지..

• format_list_bulleted 자료구조/비선형 자료구조
• · 2024. 3. 4.
• textsms

[Java]힙(Heap) 자료구조

힙(Heap)이란 ? 힙은 완전 이진트리 형태로 최대, 최소 값을 빠르게 찾아내는데 유용한 자료구조이다. 힙은 중복 값을 허용하며, 부모 - 자식 간 정렬은 보장하나 형제간의 정렬은 보장하지 않는다. (반 정렬 상태) 최소 힙( Min Heap) 최소 힙은 부모 노드의 Key가 자식 노드의 Key보다 작거나 같은 완전 이진트리이다. 최소 힙 - 삽입 트리의 가장 끝 위치에 데이터 삽입 부모 노드와 키 비교한 후 부모 보다 작을 경우 부모와 자리 교체 (반복) 최소 힙 - 삭제 최상위 노드 반환 및 삭제 가장 마지막 위치의 노드를 최상위 노드로 위치 시킴 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체 (반복) 최소 힙 - 구현 기본 구조 ArrayList heap; MinHeap() {..

• format_list_bulleted 자료구조/비선형 자료구조
• · 2023. 12. 17.
• textsms

[Java] 큐(Queue)의 개념과 구현

Queue란? 큐는 선형 자료구조 중 하나로 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(FIFO, First-In-First-Out) 형태의 자료구조이다. 큐에서 가장 먼저 들어온 데이터를 Front라고 하며 가장 먼저 나가게(삭제)된다. Front가 나가고 나면 그 다음 데이터가 새로운 Front가 된다. 큐에서 가장 마지막에 입력된 데이터를 Rear라고 한다. 새로운 데이터는 기존 Rear 다음에 삽입되고 그 데이터가 새로운 Rear가 된다. Queue Interface Java에서 큐는 인터페이스(Interface)로 제공되며 주로 큐 인터페이스(Queue Interface)를 구현(Implement)한 연결리스트(LinkedList) (Queue Interface 를 상속받은 Deque..

• format_list_bulleted 자료구조/선형 자료구조
• · 2023. 12. 15.
• textsms

[Java] 스택 (Stack)

스택 (Stack) 스택 (Stack)이란? 스택 (Stack) 은 ` (깔끔하게 정돈하여) 쌓다` 라는 뜻으로, 물건 등을 쌓아 올리듯이 데이터를 쌓아 올려가는 자료 구조라고 할 수 있다. 스택은 그림과 같이 나중에 넣은 데이터가 먼저 나오게 되는 후입선출 (LIFO, Last In First Out) 구조를 가지고 있다. Push와 Pop 스택에 데이터를 추가하는 동작을 Push, 스택에서 데이터를 꺼내는 동작을 Pop이라고 한다. 자바에서는 java.util.Stack 클래스를 통해 스택을 제공하고 있다. stack.pop()은 스택의 마지막 데이터를 꺼내고 그 데이터를 반환해주며, stack.peek()은 스택의 마지막 데이터를 꺼내지 않고, 반환만 해준다. 알고리즘 문제에서 스택의 제일 마지막 ..

• format_list_bulleted 자료구조/선형 자료구조
• · 2023. 12. 11.
• textsms