Kotlin/Kotlin 자료구조
[Kotlin] PriorityQueue란 무엇인가? Priority Queue의 삽입, 삭제, 탐색을 위한 시간 복잡도 알아보기
PriorityQueue란? PriorityQueue는 원소들을 우선순위에 따라 저장하고 관리하는 자료구조이다. 각각의 원소는 우선순위의 순서대로 저장된다. PriorityQueue는 일반적으로 min-heap 이나 max-heap을 사용해 구현된다. Heap은 트리 형태의 우선순위대로 순서가 나타내지는 자료 구조로. min-heap 방식으로 구현되면 우선순위가 낮은 요소가 맨 앞에 오고, 우선순위가 높은 요소가 맨 뒤에 오게 되며, max-heap 방식을 사용해 구현되면, 우선순위가 높은 요소가 맨 앞으로 오고 우선순위가 낮은 요소가 맨 뒤에 위치한다. Kotlin과 Java의 PriorityQueue는 min-heap 방식으로 구현되어 우선순위가 낮은 요소가 가장 앞쪽에 온다. 예를 들어 아래와 같이..
[Kotlin] Binary Search Tree Kotlin으로 구현해보기 : insert, search
Binary Search Tree 구현하기 이전 글에서 Binary Search Tree가 무엇인지에 대해 살펴보았다. 이번 글에서는 이를 직접 구현해보려고 한다. 구현할 Binary Search Tree의 요구사항은 다음과 같다. 중복을 허용하지 않는다. 이미 있는 값의 추가 요청이 들어오면 아무런 동작을 하지 않고 반환한다. 노드는 임의로 다음과 같이 구성한다. data class Node(var value: Int) { var left: Node? = null var right: Node? = null } insert 메서드 구현하기 새로운 노드를 추가할 때는 다음과 같은 순서를 따른다. 추가 요청이 들어온 노드를 생성한다.(새로운 노드) 루트 노드가 null인지 확인 후 null이라면 새로운 노드..
[Kotlin] Binary Search Tree란 무엇인가? Binary Search Tree의 한계와 시간 복잡도 알아보기
Binary Search Tree란? Binary Search Tree는 Binary Tree의 한 종류로써, 데이터를 저장하고 탐색하기 위한 자료 구조이다. Binary Search Tree는 각 노드가 특정한 값을 가지고 있고, 각 노드의 왼쪽 서브트리에는 노드의 값보다 더 작은 값의 노드들이, 오른쪽 서브트리에는 더 큰 값의 노드들이 위치하도록 만들어진다. 이러한 특성으로 인해 Binary Search Tree는 아래와 같은 특징을 가진다. 값들이 정렬되어 있는 Binary Tree 구조이다 : 특정 노드를 기준으로 해당 노드 왼쪽에 있는 노드들은 모두 해당 노드의 값보다 작은 값을 가지며, 해당 노드 오른쪽에 있는 노드들은 해당 노드의 값보다 큰 값을 가진다. 위와 같이 정렬되어 있어, Binar..
[Kotlin] Stack 다루는 방법 한 번에 정리하기 : Kotlin의 Stack의 한계와 ArrayDeque를 사용한 해결 방안
Stack 이란 무엇인가? Stack은 마지막에 들어온 값이 제일 먼저 나가는(LIFO) 특징을 가진 자료구조로, 값을 추가하고 빼내는데 O(1)의 시간 복잡도로 가능해 다양한 곳에 활용될 수 있는 자료 구조이다. *예를 들어 안드로이드에서는 화면(Fragment) 변경 시 이전 화면의 목록을 관리하는데 Stack 자료 구조를 사용하고 있다. 한 번 Stack이 어떻게 동작하는지 그림으로 살펴보자. Stack은 값을 여러개 담을 수 있는 하나의 Container을 가지고 있으며, 값을 집어넣으면 아래와 같이 순서대로 Container에 쌓인다. 예를 들어 Element1, Element2를 Stack에 순서대로 쌓으면 아래와 같은 형태가 된다. 값을 빼낼 때는 무조건 위에 있는 값부터 빼내진다. 즉, S..
[Kotlin] Set, MutableSet 은 어떻게 원소에 빠르게 접근할 수 있을까? : Set이 평균적 O(1)의 속도로 원소에 접근하는 방법
Set, MutableSet 은 어떻게 원소에 빠르게 접근할 수 있을까? Kotlin의 Set은 원소에 접근하는데 걸리는 시간이 평균적으로 O(1)이고 중복을 체크하는데 걸리는 시간도 O(1)이다. 이 때문에 많은 Set을 사용하면 매우 효율적으로 원소에 접근할 수 있다. 이번 글에서는 그 이유를 알아보고자 한다. Kotlin의 Set, MutableSet에서 사용하는 자료 구조 Kotlin의 Set, MutableSet은 모두 인스턴스를 만들기 위해 LinkedHashSet을 사용한다. Set의 내부 구현 살펴보기 Set의 모든 생성자를 보는데는 너무 시간이 많이 걸리므로 Set을 만드는 대표적인 함수인 setOf 함수만 보도록 하자. Kotlin에서 setOf를 사용해 Set 생성하는 부분을 보면 ..