개발공부

[알고리즘] Priority Queues 우선순위 큐: 필수 기본 정리 - 구현, 활용, comparable, comparator

목차 우리는 이전 포스트 들에서 선입선출 FIFO 후입 선출 LIFO 와 같은 큐의 순서를 알아봤습니다. 새로 배우는 우선순위 큐도 이 큐들 중 한 종류입니다. 우선순위 큐(Priority Queue) 개념 일반적으로 쓰이는 queue에서는 선입선출(FIFO)과 다르게 특정 기준 순서로 아이템이 큐에서 빠지게 됩니다. 예를 들면 리스트에서 가장 큰 값 먼저 dequeue 될 수 있고 작은 값 먼저 dequeue 될 수 있습니다. 이러한 기준을 정하여 queue를 생성할 수 있는 것이 우선순위 큐의 특징입니다. 우선순위 큐는 두 가지 형태를 가지고 있을 수 있습니다. 1. Max-Priority : 가장 우선순위에있는 element는 가장 큰 값 2. Min-Priority : 가장 우선순위에있는 elem..

[알고리즘] Heap 힙 데이터구조 : 필수 기본정리 - Min Heap, Max Heap, 삽입, 제거, 탐색 구현

목차 힙(Heap) 개념 힙은 우선 우선순위의 개념을 대입한 자료구조입니다. 전포스트에서 다뤘던 Stack,Queue와 같이 자료가 들어오고 나가는 순서를 정할수있습니다. 우선순위개념과 Stack Queue에대하여 자세히 알고싶으시다면 아래 포스트를 참고해주세요. [알고리즘] Stack 스택: 기본정리 - pop, push, peek, count - Kotlin 목차 스택 자료구조 개념 스택은 아이템을 쌓아 올리는 구조입니다. 제거할 때도 가장 위에 있는 아이템부터 제거하게 되고 추가할 때도 위에서부터 추가합니다. 그래서 스택에는 2가지 동작이 underdog11.tistory.com [알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐)..

[알고리즘] Binary Search 이진 탐색 : 필수 기본 정리 - 장점, Kotlin 구현

목차 이진 탐색 Binary Search 이진 탐색은 가장 효율적인 탐색 알고리즘 중 하나입니다. Big O에서 O(log n)으로 나타냅니다. 균형 이진 탐색 트리(Balanced Binary Search Tree)에서 element를 찾는 것과 비슷한 구조를 가지고 있습니다. 만약 시간 복잡도와 이진 탐색 트리에 대하여 더 알고 싶으시다면 아래 링크를 확인해주세요. [알고리즘] Binary Tree 바이너리 트리: 기본정리 - 바이너리트리 구현, 중위순회, 전위순회, 후위순 목차 바이너리 트리 개념 바이너리 트리는 트리와 같지만 최대 2개의 자식만 가질 수 있는 트리구조입니다. 자식 두 개의 왼쪽을 LeftChild 오른쪽을 rightChild로 부릅니다. 바이너리 트리 구현하기 underdog11...

[알고리즘] Tries 트라이 자료구조 : 필수 기본 정리 - 구조, 장점, 삽입 Insert, 포함여부 contains, 제거 remove - Kotlin 구현

목차 Trie 자료 구조 개념 우리가 구글 엔진에서 방대한 자료 중 검색어를 찾을 때 위와 같이 뒤에 올 연관 검색을 찾아주거나, 사전에서 단어 검색을 할 때 자동완성시켜줄 때처럼 Trie는 문자열을 저장하기 위해 가장 효율적인 자료구조입니다. Trie 자료구조를 그림으로 나타내보겠습니다. springBoot, springCloud, springMvc sports라는 문자열들을 저장한다고 가정합시다. 그리고 springBoot를 검색할 때 node에 있는 character하나하나씩 접근하면서 문자열을 찾게 됩니다. 우리가 사전에서 단어를 찾을 때와 비슷한 메커니즘입니다. 한 글자씩 찾아가며 문자열에 도달합니다. Trie 자료 구조의 장점 words라는 Array에 몇 개의 단어가 있다고 가정해봅시다. c..