AndroidTeacher

해시 테이블​ 해시 테이블이란 연관배열 구조를 이용하여 (Key, Value)로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있는 자료구조이다. 기본 연산으로는 탐색, 삽입, 삭제가 있다. TIP 연관배열 구조란 키(Key) 1개와 값(Value) 1개가 1:1로 연관되어 있는 자료구조이다. 해시 테이블 연산​ ① 삽입​ 해시 테이블에서 자료를 저장하기 위해서는 해시 함수(Hash Function)를 통하여 키(Key)를 -> 해시(Hash)로 변경해야 한다. 위 사진의 해시 함수는 input key를 7로 나눈 나머지이므로 첫 번째 데이터의 키는 76, 해시는 6이 된다. 미리 준비해놓은 0 ~ 6의 저장소 중에 맞는 해시값을 찾아 해당 값을 저장한다. 해시 함수로 해시를 얻어내는 과정에서..

레드-블랙 트리 (Red-black tree) 란 ?​ 레드-블랙 트리는 자가 균형 이진 탐색 트리의 한 종류이며, 앞서 살펴본 이진 탐색 트리가 탐색 시 최악의 경우 시간복잡도가 O(n)인 부분을 몇 가지 조건을 통해 균형 잡힌 트리로 만들어 최악의 경우에도 탐색 시 O(logn) 을 보장하는 자료 구조이다. 레드-블랙 트리의 조건​ 이진 탐색 트리가 가진 조건에서 다음 조건을 만족해야 레드-블랙 트리라고 할 수 있다. 모든 노드는 Red이거나 Black이다. 루트 노드는 Black이다. 모든 리프노드(단말노드)는 Black이다. 노드가 Red이면 그 자식은 Black이다. No Double Red => Red 노드가 연속으로 나올 수 없음 루트노드에서 모든 리프노드까지의 경로에서 만나는 Black노드..

1. B-Tree란?​ B-Tree는 자식 노드의 개수가 2개 이상인 트리를 말한다. 이진트리가 자식 노드가 최대 2개인 트리를 말하는 것인데, 이 이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree이다. 2. B-Tree의 구조​ 그림의 네모 칸 하나 하나를 '노드' 라고 하며, 가장 상단의 노드를 '루트 노드(Root Node)', 중간 노드를 '브랜치 노드(Branch Node)', 가장 하단의 노드를 '리프 노드(Leaf Node)' 라고 한다. 안의 구조를 자세히 살펴보면 다음과 같다. 위 그림에서 보듯이, 노드당 데이터를 2개 이상 가질 수 있으며 자식 노드를 자신의 데이터 수 이상으로 가질 수 있다. 즉, 노드의 데이터가 N개이면, 자식 수는 N+1개가 된다..

1. 이진탐색트리란?​ 이진탐색트리란 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진 탐색 연결 리스트 장점 탐색에 소요되는 시간복잡도가 O(logN) 로 빠르다 삽입과 삭제에 걸리는 시간 복잡도가 O(1)로 빠르다 단점 삽입과 삭제가 불가능하다 탐색의 시간 복잡도가 O(N) 이다 위와 같은 이진 탐색과 연결리스트의 장점을 고안하기 위해 만들어졌으며, 이진 탐색의 효율적인 탐색 능력을 유지하면서도 빈번한 자료 입력과 삭제가 가능하기 위해 사용된다. 2. 이진탐색트리 특징​ 이진탐색트리는 이진트리의 일종으로 다음과 같은 규칙으로 구성한다. 모든 노드는 유일한 키를 갖음. (중복된 노드 X) 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값..

힙이란?​ 힙(Heap)이란, 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조이다. 키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap)이라 하고, 키 값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다. 아래 그림은 최대 힙과 최소 힙의 예시이다. 힙의 연산​ 힙에는 새로운 원소를 추가하는 삽입 연산, 루트 노드에 있는 원소를 삭제하는 삭제 연산 두가지가 존재한다. 다만, 힙은 항상 부모노드를 최대 힙일 경우 최대, 최소 힙일 경우 최소로 유지해주어야 하는 특성이 있다. 최대 힙 : 부모노드의 키 값 >= 자식노드의 키 값 최소 힙 : 부모노드의 키 값

Stack의 정의​ Stack이란, Stack이란 단어의 의미처럼 쌓아 올린다는 뜻이다. 한쪽에서만 원소를 삽입하고 삭제가 가능한 자료구조이다. 한쪽에서만 원소를 쌓아 올리고 꺼내고 하기 때문에 LIFO(Last In First Out) 구조로 되어있다. Stack의 기술 내용​ Stack에는 두가지 중요한 기술인 Push와 Pop이 있다. 위 그림과 같이 입구와 출구가 동일한 바구니가 있다. Push를 하게 되면 바구니에 원소를 집어넣게 되며, 또 한번 Push를 하게 되면 첫 원소 위에 두번째 원소가 위치하게 된다. 여기서 첫번째 원소를 꺼내고 싶다면 Pop을 두번해야 한다. 결국 삽입을 할 때에도 맨 위(Top)에 삽입을 하게 되고 꺼낼때에도 맨 위에 있는 원소를 꺼내게 된다. 주로 문자열의 역순을..

트리(Tree) 란?​ 트리는 노드로 이루어진 자료 구조 트리는 하나의 루트 노드를 갖음 루트 노드는 0개 이상의 자식 노드를 갖고 있음. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있음. 노드와 노드는 서로를 연결하는 간선들로 구성. 트리에는 사이클(cycle)이 존재할 수 없음. 노드들은 특정 순서로 나열될 수도, 아닐 수도 있음. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있음. 각 노드는 어떤 자료형으로도 표현 가능함. 비선형 자료구조로 계층적 관계를 표현함. 그래프의 한 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류. 트리의 특징​ 그래프의 한 종..

안드로이드 개발 입문단계에서는, View( Activity, Fragment )에서 View의 동작과, 데이터 처리까지 모두 작성하는 방법으로 안드로이드 앱을 제작했을 것이다. 하지만 이렇게 작성하게 되면 코드 작성은 쉬울 수 있지만, 여러 사람들과 협업을 했을 때, 코드 가독성이나 관리, 로직 구현이 굉장히 까다로워진다. 또한 하나의 class에 모든 처리를 위한 수많은 코드들이 들어가게 되어 스파게티 코드로 변환될 가능성이 있다. 그리고 UI에서 모든 걸 처리하기 때문에 비즈니스 로직에 따른 UI의 변화들을 직접 개발자가 바꿔줘야 하는 까다로움이 존재한다. 이로 인해 테스트 코드의 작성이 어려워지게 되며 유지보수에 굉장히 큰 어려움이 따를 수 있다. 이러한 단점을 극복하고자 나온 패턴이 바로 MVP ..

오늘 안드로이드 코틀린의 코루틴에 대해 알아보고자 한다. Coroutine vs Thread를 통해 Coroutine을 사용하는 이유 알아보기 Coroutine Dispatcher Coroutine Context Coroutine Scope Coroutine Builder + Job suspend(일시 중단 함수) Coroutine 직접 사용해보기 Coroutine vs Thread Thread Task단위 => Thread 각 작업에 Thread를 할당 각 Thread는 자체 Stack 메모리를 가지며, JVM Stack 영역 차지 Context Switching Blocking (Thread1이 Thread2의 결과가 나올 때 까지 기다려야 한다면 Thread1은 Blocking되어 사용하지 못함) ..

ListAdapter + DiffUtil 사용 이유 기존에는 RecyclerView의 Adapter는 RecyclerView.Adapter를 이용하여 구성하였다. 이는 RecyclerView에서 데이터가 변경되었을 경우 notifyDatasetChanged()를 사용하게 되는데 이 경우, 리스트 내의 데이터를 모두 바꾸게 된다. 따라서, 데이터가 매우 많을 경우 시간 지연이 발생하게 된다. 이러한 불편한 점을 해소하기 위해 ListAdapter + DiffUtil을 활용하게 된다. DiffUtil은 현재 데이터 리스트와 교체할 데이터 리스트를 비교하여 변경이 필요한 부분만을 뽑아내어 변경을 하기 때문에 notifyDatasetChanged() 보다 훨씬 빠른 시간내에 리스트를 변경할 수 있게 되기 때문이..