스위프트를 이용한 자료구조

데이터 구조의 가장 근원적인 형태는 사실상 배열과 포인터 두가지 타입이며, 다른 데이터 구조는 여기서 파생된다고 할 수 있다.

• 인접 데이터 구조(Contiguous data structure)
  데이터를 메모리 영역중 인접한 부분에 저장한다.
  배열(Array), 힙(Heap), 매트릭스(Matrix), 해시 테이블(Hash table) 등이 있다.
• 연결 데이터 구조(Linked data structure)
  서로 명확히 구분되는 메모리 영역을 차지하되, 포인터라는 주소체계로 연결해 관리하는 구조이다.
  목록(List), 트리(Tree), 그래프(Graph) 등이 있다.

인접 데이터 구조

인접 데이터 구조는 선형 데이터 구조를 이루며 일정한 순서에 따라 개별 데이터 요소에 접근할 수 있는 인덱스 기반의 데이터 구조이다.

배열

스위프트에서 배열의 인덱스값은 0부터 시작하며 데이터 간에 순서가 있고, 임의로 특정 요소에 접근할 수 있는 데이터 집합의 성질을 갖는다.
일차원 배열에서는 간단하게 $a_{i}$ 형식으로 요소를 표현한다.
매트릭스는 이차원 배열이다.
스위프트에서 다중배열 선언은 대괄호 안에 대괄호를 넣는 식으로 선언한다.

var multiArray : [[Int]] = [[1,2],[3,4]]

배열은 스택, 큐, 힙, 해시 테이블, 문자열 등 다양한 데이터구조를 표현하는데 활용된다.

연결 데이터 구조

연결 데이터 구조는 데이터 타입과 이를 다른 데이터와 묶어주는 포인터로 구성된다.
포인터는 메모리상의 위치주소를 의미한다.
C언어와 같은 로우레벨 프로그래밍 언어와 달리, 스위프트는 포인터에 직접 접근하지 않고, 포인터를 활용할 수 있는 별도의 추상 체계를 제공한다.

연결 리스트

연결 리스트는 일련의 노드로 구성되며, 노드는 링크 필드를 통해 서로 연결돼 있다.
가장 간단한 형태의 연결 리스트는 데이터와 다음 노드에 연결할 수 있는 레퍼런스(또는 링크) 정보를 포함한다.
좀 더 복잡한 형태의 경우, 추가 링크 정보를 통해 연결된 데이터에서 앞 또는 뒤로 이동할 수 있다. 연결 리스트에서 추가 노드를 삽입하거나 삭제하는 일은 매우 간단하다.
단일 연결 리스트의 노드는 다음 노드를 향한 링크 정보만 갖고 있고, 이중 연결 리스트의 노드는 이전 노드와 다음 노드에 대한 링크 정보를 갖고 있다.

단일 연결 리스트의 골격은 다음과 같다.

class LinkedListNode<T> {
	var item : T?
	var next : LinkedListNode<T>?
}

데이터 구조의 종류와 장단점

데이터 구조	장점	단점
배열	인덱스 값을 미리 알고 있는 경우 해당 데이터에 매우 빠르게 접근할 수 있고, 새로운 요소를 매우 빠르게 삽입할 수 있다.	크기가 고정되고, 삭제와 검색은 느리게 진행된다
정렬된 배열	비정렬 배열에 비해 검색속도가 더 빠르다.	크기가 고정되고, 삭제 및 검색은 느리다.
큐	먼저 입력된 데이터가 먼저 출력될 수 있는 FIFO(First In First Out) 접근 방식이 제공된다.	다른 요소에 대한 접근속도가 느리다.
스택	나중에 입력된 데이터가 먼저 출력되는 LIFO 접근 방식이 제공된다.	다른 요소에 대한 접근 속도가 느리다.
리스트	데이터 삽입 및 삭제 속도가 빠르다.	검색 속도가 느리다.
해시 테이블	키 값을 미리 알고 있는 경우 해당 데이터에 매우 빠르게 접근할 수 있고, 새로운 요소를 매우 빠르게 삽입할 수 있다.	키 값을 모를 경우 접근 속도가 느리고, 삭제 속도가 느리며 메모리 효율성이 떨어진다.
힙	매우 빠르게 삽입 및 삭제가 가능하고, 최대 혹은 최소 항목에 대한 접근 속도가 빠르다.	다른 요소에 대한 접근 속도는 느리다.
이진 트리	균형 잡힌 트리구조의 경우 삽입, 삭제, 검색 속도가 매우 빠르다.	삭제 알고리즘이 복잡해질 수 있고, 트리 구조가 삽입순서에 영향을 받으며, 성능이 저하될 수 있다.
레드블랙 트리	삽입, 삭제, 검색속도가 매우 빠르며 트리는 항상 균형상태를 유지한다.	한계 상황에서 데이터 구조를 운영하므로 구현이 까다롭다.
R 트리	공간적 데이터를 나타낼 때 좋으며, 2차원 이상의 구조를 지원한다.	역사적으로 성능이 검증되지 못했다.
트라이	데이터 접근 속도가 매우 빠르며, 서로 다른 키값에 대한 충돌 가능성이 없고, 삽입과 삭제 또한 매우 빠르다. 문자열 딕셔너리의 정렬, 프리픽스 검색 등에 유용하다.	특정 상황에서 해시 테이블보다 속도가 느리다.
그래프	실제 세계의 상황을 반영한 모델을 구현한다.	일부 알고리즘은 느리고 복잡하다

알고리즘

알고리즘은 입력값에 맞는 출력값을 내놓기 위해 만들어진 처리 절차이다.
알고리즘 구현에 있어서 시간과 공간은 매우 중요한 자원이다.
문제 규모에 따라 투자해야 될 자원의 양을 가늠하기 위해 점근 행동(Asymptotic behavior)을 살펴본다.
각 알고리즘은 적합한 데이터 구조를 갖고 있으며, 대부분의 데이터 구조에서 다음과 같은 내용은 필수적으로 파악하고 있어야 한다.

• 데이터를 삽입하는 방법
• 데이터를 삭제하는 방법
• 특정 데이터를 찾는 방법
• 모든 데이터를 순회하는 방법
• 데이터를 정렬하는 방법

스위프트에서의 데이터 타입

C와 같은 언어에서는 원천(primitive) 데이터 타입을 단일 값을 가지는 스칼라 타입으로 구현한다.
스위프트에서 원천 데이터 타입은 스칼라 타입으로 구현돼 있지 않고 다른 프로그래밍 언어와 차이가 있다.

밸류 타입과 레퍼런스 타입

스위프트의 데이터 타입은 밸류 타입과 레퍼런스 타입 두가지다.
밸류 타입은 오직 하나의 소유 객체만을 지니며, 해당 타입의 데이터가 변수 또는 상수에 할당됐을때 혹은 함수에 전달됐을 때, 지니고 있던 값을 복사한다. 밸류 타입에는 구조체와 열거형이 있다. 스위프트의 모든 데이터 타입은 기본적으로 구조체다.
레퍼런스 타입은 밸류 타입과 달리 값을 복사하지 않고 공유한다. 레퍼런스 타입은 변수에 할당하거나 함수에 전달될 때 동일한 인스턴스를 참조값으로 활용한다. 레퍼런스 타입은 여러개의 소유 객체가 참조라는 방식으로 공유할 수 있다.
스위프트의 표준 라이브러리가 제공하는 Int, Double, Floar, String, Character, Bool, Array, Dictionary, Set 등 네이티브 데이터 타입은 다른 언어에서와 같은 원천 데이터 타입이 아니다. 이들 데이터 타입은 구조체 타입으로 정의되고 구현된 기명 타입(Named type) 이다.

기명 타입과 복합 타입(Compound type)

스위프트의 또 다른 데이터 타입 분류체계는 기명 타입과 복합타입이다.
기명 타입은 사용자가 저으이할 수 있는 데이터 타입이자, 해당 타입이 정의될 당시 특정한 이름을 부여할 수 있는 타입이다. 기명타입에는 클래스, 구조체, 열거형, 프로토타입이 있다.

Array

스위프트의 배열은 제네릭 타입 컬렉션. Int, Float, String, 열거형은 물론 클래스까지 포함할 수 있다.
스위프트에서 배열에 요소가 추가될 때마다 소진된 배열용량을 자동으로 증가시킨다. 배열에 대량의 요소가 추가될 것이 예상된다면, 미리 추가적인 배열 용량을 할당해 둬서 수행시간을 줄일 수 있다.

Dictionary

딕셔너리는 무순위 컬렉션으로, 딕셔너리 순회에 따라 반환되는 결과물은 삽입된 순서를 따르지 않는다.

let Dict : [Int: String] = [1: "one", 2: "two", 3: "three"]

for (num, str) in Dict {
    print("num is \(num). str is \(str)")
}

// num is 3. str is three
// num is 1. str is one
// num is 2. str is two
출력순서는 매 실행때마다 바뀐다.

Set

서로 중복되지 않고 unique와 nil이 포함되지 않은 무순위 컬렉션. 스위프트 모든 기본타입이 Hashable 프로토콜을 따르듯 Set 도 Hashable 프로토콜을 준수한다.
세트는 배열에 비해 데이터 접근속도가 훨씬 빠르다. 배열의 크기가 n일때 배열요소에 대한 최악의 검색시나리오에서는 O(n)인 반변, 세트는 크기와 관계없이 O(1)을 유지한다.

Tuple

튜플은 여러 데이터 타입을 동시에 담을 수 있으며, 컬렉션이 아니다. 그래서 내부 요소의 순회는 불가능하다.
튜플은 임시적으로 쓰일 값의 그룹을 만드는데 유용하지만, 영구적으로 저장할 경우에는 다른 자료구조를 사용해야 한다.