[Swift] 시간복잡도의 함정, Swift에서 Queue는 뭘로 구현해야 할까?

GUNDY·2024년 1월 22일
algorithmqueueswift
post-thumbnail

큐하면 무엇이 떠오르는가?

블리츠의 큐?

그거 말고

그럼 게임의 큐?

맞다. 오늘 알아볼 것은 바로 대기열을 의미하는 큐(Queue)이다.

Queue

큐는 마트의 계산줄을 생각하면 바로 이해할 수 있는 개념이다.

  • 새로 온 손님은 줄의 맨 뒤에 서게 된다.
  • 맨 앞의 손님이 먼저 계산을 받고 떠난다.

즉 먼저 온 손님이 먼저 가게 되는 것이다. 이를 선입선출(First In First Out, FIFO)이라고 한다.

그리고 큐는 대표적인 FIFO 자료구조이다.

Behavior

큐에는 기본적인 동작 두 가지가 필요하다.

  1. 요소를 큐의 맨 뒤에 추가하는 enqueue
  2. 맨 앞에서 요소를 꺼내는 dequeue

이 두 가지 동작만 정의되어도 그것은 큐라고 부를 수 있다. 이 행동들을 프로토콜로 정의한다면 다음과 같다.

protocol Queueable {
    associatedtype Element
    mutating func enqueue(_ newElement: Element)
    mutating func dequeue() -> Element?
}

enqueue랑 dequeue만 필요하다며, Element는 뭔데?

위 예시 코드를 보면 associatedtype Element이 눈에 띌 것이다.

Swift는 타입에 있어 아주 깐깐하기 때문에 이 자료구조가 어떤 타입을 다룰 것인지 명확히 해줘야한다. 하지만 아직은 큐가 어떤 타입의 요소를 관리할 것인지 알 수 없기 때문에 특정 타입 대신 자리 표시자 역할을 하는 Associated Type을 사용했다.

이 Queueable 프로토콜을 준수하기만 하더라도 그것은 큐라고 부를 수 있다.

Implement

보통 Swift에서 큐를 구현할 땐 세 가지 방법 중에서 구현한다.

  • Array
  • Double Stack
  • Linked List

모두 enqueue와 dequeue 메서드를 구현할 것이지만 그 내부 구현에 무엇을 사용할 것이냐가 기준이다.

Array

가장 쉬운 방법으로 배열을 사용하는 방법이다.

Swift의 배열은 맨 뒤에 추가하는 append와 맨 앞에서 꺼내는 removeFirst가 있기 때문이다.

struct ArrayQueue<Element>: Queueable {
    private var array = [Element]()
    
    mutating func enqueue(_ newElement: Element) {
        array.append(newElement)
    }
    
    mutating func dequeue() -> Element? {
        array.removeFirst()
    }
}

얼핏보면 문제가 없을 것 같지만 이 코드에는 치명적인 문제가 있다.

배열이 빈 상태에서 removeFirst()를 호출하는 것은 런타임 에러를 발생시키기 때문이다.

이를 해결하는 방법은 무척 쉬운데, guard 문을 통해 비어있는 경우를 막아주는 것이다.

mutating func dequeue() -> Element? {
    guard let first = array.first else { return nil }
    
    return array.removeFirst()
}
````는 `removeLast`와 달리 비어있을 경우 nil을 반환하지, 에러를 발생시키지는 않기 때문이다.

그래서 다음과 같이 구현하면 에러를 발생시키지 않고 기본적인 큐를 구현할 수 있다.

```swift
struct ArrayQueue<Element>: Queueable {
    private var array = [Element]()
    
    mutating func enqueue(_ newElement: Element) {
        array.append(newElement)
    }
    
    mutating func dequeue() -> Element? {
        guard let first = array.first else { return nil }
        
        return array.removeFirst()
    }
}

Double Stack

우선 스택이란 것도 큐와 마찬가지로 자료구조이다. 그런데 큐와 달리 마지막에 입력한 요소가 먼저 꺼내지는 후입선출(Last In First Out, LIFO)의 자료구조이다.

LIFO를 가지고 어떻게 FIFO로 만드나 의아할 사람들이 있을 것이다.

우선 Swift에서 스택을 구현하는 것은 아주 쉽다고 이야기하고 싶다. 그저 배열의 append와 removeLast를 쓰면 되기 때문이다. 사실 직접 구현하지 않고 배열을 가지고 해당 메서드만 써도 된다.

앞서 말했듯이 에러를 발생시킬 수 있으니 popLast를 쓰는 것이 더욱 좋다.

중요한 것은 Swift의 배열은 뒤집을 수 있다는 것이다.

넣을 때는 입력을 받는 용도의 스택에 차곡차곡 쌓고, 꺼낼 때는 그걸 뒤집어서 꺼내는 용도의 스택에 할당한 뒤 마지막에 꺼내준다.

코드로 구현하면 다음과 같다.

struct DoubleStackQueue<Element>: Queueable {
    private var inStack = [Element]()
    private var outStack = [Element]()
    
    mutating func enqueue(_ newElement: Element) {
        inStack.append(newElement)
    }
    
    mutating func dequeue() -> Element? {
        if outStack.isEmpty {
            outStack = inStack.reversed()
            inStack.removeAll()
        }
        
        return outStack.popLast()
    }
}

그런데 굳이 배열 하나로 하지 않고 뒤집는 이유가 뭘까?

그것은 시간복잡도 때문이다. 배열은 메모리의 연속된 부분에 할당되는데, 앞에서부터 인덱스를 부여받기 때문에 앞에서 꺼내면 0번 인덱스 위치로 1번 인덱스의 요소가 이동하게 된다. 마찬가지로 n번의 인덱스까지 앞자리로 한 칸씩 이동해야 하므로 이 꺼내는 동작 하나를 위해서 n번의 작업을 수행해야 한다. 그렇기 때문에 배열의 앞에서 꺼내는 동작, 즉 removeFirst는 O(n)의 시간복잡도를 가진다.

그런데 맨 마지막에서 꺼내는 동작은 앞선 요소들의 인덱스가 변경되지 않기 때문에 마지막 요소만 제거하고 끝난다. 즉, popLast는 O(1)의 시간복잡도를 가진다고 할 수 있다.

이 더블 스택 큐는 넣는 동작과 빼는 동작 모두 O(1)의 시간복잡도를 갖게 되므로 배열로 구현한 경우보다 더욱 빠르다.

Linked List

링크드 리스트, 소위 말하는 연결 리스트 또한 하나의 자료구조이다. 이 구조의 특징은 배열과 달리 연속되지 않은 메모리로도 사용할 수 있다는 것인데, 참조 테크닉을 통해 이를 수행할 수 있다.

코드를 보면서 설명하는 것이 더 이해하기 쉬울 것이다.

struct LinkedListQueue<Element>: Queueable {
    final class Node {
        let value: Element
        var next: Node?
        
        init(value: Element) {
            self.value = value
        }
    }
    
    private var head: Node?
    private var tail: Node?
    
    mutating func enqueue(_ newElement: Element) {
        let newNode = Node(value: newElement)
        tail?.next = newNode
        
        if head == nil {
            head = newNode
        }
        
        tail = newNode
    }
    
    mutating func dequeue() -> Element? {
        let element = head?.value
        head = head?.next
        
        if head == nil {
            tail = nil
        }
        
        return element
    }
}

이전 큐들에 비해 코드가 길고 복잡하게 느껴질 수 있다.

우선 중첩 타입인 Node 타입부터 살펴보자.

  • Element 타입의 value 프로퍼티가 있다. 이는 큐의 요소를 보관한다는 의미이다.
  • Node? 타입의 next 프로퍼티가 있다. 이는 이 노드의 다음 노드를 참조한다는 의미이다.

즉 비상연락망처럼 각 노드는 자신의 다음 노드에 대해서만 알고 있는다.

다음은 LinkedListQueue 자체에 대해 살펴보자.

  • 두 저장 프로퍼티 head와 tail을 갖고 있다. 이로 인해 큐의 맨 처음와 끝을 알 수 있다.
  • enqueue에서는 전달된 값으로 새 노드를 만들어 tail.next에 할당한 뒤, tail에 다시 할당하는 것을 볼 수 있다. 이로 인해 모든 요소가 연결되게(Link) 된다.
  • dequeue에서는 head의 값을 반환하기 위해 지역 변수에 값을 할당한 다음 head를 head.next로 바꿔주고 반환한다. 이로 인해 순서대로 꺼낼 수 있게 된다.
  • enqueue와 dequeue에서 모두 if head == nil 조건문이 사용된다. 이로 인해 빈 큐에 넣을 때, 꺼내면서 빈 큐가 될 때 모두 적절한 처리를 하게 된다.

참조 개념을 이해하지 못했다면 이 방법이 제일 어렵게 느껴질 수 있다.

Compare each queue

지금까지 세 가지 방법으로 큐를 구현하는 것을 보았는데, "그래서 어떤 게 좋은 거지?"하고 생각할 수 있다.

우선 시간복잡도를 기준으로 고민을 했으면 좋겠다.

첫 번째, enqueue

  • Array: O(1)
  • Double Stack: O(1)
  • Linked List: O(1)

enqueue에 있어서는 시간 복잡도로 따지면 세 방법 모두 O(1)이다

두 번째, dequque

  • Array: O(n)
  • Double Stack: O(1), reversed() 호출시 O(n)
  • Linked List: O(1)

dequeue를 보아하니 Array는 꺼낼 때 항상 O(n)이기 때문에 피하는 것이 좋을 것 같다.

그럼 나머지 둘은? 더블 스택은 가끔 뒤집어줘야 하니까 연결 리스트가 유리한 건가?

우연히 dequeue를 수행할 때 reversed()를 호출해줘야 하는 경우 항상 O(1)인 연결 리스트보다 느릴 수도 있을 것이다.

하지만 중요한 것은 더 넓게 봐도 시간복잡도가 차이나는가?

조금 더 길게 봐서 일련의 요소를 큐로 처리한다고 했을 때 모든 요소를 enqueue 한 뒤에 dequeue 한다고 해보자. 내부 구현으로 치환해서 생각해보자

  • Double Stack: append() n번, reversed() 1번, popLast() n번, 즉 O(n), O(n), O(n)이므로 총 시간복잡도는 O(n)이다
  • Linked List: Node.init() n번, tail.next 할당 n번, tail 할당 n번, 지역변수 할당 n번, head.next 할당 n번, 즉 이것도 O(n)이다.

여기서 일부 사람들은 이건 reversed가 한 번 호출되는 가정이니까, 여러 번 호출되면 다르지 않겠느냐고 할 수 있다.

그건 틀렸다.

매번 n의 크기를 가진 배열을 뒤집는다면 시간복잡도가 O(n²)이겠지만 이 작업은 매번 수행되지 않는다. dequeue에서는 매번 수행할 수도 없을 뿐더러, 만약 매번 수행하게 하기 위해 enqueue를 할 때마다 reversed를 호출해 out에 추가할당 해준다면 그 작업은 항상 크기가 1인 배열을 뒤집기 때문에 O(1)로 간주하는 것이 적절하다.

그러니까 더블 스택 큐의 dequeue는 그냥 O(1)이라고 보는 것이 타당하다. 물론 Big O 표기법은 최악의 경우를 상정해 작성하니까 O(n)이라고 표현한다. 하지만 나는 더블 스택의 dequeue가 O(n)이라는 것을 납득할 수 없다. dequeue가 O(n)이라면 dequeue를 n번 호출하는 동작이 O(n²)이 되지 않겠는가? dequeue를 n번 호출하는 동작이 O(n)임을 보장하는데 이는 납득하기 어렵다 이미 말이 되지 않는다. 적어도 O(1)에 준한다 정도로 표현하고 싶다.

둘 다 O(1), 혹은 그에 준한다면 어느 쪽을 사용해도 상관 없는 것 아니야?

둘 모두 시간복잡도는 O(1)이지만 내부에서 처리하는 코드가 연결리스트 쪽이 더 많다.

그리고 Node는 클래스이기 때문에 힙 할당과 참조 카운팅이라는 요소도 고려해야 한다.

어차피 배열도 힙에 할당하고 참조 카운트 발생시키지 않나?

두 개의 배열과 N개의 노드를 비교하면 어느쪽 힙 할당과 레퍼런스 카운팅이 더 성능적으로 소모가 많이될 지 예상할 수 있다.

결론

이 글을 작성하기 전에 큐 구조를 사용하는 알고리즘 문제를 풀 때, 내가 시도해본 모든 문제에서 더블 스택보다 연결 리스트 구현 쪽이 느려 막연한 의구심을 갖고 있었다. 왜냐하면 나는 시간복잡도 적으로 항상 O(1)인 연결 리스트 쪽이 더 빠를 것이라고 기대하고 있었기 때문이다. 이는 시간 복잡도의 함정이었고, 요즘 WWDC의 성능과 관련된 세션들을 보다보니 머릿속에서 퍼즐이 맞춰지며 이 포스팅을 쓰게 되었다. 시간복잡도는 물론 중요하지만 시간복잡도가 나를 속일 수도 있다. 보다 다각도에서 고려해야 한다.

나는 오늘 알아본 방법 중에서 더블 스택 큐가 구현하기도 쉽고 성능도 우수하다고 생각한다. 그러니 큐 자료구조를 구현할 일이 있으면 더블 스택 큐를 사용하기를 추천한다.

똑같은 문제를 큐 타입만 바꿔서 푼 결과이다. 위는 연결 리스트 큐이고 아래는 더블 스택 큐이다. 시간도 메모리도 차이가 많이 난다. 물론 이런 온라인 문제 풀이는 채점 당시의 상황이나 기타 요인들로 인해 항상 같은 결과를 장담할 수는 없고 항상 옳은 것은 아니지만, 이는 유의미한 차이로 보인다. 시간, 즉 성능도 메모리도 차이가 많이 난다.

이 포스팅에서는 매우 기본적인 enqueue와 dequeue만을 예시 코드로 보여줬지만 그 밖에도 isEmpty나 count 등의 프로퍼티가 필요하다면 조금 고민해보면 쉽게 구현할 수 있을 것이다.

profile
GUNDY
개발자할건디?
이전 포스트

[Swift] Task

다음 포스트

불필요한 업데이트를 유발하는 프로퍼티

0개의 댓글