도입
Swift로 조합을 구현하는 코드를 작성해보려고 하면, 다음과 같이 작성할 수 있습니다.
[Read More]
균형 이진 탐색 트리(1)-트립(treap)
이전 포스트에서 알아본 이진 검색 트리는 검색과 삽입 삭제 모두 O(log n)의 빠른 속도를 제공하지만, 원소의 입력 순서에 따라 이진 트리가 치우치게 되면 성능이 O(log n)으로 악화되는 문제가 있습니다. 이를 위해서는 이진 트리가 균형을 유지하도록 해야되는데, 이를 위해서는 별도로 트리가 균형잡히도록 변형시키거나, 삽입과 삭제 과정에서 자동적으로 균형을 맞춰주도록 해야 합니다....
[Read More]
이진탐색트리(Binary Search Tree)-기본
이번 포스트에서는 이진 탐색 트리(Binary Search Tree, BST)에 대해서 알아보고, 이를 실제로 구현해보도록 하겠습니다. 들어가기 전, 여기서 다루는 BST는 가장 기본적인 형태의 BST임을 밝힙니다.
[Read More]
이분탐색(Binary Search)
이번 포스트에서는 배열에서 원하는 원소의 존재 여부를 빠르게 탐색할 수 있게 만드는 이분 탐색에 대해서 알아보고, Swift에서 이를 활용하는 방법에 대해서 알아보겠습니다.
[Read More]
Swift의 기본 정렬 알고리즘 - Timsort
Swift는 RandomAccessCollection 타입에 대해서 기본 sort() 메소드를 제공합니다. 이 sort()메소드는 TimSort라는 정렬 알고리즘을 사용합니다. 이번 포스트에서는 이 TimSort와, 이 Timsort의 기반이 되는 InsertionSort와 MergeSort에 대해서도 알아보겠습니다.
[Read More]
Heap 자료구조
힙 자료구조는 트리의 일종으로, 여러 원소 중 최댓값 혹은 최솟값을 찾는데에 유용하게 사용할 수 있는 자료구조입니다. 오늘은 Heap의 원리와 그 구현을 한번 살펴보도록 하겠습니다.
[Read More]
문자열 검색(2) - Trie
이번 포스트에서는 문자열 검색 문제에 유용하게 사용할 수 있는 자료구조인 Trie에 대해서 알아보겠습니다. 지난번에 알아본 KMP가 매우 긴 문자열에서 원하는 문자열을 찾는 알고리즘이라면, 여기서 살펴볼 Trie는 여러개의 문자열 집합에서 원하는 문자열을 찾는 문제에 사용할 수 있습니다.
[Read More]
상호 배타적 집합-union-find
정의
상호 배타적 집합(disjoint set)은 전체 집합에서 공통 원소를 가지지 않는 여러 부분 집합들을 저장하고 조작하는 자료구조입니다.
[Read More]
문자열 검색(1)-KMP알고리즘
문자열 검색이란, 전체 문자열(짚더미(HayStack)에 비유합니다)에서 원하는 문자열(바늘(Niddle)에 비유합니다)의 위치를 모두 찾는 알고리즘입니다. 문자열의 위치는 전체 문자열에서의 시작 인덱스로 나타냅니다. 가장 간단한 구현방법과, 이를 개선한 KMP 알고리즘을 알아보도록 하겠습니다.
[Read More]