힙(heap)

힙(heap) 힙은 일종의 완전 이진트리(complete binary tree)로 구현되며, 최대값 혹은 최소값을 빠르게 찾아내는 자료구조이다. 최대값을 찾는 경우에는 최대 힙(max heap), 최소값을 찾는 경우에는 최소 힙(min heap) 이라고 한다. 이진트리, 완전 이진트리, 포화 이진트리 이진트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다. 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워져 있는 상태를 말한다. 포화 이진트리는 마지막 자식 레벨도 꽉 채워진 상태를 말함. 힙에서는 각 노드가 특정 조건을 만족해야 한다. 최대 힙의 경우, 모든 노드는 그 자식 노드들보다 큰 값을 갖는다. 최소 힙의 경우, 모든 노드는 그 ..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 19.
• textsms

연결리스트(LinkedList)

연결리스트(LinkedList) LinkedList는 자바에서 제공하는 자료구조 중 하나로, 리스트를 구현하는데 사용된다. LinkedList는 노드(Node)들이 링크로 연결되어 있는 자료구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(주소)로 이루어져 있다. 첫 번째 노드를 head(머리)라고 하고, 마지막 노드는 tail(꼬리)라고 한다. 새로운 노드가 추가되면, 추가된 노드의 포인터가 다음 노드를 가리키도록 설정되고, 이전 노드의 포인터는 새로운 노드를 가리키도록 변경된다. 노드가 삭제가 되면, 삭제 되는 노드의 이전 노드의 포인터를 삭제 하고 삭제 대상 노드의 다음 노드로 포인트를 지정 후 삭제된다. 삭제는 GC(가비지 컬렉터)가 참조되지 않는 데이터에 관해서 알아서 삭제 해준다. (..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 17.
• textsms

해시맵(HashMap, HashTable)

해시 맵(Hash Map, Hash Table) 해시맵은 키(Key)와 값(Value)이 한쌍으로 이루어진 데이터를 저장하고, 키를 이용하여 값을 검색할 수 있다. 내부적으로 배열을 이용하여 구현되며, 각 키는 해시 함수를 이용하여 배열의 인덱스로 변환되어 저장이 된다. 이 때, 해시 함수는 키의 일부를 이용하여 인덱스로 변환하는데, 이를 해싱(Hashing) 이라고 한다. 해시 함수를 통해 구한 인덱스에 해당하는 배열 위치에 데이터를 저장하면, 나중에 같은 키를 이용하여 검색할 때도 해시 함수를 통해 인덱스를 구한 후 해당 위치의 값을 바로 찾을 수 있다. 이 때 검색 시간 복잡도는 O(1)이기 때문에 매우 빠른 검색 속도를 보장하고 있다. 해시 맵(Hash Map)과 해시 테이블(Hash Table)..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 16.
• textsms

배열(Array)

배열(Array) 배열은 기차와 같은 자료구조이다. 데이터를 연속적으로 저장을 하면서 많은 데이터들을 다룰 때사용하는 자료구조로 제일 많이 사용하는 자료구조라고 할 수 있다. 배열을 공부하게 되면 먼저 사이즈(size)와 인덱스(index)에 대해서 알아야 한다. 사이즈 라는 것은 배열의 크기를 선언할 때 사용하는 용어이다. 그리고 인덱스는 생성된 배열에서 원하는 값이 존재하는 위치라고 보면 되는데, 안타깝게도 이 둘의 값은 같지가 않다라는게 함정이다. 사이즈와 인덱스의 값 사이즈가 5인 배열을 만들었다면 인덱스는 0~4까지 존재한다. 즉 인덱스는 사이즈 - 1 까지의 값을 가진다. 만약 사용자가 사이즈가 5인 배열을 만들게 된다면 인덱스는 0부터 시작해서 4에서 끝나는 배열을 만들어 준다. 그렇기 때문..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 15.
• textsms

큐(Queue) 관련 문제

보호되어 있는 글입니다.

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 14.

큐(Queue)

큐(Queue) 큐도 스택과 같이 기본적으로 알아둬야 하는 자료구조중 하나이다. 해당 자료구조는 선형 구조와 원형 구조 두가지가 있으며, 상황에 맞게 사용하면 된다. 큐는 선입선출 (First In First Out) 자료구조이다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조를 이용하고 있다. 해당 자료구조는 프린터 출력 대기열, BFS(Breath - First Search) 등에 사용이 된다. BFS(Breath - First Search) 가장 얕은 노드부터 검색을 하면서 깊은 노드까지 탐색하는 방식. Tree 구조에서 사용하는 검색 방식 큐 용어설명 Front : 큐에서 데이터를 꺼내면 제일 먼저 나오는 부분. Rear : 큐에서 데이터가 추가되는 부분. Enqueue : 큐에 데이터를 삽입. D..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 14.
• textsms