본문 바로가기

728x90

🖥 Computer Science/Data Structure10

[Data Structure] Trie란? (feat. 이론) 안녕하세요 Foma 💻 입니다! 오늘은 연결된 문자열을 효율적으로 저장해 검색을 효율적으로 도와주는 자료구조인 트라이(Trie)에 대해 정리해 보려고 합니다! 바로 시작할게요~ Trie란? 트라이(trie)는 컴퓨터 과학에서 탐색 트리의 일종이다. 동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조이다. 주로 문자열이 키인 경우가 많다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. - 위키 백과 - 즉, 트리 형태로 연결된 문자열을 차례로 저장하는.. 2022. 7. 29.

[Data Structure] B-Tree란? 안녕하세요 Foma 💻 입니다! 오늘은 트리 자료구조 중 균형 끝판왕 (이름 자체가 Balanced - Tree)인 B-Tree에 대해 알아보겠습니다. 바로 시작할게요~ B-Tree의 배경 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. - 위키 백과 - 즉, 이진 트리를 조금 더 효율적으로 확장한 자료구조에요! 이진 탐색 트리는 최악의 경우 O(n)의 시간 복잡도를 갖기 때문에 그것을 조금 더 효율적으로 만든 것이 O(logn)의 시간 복잡도를 갖는 AVL 트리였습니다. 하지만 만약 2천만개의 데이터가 있다면 log20,000,000 = 24 즉, 최대 2.. 2021. 12. 6.

[Data Structure] AVL 트리 구현해보기 (feat. Swift) 안녕하세요 Foma 💻 입니다! 저번 시간에 AVL 트리가 뭔지 이론에 대해 알아보았는데요. (혹시 안보신 분들은 여기 에서 확인해주세요!) 오늘은 AVL 트리를 직접 구현해보려고 합니다. 바로 시작할게요~ AVLNode 기본적으로 이진탐색트리의 노드와 똑같지만 왼쪽과,오른쪽 자식의 높이와 밸런스 팩터를 측정할 변수를 따로 만들어었습니다. class AVLNode { var value:T var leftChild:AVLNode? var rightChild:AVLNode? var height:Int = 0 var leftHeight:Int { return leftChild?.height ?? -1 } var rightHeight:Int { return rightChild?.height ?? -1 } var.. 2021. 12. 6.

[Data Structure] AVL(Adelson-Velsky and Landis) 트리란? 안녕하세요 Foma 💻 입니다! 오늘은 저번에 정리했던 이진 탐색 트리를 더 업그레이드(?)한 자료구조인 AVL 트리에 대해서 알아보도록 하겠습니다. (혹시 이진 탐색 트리에 대해 모르시는 분들은 여기 에서 보고 와주세요!) 바로 시작할게요~ AVL(Adelson-Velsky and Landis) 트리란? 🤔 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 스스로 균형을 잡는 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. - 위키 백과 - 즉, .. 2021. 12. 1.

[Data Structure] 이진 탐색 트리(Binary Search Tree) 구현해보기 (feat.Swift) 안녕하세요 Foma 💻 입니다! 저번 시간에 이진 탐색 트리가 뭔지 이론에 대해 알아보았는데요. 오늘은 이진 탐색 트리를 직접 구현해보려고 합니다. 바로 시작할게요~ BSTNode 이진 탐색 트리의 노드를 만들어 주겠습니다. 노드는 값,왼쪽,오른쪽 자식의 노드 정보를 가지고 있습니다. class BSTNode { var value:T var leftChild:BSTNode? var rightChild:BSTNode? init(value:T) { self.value = value } } Binary Search Tree 이진 탐색 트리의 최상단 값을 가질 root를 프로퍼티로 정의했습니다. struct BinarySearchTree { var root:BSTNode? Insert public mutatin.. 2021. 11. 18.

[Data Structure] 이진 탐색 트리(Binary Search Tree)란? 안녕하세요 Foma 💻 입니다! 오늘은 트리 자료구조 중 효율적인 검색,삽입,삭제를 할 수 있는 이진 탐색 트리에 대해서 알아보겠습니다. 바로 시작할게요~ 이진 트리(Binary Tree)란? 🤔 이진 탐색 트리는 이진 트리 자료구조로 되어있기 때문에 먼저 이진 트리가 뭔지에 대해 알아보겠습니다. 이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.... - 위키 백과 - 즉, 노드마다 자식이 2개 이하인 트리를 말합니다. 아래 그림처럼 이루어진 트리를 말합니다. (자식이 없어도 되고, 하나여도 되고, 두 개여도 됩니다.) 이진 탐색 트리(Binary Search Tree)란? 🧐 이진 탐색 트리는 다음과 같은 속.. 2021. 11. 17.

[Data Structure] 해쉬 테이블(Hash Table) 구현해보기(feat. Swift) 안녕하세요 Foma 💻 입니다! 오늘은 저번 글에서 해쉬 테이블의 이론에 이어서 직접 구현해 보려고 합니다! (혹시 저번 글을 안보셨다면 여기 를 통해서 보고 와주세요~) 바로 시작할게요~ HashTable 먼저 저는 해쉬 함수를 Digit Folding 알고리즘을 이용해서 만들 것이기 때문에 key값을 String으로 설정했습니다. 또한 충돌이 났을 때 해결 방법으로 Chaining 기법을 사용하였지만 연결 리스트 대신 배열을 사용했습니다. 아래와 같이 typealias로 별칭을 설정해주고 버킷을 이중배열로 선언했습니다. public struct HashTable { public typealias Key = String private typealias Element = (key:Key,value:Val.. 2021. 11. 16.

[Data Structure] 해쉬 테이블(Hash Table)이란? (feat. 이론) 안녕하세요 Foma 💻 입니다! 오늘은 우리가 아주 흔하게 사용하고 있는 해쉬 테이블, Swift로 말하면 딕셔너리에 대해서 알아볼 거에요! 이미 구현되어 있는 코드로 쉽게 사용했는데 직접 구현하려고 하니 진짜 복잡하더라구요. 그래서 오늘은 해쉬 테이블에 대해서 정리해보려고 합니다! 바로 시작할게요~ 해쉬 테이블(Hash Table)이란? 정의는 아래와 같습니다. 해시 테이블은 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. - 위키 백과 - 즉, key와 value를 사용해서 데이터를 저장하는 자료구조입니다. key값으로 value를 한 번에 찾을 .. 2021. 11. 15.

[Data Structure] 힙(Heap)이란? (feat. Swift) 안녕하세요 Foma 💻 입니다! 요즘 알고리즘을 공부하고 있는데 그 중 힙소트에 대해 알게 되었습니다. 힙소트를 하려면 힙이라는 자료구조가 필요하더라구요. 그래서 힙이 무엇이고 어떻게 구현하는지에 대해 정리하려고 합니다! 바로 시작할게요~ 완전 이진트리(Complete Binary Tree)란? ⛓ 먼저 힙에 대해 알아보기 전에 완전이진트리에 대해서 알아보겠습니다. 이유는 힙이 완전이진트리로 되어있기 떄문입니다. 완전 이진 트리에서, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h 에서 1부터 2h-1 개의 노드를 가질 수 있다. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다. - 위키 백과 - 즉, 맨 마지막.. 2021. 10. 15.

[Data Structure] 연결리스트에 대해 알아보자(Linked List) 안녕하세요 Foma👟 입니다. 오늘은 연결리스트에 대해서 알아보려고 하는데요. 얼마 전에 2021 카카오 인턴쉽에 출제되었던 "표편집" 이라는 문제를 풀게 되었는데 해당 문제는 연결 리스트를 꼭 사용해야 효율성을 통과할 수 있는 문제였습니다. 그 동안 연결 리스트를 사용해볼 일이 거의 없어서 구체적으로 알아본 적이 없었는데 이번 기회에 연결 리스트의 장점과 구현하는 방법에 대해 정리하려고 합니다. 바로 시작할게요~ Linked List란? "연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을.. 2021. 8. 11.

이전 1 다음

728x90

티스토리툴바