Seri

百覺不如一行, A picture is worth one thousand words.

큐

✔︎ 이 글은 Swift Algorighm Club 의 문서를 번역한 글입니다.

큐

이 주제의 튜토리얼은 이 곳에서

큐는 뒤에서부터 새로운 요소를 추가하고, 앞에서부터 삭제하는 리스트이다. 이는 당신이 처음으로 큐에 집어넣는(enqueue) 원소가 처음으로 큐에서 추출하는(dequeue) 원소임을 보장한다. 선입선출을 뜻한다!

이게 왜 필요할까? 많은 알고리즘에서 당신은 무언가를 일시적인 리스트에 추가했다가 나중에 꺼내고 싶을 것이다. 때때로 이것들을 추가하고 삭제하는 순서가 중요할 수 있다.

큐는 선입선출(FIFO-First In First Out)의 구조를 따른다. 처음에 추가한 요소가 처음으로 나오게 되는 것이다. 당연한 말이다! (비슷한 자료구조인 스택은, 후입선출 LIFO-Last In First Out의 구조로 되어 있다.)

예시

아래는 수를 큐에 집어넣는(enqueue) 예시이다.

queue.enqueue(10)

큐는 [ 10 ] 이 된다. 다음 수를 집어넣어보자.

queue.enqueue(3)

큐는 [ 10, 3 ] 이 된다. 또 다른 수를 하나 집어넣어보자.

queue.enqueue(57)

큐는 [ 10, 3, 57 ] 이 된다. 여기서 처음 요소를 큐의 맨 앞에서 꺼내(dequeue)보자.

queue.dequeue()

우리가 처음 추가한 숫자인 10 을 반환한다. 큐는 [ 3, 57 ] 이다. 모든 요소가 하나씩 옮겨졌다.

queue.dequeue()

위 코드 실행시 3 이 반환되고 다음 디큐(dequeue)시 57 을 반환하며 이 방식이 계속된다. 큐가 비어있다면, 큐에서 요소를 빼내는 작업(dequeue)으로 nil 이 반환되거나, 어떤 구현 코드에서는 오류 메시지를 보여 줄 것이다.

주의 : 큐는 항상 최선의 선택이 아닐 수 있다. 아이템이 추가되고 삭제되는 순서가 중요하지 않다면, 큐 대신 스택을 사용할 수 있다. 스택이 큐보다 단순하고 빠르다.

코드

다음은 스위프트로 큐를 구현한 단순한 코드이다. 이는 큐에 집어넣기(enqueue), 큐에서 빼내기(dequeue), 맨 앞 요소 보기(peek) 하기 위한 배열을 새롭게 만든 것과 같다.

wrapper 에 대한 설명 : stack 참고

public struct Queue<T> {
    fileprivate var array = [T]()

    public var isEmpty: Bool {
        return array.isEmpty
    }

    public var count: Int {
        return array.count
    }

    public mutating func enqueue(_ element: T) {
        array.append(element)
    }

    public mutating func dequeue() {
        if isEmpty {
            return nil
        } else {
            return array.removeFirst()
        }
    }

    public var front: T? {
        return array.first
    }
}

이 큐는 잘 작동하지만, 최적의 코드는 아니다.

큐에 추가하는(enqueue) 것은 O(1) 만큼의 연산이 되는데, 배열의 마지막에 요소를 추가하는 것은 배열의 크기와 상관없이 항상 같은 시간이 들기 때문이다.

왜 요소를 추가하는 것이 항상 O(1) 혹은 상수 시간(O(1)과 동일 표기)이 드는지 궁금할 것이다. 이는 스위프트의 배열이 항상 마지막에 빈 공간을 가지고 있기 때문이다.

다음과 같이 실행한다면,

var queue = Queue<String>()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")

배열은 다음과 같이 보일 것이다.

[ "Ada", "Steve", "Tim", xxx, xxx, xxx ]

xxx 로 표시된 공간은 아직 채워지지 않았지만 예약된 메모리 공간이다. 새로운 요소를 추가할 때 사용되지 않은 곳을 덮어쓰게 될 것이다.

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]

이는 하나의 공간에서 다른 곳으로 메모리를 복사하는 것이므로 상수 시간만큼의 연산 시간이 든다.

배열의 끝에는 한정된 수의 공간이 남아 있다. 마지막 xxx 까지 사용된 상태에서, 다른 요소를 추가하고 싶다면, 배열은 더 많은 공간을 만들기 위해 크기를 조정해야 한다.

크기를 조정하는 것은 새로운 메모리를 할당하고, 원래 있던 모든 데이터를 새로운 배열에 복사하는 작업을 포함한다. 이는 비교적으로 느린 O(n) 만큼의 시간을 갖는다. 이는 가끔 일어나는 일이므로, 배열의 끝에 요소를 추가하는 것은 평균적으로, 그리고 분할상환분석상 O(1)의 연산 시간을 갖는다.

분할상환분석(amortized analysis) 은 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리같은 자원 사용량을 분석하기 위해 사용하는 기법이다. 수행된 모든 연산에 대해 자료구조 연산이 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 확률이 포함되지 않으므로 평균비용 분석과는 다르며, 최악의 경우에도 각 연산의 평균 수행성능을 보장한다.

큐에서 제거하는(dequeue) 일은 조금 다르다. 큐에서 요소를 제거하기 위해서 우리는 배열의 첫번째부터 원소를 제거해야 한다. 이는 항상 O(n) 만큼의 연산을 하는데, 배열에 남아 있는 모든 요소들을 메모리 상에서 옮겨야 하기 때문이다.

우리의 예시에서 첫번째 요소 "Ada" 를 제거하면 "Steve" 를 "Ada" 의 자리로, "Tim" 을 "Steve" 의 자리로, "Grace" 를 "Tim" 의 자리로 복사하게 된다.

before   [ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
                   /       /      /
                  /       /      /
                 /       /      /
                /       /      /
 after   [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]

모든 요소들을 메모리에서 옮기는 것은 항상 O(n)의 시간복잡도를 갖는다. 그러므로 우리가 구현한 단순한 큐에서 큐에 추가하는 것(enqueue)은 효율적이지만, 큐에서 제거하는 것(dequeue)은 조금 더 생각해볼만 하다.

더 효율적인 큐

큐에서 제거하는 것(dequeue)을 효율적으로 만들기 위해서 우리는 새로운 공간을 예약해놓을 수 있는데, 이번엔 배열의 앞쪽에 만들어 놓는다. 우리는 이 코드를 우리 스스로 짜야 하는데, 스위프트가 이를 기본적으로 제공해주지 않기 때문이다.

우리가 큐에서 요소를 제거할 때마다(dequeue) 배열의 요소들을 앞으로 옮기(느림)지 않고 빈 배열의 위치를 저장(빠름)하는 것이 더 효율적인 큐의 중심 아이디어다. "Ada" 를 큐에서 제거(dequeue)하고 난 뒤 배열은 다음과 같다.

[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]

"Steve" 를 큐에서 제거(dequeue)하고 나면 배열은 이렇게 된다.

[ xxx, xxx, "Tim", "Grace", xxx, xxx ]

앞에 남겨진 빈 공간들은 절대 재사용되지 않으므로 주기적으로 배열을 잘라 남아 있는 요소들을 앞으로 옮길 수 있게 할 수 있다.

[ "Tim", "Grace", xxx, xxx, xxx, xxx ]

위와 같은 자르기는 메모리를 옮기므로 O(n) 만큼의 시간이 든다. 하지만 이는 한 번씩 일어나는 일이므로 큐에서 빼내는 작업(dequeue)은 평균적으로 O(1) 의 시간을 갖는다.

효율적인 버전의 Queue 를 구현하면 다음과 같다.

public struct Queue<T> {
    fileprivate var array = [T?]()
    fileprivate var head = 0

    public var isEmpty: Bool {
        return count == 0
    }

    public var count: Int {
        return array.count - head
    }

    public mutating func enqueue(_ element: T) {
        array.append(element)
    }

    public mutating func dequeue() -> T? {
        guard head < array.count, let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if array.count > 50 && percentage > 0.25 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    public var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

배열의 요소를 빈 채로 놔둬야 하기 때문에 이 때의 배열은 T 형이 아닌 T? 형 객체를 담게 된다. 변수 head 는 배열의 가장 앞 요소의 인덱스를 담는다.

대부분의 새로운 기능들은 dequeue() 에 있다. 요소를 큐에서 제거할 때(dequeue) 첫 번째로 할 일은 배열에서 해당 객체를 없애기 위해 array[head] 를 nil 로 만드는 것이다. 그다음 head 를 증가시켜야 하는데, 앞의 요소가 삭제됨에 따라 뒤의 요소가 첫 번째 요소가 되기 때문이다.

아래와 같은 상태에서,

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
  head

다음과 같은 상태로 바뀌는 것이다.

[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
        head

이는 마치 슈퍼마켓에서 사람들이 계산대로 한칸씩 당겨져 오는 것이 아니라, 계산대가 한칸씩 큐를 타고 올라가는 것과 같다.

만약 앞의 빈 공간을 없애지 않으면 큐에 추가하고 삭제하는(enqueue, dequeue) 과정에서 배열의 크기는 계속 늘어날 것이다. 주기적으로 배열을 잘라내기 위해 다음과 같이 해야 한다.

let percentage = Double(head)/Double(array.count)
    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }

이는 전체 배열의 크기에서 빈 공간이 차지하는 비율을 퍼센트로 계산하는 부분이다. 배열의 25% 이상이 쓰이지 않으면, 낭비되는 그 공간을 잘라내버린다. 하지만 배열의 크기가 낭비되는 공간을 무시할만큼 작다면 크기 조정을 하지 않아도 되므로, 배열에 적어도 50개의 요소가 있어야만 배열을 잘라내도록 했다.

주의 : 위의 숫자는 순식간에 적어낸 것이다. 큐를 사용할 앱이나 환경에 따라서 이를 수정해야 할 수도 있다.

이를 플레이그라운드 상에서 테스트하고자 한다면 다음과 같이 하면 된다.

var q = Queue<String>()
q.array                   // [] 비어있는 배열

q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array             // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count             // 3

q.dequeue()         // "Ada"
q.array             // [nil, {Some "Steve"}, {Some "Tim"}]
q.count             // 2

q.dequeue()         // "Steve"
q.array             // [nil, nil, {Some "Tim"}]
q.count             // 1

q.enqueue("Grace")
q.array             // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count             // 2

여기서 잘라내는 행동을 테스트해보고 싶다면,

if array.count > 50 && percentage > 0.25 {

이 부분을 다음과 같이 바꾸면 된다.

if head > 2 {

이제 다른 요소를 큐에서 제거(dequeue)하면 배열은 다음과 같아질 것이다.

q.dequeue()         // "Tim"
q.array             // [{Some "Grace"}]
q.count             // 1

앞 부분의 nil 부분은 제거되고, 더이상 배열에 낭비되는 공간은 없다. 새로운 버전의 Queue 는 첫번째 것보다 크게 복잡하지 않으면서 큐에서 제거하는 것(dequeue) 또한 O(1) 만큼의 시간을 갖는다. 이는 우리가 배열을 어떻게 쓰는지에 대해 궁리한 결과이다.

참고하기

큐를 만드는 방법은 정말 많다. 대안으로 연결리스트(linked list), 원형 버퍼(circular buffer) 또는 힙이 있다.

이를 변형한 것에는 큐에 추가와 제거(enqueue, dequeue)를 양 끝에서 할 수 있는 덱(deque, double-ended queue)과, 가장 중요한 요소가 앞에 배치되는 정렬된 큐인 우선순위 큐(priority queue)가 있다.

출처

Written for Swift Algorithm Club by Matthijs Hollemans

댓글남기기

참고