본문 바로가기

Swift/자료구조

 (8)
트라이(Trie) Swift 트라이트라이는 문자열이 트리형태로 저장된 자료구조이다.특정 문자열을 탐색할때 특화된 알고리즘으로, 트리는 K진 트리이다. (K는 문자열의 첫번째 문자의 종류) 예로 문자열 "apple", "banana", "avocado" 세가지가 있다고 하면 아래와 같은 트리형태로 만들 수 있다.트리의 최상단노드는 비워두고, 그아래로 k개의 접두사를 갖는 자식노드들을 만든다.문자열 세개중 중복되지 않는 접두사는 a,b로 최상단노드는 두개의 자식노드를 갖는다.우리가 문자열을 비교할때, 앞에서부터 차례로 읽어나가듯이, 주어진 문자열을 순차적으로 연결시킨다.그리고 문자열을 모두 연결시켰다면 마지막노드에 해당노드가 마지막임을 저장해둔다.(Bool 변수를 이용) 주어진 문자열에서 특정 문자열을 찾을때, 최상단 노드부터 시작하여..
세그먼트 트리 Swift 세그먼트 트리세그먼트 트리는 트리형태의 자료구조로 해당 노드에는 구간합이 저장되어 있다.일반적으로 배열에서 특정 구간의 합을 구해야 한다면 O(N)이 걸린다.세그먼트 트리는 노드마다 구간의 합이 저장되어 있기때문에 해당 노드에 접근하여 반환하면 되므로 O(logN)이 걸리게 된다.이처럼 세그먼트 트리는 여러개의 데이터가 연속적으로 있을 때, 특정 구간의 합을 구하는데 효율적인 자료구조이다. 세그먼트 트리만들어보기배열 A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 주어졌다. 편의상 인덱스는 1부터 시작한다.12345678910이를 트리로 만들어보자.위 그림은 배열 A를 트리로 만들어본 형태다.왼쪽노드는 index*2, 오른쪽노드는 index*2+1이 되고, 트리의 특성상 합을 구하면 ..
분리집합과 Union-Find Swift 분리집합분리 집합은 서로 다른원소를 갖는 집합이다. 그래서 각각 분리집합의 공통원소는 없다.전체집합 U라고 하고, 분리집합 A와 B가 있다면, 아래의 수식이 성립한다.- U = A U B- A ∩ B = Ø(A와B는 U의 부분집합이다.)  Union-Find분리집합끼리의 표현을 효율적으로 구현하고, 조작하기 위해 생긴 알고리즘이다.서로다른 분리집합을 합치는 Union연산과 임의의 원소가 어디의 집합에 속하는지 알기위한 find연산이 주어져서 Union-Find라고 불린다.이 알고리즘을 사용하기위해 3가지의 연산을 구현해야한다. 1. 초기화: 기본적으로 구현하고 조작하기위해 분리집합을 구현해야한다. 분리집합의 원소는 자기 자신을 루트노드로 갖는다.2. Union(x,y): 두 원소 x와 y가 주어졌을때, ..
Swift 덱(Deque) 구현 덱 (Deque) - 양방향으로 데이터를 삽입및 삭제가 가능 한 데이터 구조이다. - 양쪽으로 push,pop이 가능하며 시간복잡도는 O(1)이다. - push,pop을 자주 사용하는 알고리즘에서 효율이 좋다. - Swift는 지원하지않고, 직접 구현해야하며, 두개의 배열로 구현한다. import Foundation // Deque struct Deque { var enqueue: [T] var dequeue: [T] = [] init(enqueue: [T]) { self.enqueue = enqueue } var count: Int { return enqueue.count + dequeue.count } var isEmpty: Bool { return enqueue.isEmpty && dequeue.i..
Swift 큐(Queue) 구현 큐 선입선출의 형식인 데이터구조 (FIFO) - Enqueue: 큐 맨 뒤에 요소 추가 - Dequeue: 큐 맨 앞의 데이터를 반환 - Peek: Front에 위치한 데이터 값 반환 - Front: 큐의 앞부분 (가장 먼저 들어온 데이터가 위치함) - Rear: 큐의 뒷부분 ( 가장 최근에 들어온 데이터가 위치함) dequeue하는 과정에서 removeFirst() 메소드를 이용한다면 시간복잡도가 O(n)이 걸리게된다. 이를 해결하기위해 index를 이용해 front부분을 확인하여 데이터를 반환하는 방법도 있지만, reversed()도 O(1)이 걸리므로 이 방법을 사용했다. import Foundation struct Queue { var elements: [T] = [] // 큐 갯수 var cou..
Swift 우선순위 큐(Priority Queue) 구현 우선순위 큐(Priority Queue) 힙을 이용해서 가장 높은 우선순위에 있는 요소를 제일 처음에 위치시키는 자료구조이다. 가장 우선순위가 제거되면, 그다음으로 높은 우선순위인 요소가 앞에 위치하게 된다. 구현을 위해서 힙이 구현되어있어야 한다. 우선순위큐의 삽입 삭제 시간복잡도는 O(logN)으로 일반 배열을 사용하는 것보다 빠르다. 힙 (Heap) Swift 구현 https://jenikeju.tistory.com/129 Swift 힙(Heap) 구현 Heap Heap이란 완전이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 여러 가지의 값 중, 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조이다. 중복값을 허용한다. 완전이진트 jenikeju.tistory.com 우선순위 큐 구현..
Swift 힙(Heap) 구현 Heap Heap이란 완전이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 여러 가지의 값 중, 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조이다. 중복값을 허용한다. 완전이진트리 - 마지막 레벨을 제외하고 모든 레벨에 노드가 꽉 차있다. - 자식노드는 최대 2개만 가질 수 있고, 노드가 왼쪽부터 채워져야 한다. - 배열을 사용한 표현이 가능하다. Swift로 Heap 구현 힙을 저장하는 자료구조는 배열이다. 쉽게 구현하기 위해 배열의 첫 번째 인덱스인 0은 사용하지 않는다. 코드로 보기 전에 Heap의 성질들을 본다. 힙은 구조체로 구현한다. struct Heap { // 힙의 원소를 넣을 배열 선언 // 최대힙,최소힙 정렬함수 선언 private var elements: [T] = [..
Swift 스택(Stack) 구현 스택: 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조로 선형구조이다 (Last In First Out) 자료를 밀어넣는다: push 넣어둔 자료를 꺼낸다: pop 선입선출하는 큐와 반대로 스택은 후입선출을 지킨다. Swift에서는 스택을 구현해서 사용해야 하지만 배열의 append, popLast 를 이용하면 굳이 구현하지않고 배열을 스택처럼 사용할 수 있다. import Foundation struct Stack { var elements: [T] = [] var count: Int { return elements.count } var isEmpty: Bool { return elements.isEmpty } mutating func pop() -> T? { return elements.popLas..

티스토리툴바