자료구조
특정 문제를 해결하기 위해 적절한 데이터 구조와 알고리즘을 선택하는 것은 해당 어플리케이션의 유용성을 결정짓는다. 데이터 구조에 대한 기초를 다진 다음 스위프트 REPL(Read-Eval-Print-Loop)을 이용해서 간단한 데이터 구조 실습 예제를 작성한다. 마지막으로, 서로 다른 데이터 구조가 지닌 장단점을 좀 더 명확히 파악하기 위한 지표인 알고리즘 성능에 대해 소개
데이터의 추상화 기법은 데이터가 지닌 복잡성을 관리하기 위한 기술이다. 데이터 구조를 디자인할 때 데이터 추상화 기법을 사용하는데, 이는 개발자가 애플리케이션을 만들려고 할 때 내부의 상세한 구현 방식을 몰라도 되도록 하기 위함이다. 내부의 복잡한 구현 방식을 드러내지 않음으로써 개발자는 알고리즘이 제공하는 인터페이스의 활용에 더욱 집중할 수 있으며, 이 때문에 데이터 구조는 프로그램 내부에서 구현하게 된다.
기본적인 데이터 구조
데이터 구조의 가장 근원적인 형태는 배열과 포인터 두 가지 타입
인접 데이터 구조는 데이터를 메모리 영역 중 인접한 부분에 저장한다. 인접 데이터 구조에는 배열, 힙, 매트릭스, 해시 테이블 등이 있다.
연결 데이터 구조는 서로 명확히 구분되는 메모리 영역을 차지하되, 포인터라는 주소 체계로 연결, 관리되는 구조. 목록, 트리, 그래프
인접 데이터 구조
선형 데이터 구조를 이루며 일정한 순서에 따라 개별 데이터 요소에 접근할 수 있는 인덱스 기반의 데이터 구조다.
배열
var myIntArray: Array<Int> = [1,3,5] // 배열 선언을 위한 기본 방법
var myIntArray: [Int] = [1,3,5] // 축약형
var myIntArray = [1,2,3] // 배열 타입 추측
var my2DArray: [[Int]] = [[1,2], [10,11], [20,30]]
배열 요소 추가
var myIntArray = [1,3,5]
myIntArray.append(7) // [1,3,5,7]
myIntArray.insert(4, at: 2) // [1,3,4,5,7]
myIntArray.removeLast() // [1,3,4,5]
myIntArray.remove(at: 3) // [1,3,4]
연결 데이터 구조
연결 데이터 구조는 데이터 타입과 이를 다른 데이터와 묶어주는 포인터로 구성된다. 여기서 포인터란 메모리상의 위치 주소를 의미한다. 스위프트는 직접적으로 포인터에 접근하지 않고 포인터를 활용할 수 있는 별도의 추상 체계를 제공한다.
연결 리스트는 일련의 노드로 구성되며, 이들 노드는 링크 필드를 통해 서로 연결돼 있다.
class LinkedList<T> {
var item: T?
var next: LinkedList<T>?
}
데이터 구조의 종류와 장단점
| 데이터 구조 …………………. | 장점 | 단점 |
|---|---|---|
| 배열 | 인덱스 값을 미리 알고 있는 경우, 해당 데이터에 매우 신속하게 접근할 수 있고, 새로운 요소를 매우 신속하게 삽입할 수 있다. | 크기가 고정되고, 삭제 및 검색은 느리게 진행된다. |
| 정렬된 배열 | 비정렬 배열에 비해 검색 속도가 더 빠르다. | 크기가 고정되고, 삭제 및 검색은 느리게 진행된다. |
| 큐 | 먼저 입력된 데이터가 먼저 출력될 수 있는 FIFO 접근 방식이 제공된다. | 다른 요소에 대한 접근 속도는 느리다. |
| 스택 | 나중에 입력된 데이터가 먼저 출력될 수 있는 LIFO 접근 방식이 제공된다. | 다른 요소에 대한 접근 속도는 느리다. |
| 리스트 | 데이터 삽입 및 삭제 속도가 빠르다. | 검색 속도는 느리다. |
| 해시 테이블 | 값을 미리 알고 있는 경우, 해당 데이터에 매우 신속하게 접근할 수 있고, 새로운 요소를 매우 신속하게 삽입할 수 있다. | 키값을 모를 경우 접근 속도가 느리고, 삭제 속도가 느리며 메모리 효율성이 떨어진다. |
| 데이터 구조 …………………. | 장점 | 단점 |
|---|---|---|
| 힙 | 매우 신속하게 삽입 및 삭제가 가능하고, 최대 혹은 최소 항목에 대한 접근 속도가 빠르다. | 다른 요소에 대한 접근 속도는 느리다. |
| 트라이 | 데이터 접근 속도 매우 빠르며, 서로 다른 키값에 대한 충돌 가능성이 없고, 삽입과 삭제 또한 매우 신속히 이루어진다. 문자열 딕셔너리의 정렬, 프리픽스 검색 등에 유용하다. | 특정 상황에서 해시 테이블보다 속도가 느릴 수 있다. |
| 이진 트리 | (균형 잡힌 트리 구조인 경우) 삽입, 삭제, 검색 속도가 매우 빠르다. | 삭제 알고리즘 작성이 복잡해질 수 있고, 트리 구조가 삽입 순서에 영향을 받으며, 성능이 저하될 수 있다. |
| 레드블랙 트리 | 삽입, 삭제, 검색 속도 매우 빠르며, 트리는 항상 균형 상태를 유지한다. | 한계 상황에서 데이터 구조를 운영하므로 구현이 까다롭다. |
| R 트리 | 공간적 데이터를 나타낼 때 좋으며, 2차원 이상의 구조를 지원한다. | 역사적으로 성능이 검증되지 못했다. |
| 그래프 | 실제 세계의 상황을 반영한 모델을 구현한다. | 일부 알고리즘은 느리고 복잡하다. |
Value types, References types
value type은 오직 하나의 소유 객체만을 지니며, 해당 타입의 데이터가 변수 또는 상수에 할당됐을 때, 혹은 함수에 전달됐을 때, 지니고 있던 값을 복사한다.
스위프트의 모든 데이터 타입은 기본적으로 구조체다.
Reference type은 값을 공유한다. 동일한 인스턴스를 참조값으로 활용한다. reference type은 여러 개의 소유 객체가 참조라는 방식으로 공유할 수 있다.
Named types, Compound types
기명 타입, 복합 타입
기명 타입은 사용자가 정의할 수 있는 데이터 타입이자, 해당 타입이 정의될 당시 특정한 이름을 부여할 수 있는 타입. 기명 타입에는 클래스, 구조체, 열거형, 프로토타입이 있다. 사용자 정의 기명 타입 외에 스위프트 라이브러리에는 배열, 딕셔너리, 세트 옵셔널 값을 나타낼 수 있는 기명 타입이 별도로 마련돼 있다. 또한 기명 타입은 익스텐션 선언을 통해 동작 범위를 확장할 수 있다.
복합 타입은 별도의 이름이 붙여지지 않은 타입이며, 스위프트에는 function 타입과 type 타입 등 두개의 복합 타입이 정의돼 있다.
스위프트 표준 라이브러리의 컬렉션 타입
스위프트는 array, dictionary, sets 등 세 가지의 컬렉션 타입을 제공한다.
삽입정렬
func insertionSort(alist: inout [Int]) {
for i in 1..<alist.count {
let tmp = alist[i] // 삽입할 수 있는 기준이 되는 두번째 아이템
var j = i-1 // j는 항상 i보다 하나 앞에 있는 index이다.
while j >= 0 && alist[j] > tmp {// 기준 아이템 바로 이전 아이템이 더 크다면
alist[j+1] = alist[j] // tmp보다 큰 아이템을 인덱스 하나를 더해준다. 즉 뒤로 한칸
j = j - 1 // 그 앞에 index도 비교하기 위해 j에 1을 뺀다.
}
alist[j+1] = tmp // 뒤로 보낸 아이템 자리에 첫 기준 아이템을 넣는다.
}
}
var testArray = [56, 17, 63, 34, 77, 52, 68]
insertionSort(alist: &testArray)
병합정렬
func mergeSort<T:Comparable>(list: inout [T]) {
if list.count <= 1 {
return
}
func merge(left:[T], right:[T]) -> [T] {
var left = left
var right = right
var result = [T]()
while left.count != 0 && right.count != 0 {
if left[0] <= right[0] {
result.append(left.remove(at: 0))
} else {
result.append(right.remove(at: 0))
}
}
while left.count != 0 {
result.append(left.remove(at: 0))
}
while right.count != 0 {
result.append(right.remove(at: 0))
}
return result
}
var left = [T]()
var right = [T]()
let mid = list.count / 2
for i in 0..<mid {
left.append(list[i])
}
for i in mid..<list.count {
right.append(list[i])
}
mergeSort(list: &left)
mergeSort(list: &right)
list = merge(left: left, right: right)
}
insertion vs merge
데이터가 100-1000개의 소규모 입력 데이터에서는 insertion이 빠르다.
입력 데이터가 대규모로 증가할수록 insertion sort algorithm은 매우 느려진다.
[참고 도서]
댓글남기기