AndroidTeacher

트라이란?​ 문자열 집합에서 어느 한 개의 문자열을 탐색하는 알고리즘은 무엇이 있을까? 최대 길이가 m인 문자열 n개의 집합이 있다고 가정해 보자. 가장 간단하지만 시간복잡도가 높은 방식은 무작정 순회를 돌며 찾는 방식인 brute force이다. 최대 길이가 m인 문자열 n개의 집합에서, 원하는 문자열이 있는지 찾는다면 비교횟수는 O(mn)이 된다. 이를 좀더 개선하는 방식으로 이진 탐색을 활용하면 좀더 낮은 시간복잡도를 갖게 된다. 이진 탐색을 사용하면 O(mlogn)으로 단축 시킬 수 있지만, 정렬 과정 자체에 O(nmlogn)의 시간이 걸려서 이 또한 비효율적인 방식이라고 볼 수 있다. 이를 모두 개선하기 위한 문자열 집합 검색법이 바로 트라이(Trie)라는 자료구조이다. 이를 트라이 알고리즘이 ..

해시 테이블​ 해시 테이블이란 연관배열 구조를 이용하여 (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, 방향성이 있는 비순환 그래프)의 한 종류. 트리의 특징​ 그래프의 한 종..

그래프란? 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수 있다. 이러한 면에서 트리는 그래프의 일종인 셈이다. 하지만 그래프는 트리와는 달리 정점마다 간선이 있을 수도 있고 없을 수도 있으며, 루트노드와 부모와 자식이라는 개념이 존재하지 않는다. 그래프와 트리의 차이점에 대해서는 아래의 표로 좀 더 자세하게 설명하겠다. 그래프와 트리의 차이 그래프와 관련된 용어 정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3) 간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다. 인접 정점(adjacent Vertex) : 간선에 의해 직접..

배열 vs 연결리스트 배열 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다. 메모리상에서 연속적으로 저장되어 있는 특징을 갖기때문에, index를 통한 접근이 용이하다. 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다. 시간복잡도 탐색: O(1) 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n) 삽입 및 삭제: 배열의 처음 또는 중간에 삽입 및 삭제: O(n) 삽입 지점 이후의 데이터를 옮겨야 하기 때문이다. 배열의 끝에 삽입 및 삭제: O(1) 연결리스트 연결리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다. 각 노드는 데이터와 다음..