자료구조&알고리즘 in Swift

Posted on | In

개요

자료구조, 알고리즘… 스위프트로는 어떻게 할까: OverView



자료구조

자료구조는 프로그래밍에 있어 효율성, 확장 가능성, 유지보수를 향상시키기 위한 주요 개념이다.

시스템에서 데이터의 공유, 유지, 정렬, 검색 등 데이터 활용을 위한 데이터의 체계화 방법이다.

Data Structure + Algorithm = Program/System



Swift REPL

Read-Eval-Print-Loop의 줄임말로 CLI환경에서의 스위프트의 컴파일러중 하나이다.

터미널에서 xcrun swift를 치면 실행할 수 있다.



자료구조의 종류와 장단점

가장 보편적으로 사용되고, 가장 발전된 형태의 자료구조의 종류를 알아보자


배열


자료구조의 종류와 장단점

가장 많이 사용되고 발전된 형태의 자료구조의 장단점에 대해 알아보겠다


배열


장점

인덱스 값을 미리 알고 있는 경우, 해당 데이터에 매우 신속하게 접근할 수 있고 새로운 요소를 추가할 수 있다.


단점

크기가 고정되고, 삭제 및 검색은 느리게 진행된다.


정렬된 배열


장점

비정렬 배열에 비해 검색 속도가 더 빠르다.


단점

크기가 고정되고, 삭제 및 검색은 느리게 진행된다.


큐


장점

먼저 입력된 데이터가 먼저 출력될 수 있는 FIFO 접근 방식이 제공된다.


단점

다른 요소에 대한 접근 속도는 느리다.


스택


장점

나중에 입력된 데이터가 먼저 출력될 수 있는 LIFO 접근 방식이 제공된다.


단점

크기가 고정되고, 삭제 및 검색은 느리게 진행된다.


리스트


장점

데이터 삽입 및 삭제 속도가 빠르다


단점

검색 속도는 느리다.


해시 테이블


장점

키값을 미리 알고 있는 경우, 해당 데이터에 매우 신속하게 접근할 수 있고, 새로운 요소를 매우 신속하게 삽입할 수 있다.


단점

키값을 모를 경우 접근 속도가 느리고, 삭제 속도가 느리며 메모리 효율성이 떨어진다.


힙


장점

매우 신속하게 삽입 및 삭제가 가능하고, 최대 혹은 최소 항목에 대한 접근 속도가 빠르다.


단점

다른 요소에 대한 접근 속도는 느리다.


트리


장점

데이터 접근 속도가 매우 빠르며, 서로 다른 키값에 대한 충돌 가능성이 없고, 삽입과 삭제 또한 매우 신속히 이루어진다.

문자열 딕셔너리의 정렬, 프리픽스 검색 등에 유용하다.


단점

특정 상황에서 해시 테이블보다 속도가 느릴 수 있다.


레드블랙 트리


장점

삽입, 삭제, 검색 속도가 매우 빠르며, 트리는 항상 균형 상태를 유지한다.


단점

한계 상황에서 데이터 구조를 운영하므로 구현이 까다롭다.


그래프


장점

실제 세계의 상황을 반영한 모델을 구현한다.


단점

알고리즘이 복잡하다.


알고리즘의 효율성

어떤 알고리즘을 선택하냐에 따라 프로그램의 성능이 달라진다. 어떤 알고리즘이 훌륭한지를 판단하기 위해 공간분석과 시간분석을 한다.

공간분석은 메모리 공간을 얼마나 차지하냐이고 시간분석은 문제해결의 소요시간을 의미한다.


최상, 최악, 평균의 경우

문제를 해결할 때 한번에 해결할 수도 모든 방법을 해봐도 해결하지 못할 수도 있다.

이를 위해 알고리즘을 평가할 때 최상, 최악, 평균의 경우로 따져서 평가한다.

보통 최악의 시나리오를 기준으로 평가한다. 최상, 최악, 평균인 상황을 계산하는 작업이 점근적 분석(asymptotic analysis)라고 하고 빅오표기법으로 나타낸다.


점근적 분석

점근적 분석은 알고리즘의 효율성을 측정하고 기본 속성을 비교할 수 있는 방법이다.

알고리즘이 특정 메모리 조건에서 어떻게 작동하는지, 그리고 처리할 데이터의 양에 따라 어느정도 속도를 내는지 파악한다.

표기법에는 3가지가 있는데 빅세타, 빅오, 빅오메가 표기법이다.

  • 빅세타: 정해진 기준선 내에서의 최악의 복잡성과 최상의 복잡성을 표현한다.
  • 빅세타: 최악의 상황을 기준으로 복잡성을 표현한다.
  • 빅세타: 최상의 상황을 기준으로 복잡성을 표현한다.

가장 많이 쓰는 것은 빅오표기법인데, 높은 수준의 복잡성을 보여주며 알고리즘의 시간/공간적 한계점을 파악할 수 있기 때문이다.

1
2
3
4
let array = [1,2,3,4,5]
for num in array {
  print(num)
}

반복문 한번 도는 데 걸리는 시간이 t라고 가정한다. 만약 다섯번 돈다고 하면 5t가 된다.

그렇다면 개수가 n개 이면 tn만큼 도는것이 된다. 이것을 단순하게 시간단위로 변환하면 n이라고 표현한다.

이를 빅오표기법을 이용해서 표현하는데 실행시간이 2n + 1이면 O(n), 2n^2 + 1이면 O(n^2)이다.


복잡도 종류

알고리즘의 복잡성 순서를 오름차순으로 정리해보겠다.


O(1)

입력값에 상관없이 저장 공간과 실행 시간이 항상 일정하다면 O(1)이다.

배열의 요소를 인덱스값으로 접근하는 명령등이 있다.

1
2
3
func firstElement(arr: [Int]) -> Int? {
  return arr.first
}

이 코드는 O(1)의 시간이 소요된다.


O(log(n))

Log(n)은 O(1)과 O(n)의 중간이다. RB트리의 검색과 삽입의 시간복잡도가 O(log(n))이다.

매우 높은 수준의 복잡성이며 DataSet에서 검색할 때 최소 소요 시간이다.


O(n)

O(n)은 선형 복잡성(Linear Complexity)라고 부르며, 실행 시간 t가 입력값의 양에 따라 증가함을 의미한다.

배열에서 최악의 경우 검색 삽입 삭제 작업이 O(n)에 해당한다.


O(nlog(n))

병합정렬에서 최악의 경우 정렬 알고리즘의 시간복잡도에 해당한다.


O(n^2)

2차함수로도 부르며, 다른 대상과의 비교에 해당하는 복잡도이다. 중첩된 두개의 순환문도 해당한다.


O(2^n)

알고리즘이 각 단계별로 진행될 때마다 데이터 처리량이 두배로 늘어나는 경우이다.

대표적으로 피보나치가 해당한다.

매우 좋지않은 성능이며 의도한 것이 아니면 복잡도에 해당한다면 다시 짜는게 좋을지도…


시간복잡도의 비교

```swift import Foundation

struct Stopwatch { init() { } private var startTime: TimeInterval = 0.0 private var endTime: TimeInterval = 0.0

mutating func start() { startTime = NSDate().timeIntervalSince1970 }

mutating func stop() -> TimeInterval { endTime = NSDate().timeIntervalSince1970 return endTime - startTime } }

개요

고급 자료구조를 구현하기 위한 개념들을 알아보고 스택, 큐, 리스트등 스위프트로 구현해보자



Protocol

스위프트는 컬렉션 자료형에서 각각의 요소에 접근할 수 있는 서브스크립트, for…in등 다양한 기능을 제고한다.

이는 컬렉션 자료형이 3개의 프로토콜을 채택하고 있기 때문인데, IteratorProtocol, Sequence, Collection이다.

이 프로토콜들을 채택하는 커스텀 컬렉션 자료형을 만들면, 그 또한 일반 자료형처럼 사용가능하다.

위의 3개뿐만 아니라 다양한 프로토콜에 대해 알아보겠다.


IteratorProtocol

CPP에서 Iterator라는 개념을 공부했었다. 직역하면 반복자이고 CPP에서는 컨테이너의 포인터 역할을 하던 애였다.

스위프트에서는 컬렉션을 반복 순회하는 next()메서드를 통해 컬렉션을 반복해서 순회할 수 있게하기 위해서 사용한다.


Sequence

Sequence Protocol을 채택하는 자료형은 for…in으로 컬렉션을 순회할 수 있다.

컬렉션 프로토콜을 까보면 이 sequence 프로토콜을 채택하고 있는 걸 알 수 있다.

이 프로토콜을 채택하고 있지 않다면 for i in example과 같은 것은 할 수 없다.

이 프로토콜을 채택하면 public func makeIterator() -> Self.Iterator라는 메서드를 구현해야한다.


Collection

컬렉션은 위치를 특정할 수 있는 시퀀스를 제공하며 컬렉션을 순회하면서 요소들을 인덱스 값으로 저장하고 접근할 수 있게 한다.

따라서 컬렉션은 Sequence, Indexable 프로토콜을 채택하고 있고 다음과 같은 메서드를 구현해야한다.

  • startIndex
  • endIndex
  • index(after:)
  • subscript


CustomStringConvertible

해당 컬렉션 요소들을 String 형태의 내가 표현하고 싶은대로 할 수 있다.

description 변수를 무조건 가지고 있어야한다.


CustomDebugStringConvertible

해당 컬렉션 요소들을 String 형태의 내가 표현하고 싶은대로 할 수 있다.

debugDescription 변수를 무조건 가지고 있어야한다.


ExpressibleByArrayLiteral

컬렉션을 배열형태로 초기화 시키고 싶을 때 구현하면 된다.

public init(arrayLiteral data: T...)의 생성자를 구현해야한다.


MutableCollection

subscript 문법을 사용할 수 있다.

서브스크립트를 이용해서 특정 요소에 인덱스로 접근할 수 있게 해준다.


Stack

자세한 설명

구현

스택은 Last In First Out의 자료구조를 나타낸다.

흔히 접시를 쌓아올린 모습을 연상하며, 배열과 비슷하지만 스택은 개별 요소에 접근하는데에 제한을 둔다.


Stack의 메서드

  • push(): 스택에 요소 추가
  • pop(): 스택에서 요소 삭제
  • peek(): 스택의 첫번째 요소 반환
  • count: 스택 요소의 수 반환
  • isEmpty(): 스택이 비었는지 판단
  • isFull(): 스택이 다찼는지 판단


Stack의 활용

스택을 활용한 대표적인 곳은 expression 평가, 파싱, 정수형 데이터의 이진수 변환, backtracking 알고리즘, 실행취소/재실행 기능등이다.

근데 스택 쓸 바엔 배열을 쓸거같다.


Queue

자세한 설명

구현

큐는 First In First Out의 자료구조를 나타낸다.

따라서 큐의 요소를 삭제하는 dequeue 메서드를 실행할 때 오버헤드가 발생할 수 있다.

맨 앞의 데이터를 없애고 뒤의 데이터들을 한칸씩 당기는 작업을 해야한다. 이 때의 시간복잡도는 O(n)이다.

따라서 구현에서 주석처리된 부분처럼 헤드 인덱스를 하나 두고 이것을 움직이면서 하는 방법으로 하면 O(1)로 최적화가 된다.


Queue의 메서드

  • enqueue(): 큐에 요소 추가
  • dequeue(): 큐에서 요소 삭제
  • peek(): 큐의 첫번째 요소 반환
  • count: 큐 요소의 수 반환
  • clear(): 큐 비우기
  • isEmpty(): 큐가 비었는지 판단
  • isFull(): 큐가 다찼는지 판단
  • capacity: 큐 용량
  • insert(_:atIndex): 큐의 특정 인덱스에 삽입
  • removeAtIndex(_): 특정 인덱스의 요소를 삭제


Queue 활용

큐는 입력된 순서대로 처리할 때 사용한다. 대표적으로 음식점에서 주문들어온대로 처리하는 시스템 같은것이다.

근데 큐 쓸 바엔 배열 쓸거같다.