[Data Structure] Tree(5) - Red-Black Tree Implementation
2024. 6. 17. 01:42
CS/Data Structure
이번 포스팅에선 "Red-Black Tree"를 Swift로 구현할 것이다.만약 개념에 대한 내용이 궁금하다면 해당 포스팅을 참고 바란다. 자세한 구현은 아래 링크에서 확인해 볼 수 있다. https://github.com/jungseokyoung-cloud/Data-Structure/tree/main/Data-Structure/Tree.playground/Sources/Red-BlackTree Data-Structure/Data-Structure/Tree.playground/Sources/Red-BlackTree at main · jungseokyoung-cloud/Data-StructureData Structures implemented with Swift. Contribute to jungseok..
[Design Pattern] Coordinator 패턴
2024. 5. 26. 22:34
iOS/Pattern
"Coordinator패턴"은 ViewController로부터 화면 전환의 부담을 줄여주기 위한 패턴이다. 이를 통해ViewController 간의 결합도를 낮춰주게 된다. 만약 ViewController에서 다음과 같이 화면 전환 로직을 담당하게 되면,ViewController는 자신의 이후에 올 ViewController가 무엇인지 알아야 한다. @objc didTapButton() { let vc = ViewController() self.pushViewController(vc, animated: true)} 이는, ViewController에서 다음 ViewController를 위한 의존성 생성도 담당해야 하는데, 특히나, MVVM 아키텍처 채턴의 경우, ViewController는 다음과..
[Data Structure] Tree(3) - AVL Tree
2024. 5. 23. 14:29
CS/Data Structure
"AVL 트리"는 자가 균형(Self-Balancing) 이진 검색 트리로, 좌우 서브 트리의 높이 차이가 1을 유지한다. 만약, 높이 차이가 1 이상이 나게 된다면 스스로 균형을 맞추어 높이 차이 1을 유지한다. 이전 포스팅에서 보았던 이진 검색 트리의 경우에는 최악의 경우 모든 연산의 시간복잡도가 $O(N)$이 되었다. 이는 다음과 같이 편향트리가 될 수 있기 때문이다. 따라서, AVL트리는 자가 균형을 통해 높이차를 1을 유지함으로써, 모든 연산의 평균 최악 모두 $O(logN)$을 보장한다. Balance Factor 이진 트리에서 Balance Factor는 다음과 같이 정의된다. 즉, 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. AVL 트리는 BF값이 [-1, 1]범위 ..
[Data Structure] Tree(2) - Binary Search Tree
2024. 5. 17. 23:13
CS/Data Structure
"이진 검색 트리"(Binray Search Tree)는 다음과 같은 성질을 만족하는 이진트리이다. 각 노드에 들어가는 값들은 대소관계를 비교할 수 있다. 노드의 왼쪽 서브트리는 작은 값들을 가진 노드들로 이루어져 있다. 노드의 오른쪽 서브트리는 큰 값들을 가진 노드들로 이루어져 있다. 좌우 서브트리는 각각 위의 2 조건을 만족한다.이러한 특성 때문에 정렬된 이진 트리(Sorted Binary Tree)라고도 부른다. 이진 검색 트리는 검색, 삽입, 삭제 연산들이 평균적으로 $O(logN)$에 동작한다. 해시의 경우, 위의 연산들을 $O(1)$에 제공하지만, 원소 간의 대소관계는 비교할 수 없다. 하지만, 이진 검색 트리의 경우 "5 보다 큰 최초의 원소"와 같은 대소비교 관련 연산을 수행할 수 있다...
[Data Structure] Graph
2024. 5. 6. 13:39
CS/Data Structure
"그래프"(Graph)는 각 데이터와 그들을 잇는 선들로 이루어진 ADT이다. 각 데이터들을 "정점"(vertex) 혹은 "노드"(node)라 부르며, 이들을 잇는 선을 "간선"(edge)라 부른다. 즉, 그래프는 유한한 개수의 정점과 간선으로 이루어진 ADT이다. 이러한 그래프 G 를 G = (V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미한다. 정점(노드) : 각 데이터 간선 : 정점들을 잇는 선 인접 정점: 간선에 의해 연결된 정점 (ex. A의 인접 정점은 B,C)차수(degree) : 정점에 연결된 간선의 개수 (ex. A의 차수는 2)이러한 그래프를 순회하는데 사용하는 알고리즘에는 대표적으로 BFS와 DFS가 있다.순회란, 그래프내의 모든 정점을 한번씩 방문하는 것을 말..
[Data Structure] Hash Table(2) - Implementation
2024. 4. 29. 16:10
CS/Data Structure
Swift에서 HashTable을 활용한 자료구조에는 Set과 Dictionary가 존재한다.이 중 Key-Value 쌍으로 데이터를 저장하는 Dictionary를 구현해 보자. 해당 포스팅에선 Dictionary를 Chaing방법과 Open Addressing 2가지 방법으로 모두 구현해 볼 것이다.여기서는 구현에 관해서만 다룰 것이기 때문에, 해시 테이블 이론에 관련한 것들은 이전 포스팅을 참고 바란다.https://seokyoungg.tistory.com/92 [Data Structure] Hash Table(1) - Concept만약 다음과 같은 데이터가 있다고 가정해 보자. 이들을 저장하기 위해선, 품목을 키값으로 매핑해 개수를 저장해야 한다. 즉, 품목이 인덱스화 될 필요가 있다. 이처럼 k..
[Data Structure] Array & Linked List(2) - Implementation
2024. 4. 5. 16:28
CS/Data Structure
이번 포스팅에선 List ADT 중 Linked List를 Swift를 통해 구현해 보자. 개념에 관해 보고 싶다면 이전 포스팅을 참고 바란다. 전체적인 구현은 여기에서 확인 할 수 있다. https://github.com/jungseokyoung-cloud/Data-Structure GitHub - jungseokyoung-cloud/Data-Structure: Data Structures implemented with Swift Data Structures implemented with Swift. Contribute to jungseokyoung-cloud/Data-Structure development by creating an account on GitHub. github.com Simple L..
[iOS] Custom Drop Down (2) - firstResponder 활용해 리팩토링하기
2024. 3. 27. 15:04
iOS/iOS
이전 포스팅에선, Custom DropDown을 구현했었다. 우선, DropDownView를 살펴보면 다음과 같다. "AnchorView를 터치"하게 되면 DropDownView는 TableView를 display 한다. "TableView에서 옵션을 선택"하거나, "외부 영역을 터치"하면 TableView를 hide 한다. 기존의 로직에선, ViewController가 터치 이벤트의 발생한 영역을 다음과 같이 판단했어야 했다. /// ViewController override func touchesBegan(_ touches: Set, with event: UIEvent?) { super.touchesBegan(touches, with: event) guard let touch = touches.fi..
[iOS] Core Animation(2) - CAAnimation
2024. 3. 7. 17:31
iOS/iOS
이전 포스팅에선 Core Animation과 CALayer의 기본 개념에 대해 알아보았다. 이번 포스팅에선 Custom Animation을 구현해보자. 특정 Layer에 Animation을 추가하고 싶다면 add(_:forKey:) 메서드를 통해 추가한다. func add( _ anim: CAAnimation, forKey key: String? ) 이때 CAAnimation을 통해 Animation을 정의할 수 있는데, 이는 abstract class이기 때문에 다음과 같은 concrete subclass를 사용한다. CABasicAnimation CAKeyframeAnimation CAAnimationGroup CATransition 이렇게 여러가지가 있지만, Core Animation 중 가장 기본..
[iOS] Core Animation(1) - Concept
2024. 3. 5. 16:16
iOS/iOS
"Core Animation"은 iOS 혹은 OS X환경에서 Grapic Rendering 및 Animation Infra로, View 혹은 여러 Element들을 Animating하는데 사용한다. 쉽게 말해 "Core Animation"은 View를 Drawing하는 Framework이다. "Core Graphics"도 View를 Drawing하는 API이지만, CPU에서 그리는 반면 "Core Animation"은 GPU에서 View를 Drawing한다. Swift에서 일어나는 Animation의 경우, 만화처럼 Frame을 빠르게 교체해 실제로 연속적으로 일어난 것처럼 보이게 하는 것이다. 이렇게 1초에 몇 개의 Frame을 표시할 수 있는 지를 "refresh rate"(주사율)로 표현하며, 단위..
[iOS] Render Loop & Hitch(2)
2024. 2. 24. 18:31
iOS/iOS
Hitch는 Render Loop에서 제시간에 Frame을 준비하지 못했을 때 발생한다. 이러한 Hitch는 어떤 Stage에서 발생했냐에 따라, Commit Hitch, Render Hitch로 구분된다. Commit Hitches "Commit Phase"는 UI를 변경하고 업데이트된 UI Layer Tree를 Render server로 제출한다. 이때 Render Server로 제출되는 결과물을 "Commit"이라 부른다. 다음과 같이 "Event Phase"에서 touch이벤트를 통해 backgroundColor와 frame을 변경했다고 가정하자. 다음과 같이 시스템은 display 혹은 layout이 필요하다고 마킹을 하게 된다. 이후 "Commit Phase"에서 시스템에 의해 각 draw(r..
[iOS] Render Loop & Hitch(1)
2024. 2. 22. 01:05
iOS/iOS
App에서 화면 스크롤, Pop Up 등 여러 Animation이 존재한다. 이러한 Animation은 유저의 터치와 같은 이벤트에 의해서 발생하는데, App은 이러한 유저의 이벤트를 통해 변경된 UI를 화면에 Display 하는 과정을 Render Loop이라 부른다. Hitch Render Loop의 각 Cycle에서 만들어지는 화면을 "Frame"이라 부른다. Swift에서 일어나는 Animation의 경우, 만화처럼 Frame을 빠르게 교체해 실제로 연속적으로 일어난것 처럼 보이게 하는 것이다. 만약 Frame이 제때 만들어지지 않는다면 제시간에 교체하지 못하게 되어 사용자에게 버벅거리게 보일 것이다. 이처럼 다음 Frame이 늦어져, 애니메이션이 끊기는 시간을 "Hitch"라고 부른다. 이때, ..