CS/자료구조 썸네일형 리스트형 [자료구조] 트라이 (Trie) 트라이란? 문자열 집합에서 어느 한 개의 문자열을 탐색하는 알고리즘은 무엇이 있을까? 최대 길이가 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노드.. 더보기 [자료구조] B-Tree & B+Tree 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) 에 대하여 힙이란? 힙(Heap)이란, 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조이다. 키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap)이라 하고, 키 값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다. 아래 그림은 최대 힙과 최소 힙의 예시이다. 힙의 연산 힙에는 새로운 원소를 추가하는 삽입 연산, 루트 노드에 있는 원소를 삭제하는 삭제 연산 두가지가 존재한다. 다만, 힙은 항상 부모노드를 최대 힙일 경우 최대, 최소 힙일 경우 최소로 유지해주어야 하는 특성이 있다. 최대 힙 : 부모노드의 키 값 >= 자식노드의 키 값 최소 힙 : 부모노드의 키 값 더보기 [자료구조] 스택(Stack), 큐(Queue) Stack의 정의 Stack이란, Stack이란 단어의 의미처럼 쌓아 올린다는 뜻이다. 한쪽에서만 원소를 삽입하고 삭제가 가능한 자료구조이다. 한쪽에서만 원소를 쌓아 올리고 꺼내고 하기 때문에 LIFO(Last In First Out) 구조로 되어있다. Stack의 기술 내용 Stack에는 두가지 중요한 기술인 Push와 Pop이 있다. 위 그림과 같이 입구와 출구가 동일한 바구니가 있다. Push를 하게 되면 바구니에 원소를 집어넣게 되며, 또 한번 Push를 하게 되면 첫 원소 위에 두번째 원소가 위치하게 된다. 여기서 첫번째 원소를 꺼내고 싶다면 Pop을 두번해야 한다. 결국 삽입을 할 때에도 맨 위(Top)에 삽입을 하게 되고 꺼낼때에도 맨 위에 있는 원소를 꺼내게 된다. 주로 문자열의 역순을.. 더보기 [자료구조] 트리(Tree) 트리(Tree) 란? 트리는 노드로 이루어진 자료 구조 트리는 하나의 루트 노드를 갖음 루트 노드는 0개 이상의 자식 노드를 갖고 있음. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있음. 노드와 노드는 서로를 연결하는 간선들로 구성. 트리에는 사이클(cycle)이 존재할 수 없음. 노드들은 특정 순서로 나열될 수도, 아닐 수도 있음. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있음. 각 노드는 어떤 자료형으로도 표현 가능함. 비선형 자료구조로 계층적 관계를 표현함. 그래프의 한 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류. 트리의 특징 그래프의 한 종.. 더보기 이전 1 2 다음 목록 더보기
