[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터4~5. 스택, 스택 도전과제

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터4~5. 스택, 스택 도전과제

Raywenderlich.com 에서 나온 Data Structures & Algorithms in Swift 책의 데모 공개본을 번역하였습니다. 즐겁게 봐주세요. 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift

 

 

 

---

 

섹션 2. 기초 자료구조 Elementary Data Structure

챕터 4. 스택 Stacks 

스택은 어느 곳에도 있습니다. 스택이 있는 일반적인 예시를 들어보겠습니다.

• 팬케익
• 책들
• 종이
• 지폐

스택 stack 자료구조는 개념적으로 객체의 물리적 스택과 동일합니다. 어떤 항목을 스택에 넣으면 스택의 맨 위에 놓이게 됩니다. 스택의 어떤 항목을 제거한다면 항상 가장 위에 있는 항목이 제거됩니다.

좋은 소식: 팬케이크가 쌓인 스택, 나쁜 소식: 가장 위에 있는 팬케이크만 먹을 수 있다는 것.

 

---

 

스택의 작업 Stack operations

스택은 유용하고 또 너무나 간단합니다. 스택을 구축하는 주요 목표는 데이터를 접근하는 방법을 적용하는 것입니다.

스택에는 두 가지의 필수 작업만 있습니다.

• 푸시 push: 스택의 최상단에 요소 추가하기
• 팝 pop: 스택의 최상단 요소를 제거하기

인터페이스를 이 두가지 작업으로 제한하는 것은 자료구조의 한 방향에서만 추가하거나 제거할 수 있다는 것입니다. 컴퓨터 과학에서 스택은 LIFO(후입선출) 자료구조로도 알려져 있습니다. 가장 마지막에 푸시Push 된 요소가 가장 먼저 팝Pop 되어 나가집니다.

스택은 프로그래밍 전 분야에서 두드러지게 사용됩니다. 몇 가지를 나열하자면,

• iOS는 네비게이션 스택을 사용하여 뷰컨트롤러를 뷰 안팎으로 푸시하거나 팝합니다.
• 메모리 할당은 아키텍처레벨에서 스택을 사용합니다. 지역변수를 저장하는 메모리도 스택을 사용하여 관리합니다.
• 미로에서 길을 찾는 것과 같은 분할 정복 알고리즘(Search and conquer algorithms)에서 스택을 사용하여 역추적을 편리하게 합니다.

구현 Implementation

이 챕터의 스타터 플레이그라운드를 열고, 플레이그라운드의 Source 폴더에 Stack.swift 라는 파일을 만듭니다. 파일 안에 아래 코드를 작성합니다.

 

public struct Stack<Element> {

  private var storage: [Element] = []

  public init() { }
}

extension Stack: CustomDebugStringConvertible {

  public var debugDescription: String {
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

 

위에 스택의 백업 스토리지(backing storage)를 정의하였습니다. 스택에 적합한 스토리지 유형을 선택하는 것은 매우 중요합니다. 배열은 append 와 popLast 를 이용하여 한쪽 끝에서 상수시간의 삽입과 삭제가 이루어지므로 확실한 선택입니다. 이 두 가지 작업을 사용하면 스택의 후입선출 특성이 더욱 용이해집니다.

CustomDebugStringConvertible 프로토콜에 필요한 debugDescription 의 함수 호출 체인을 위해서 3가지 작업을 해야합니다.

1. storage.map { "\\($0)" } 로 문자열에 매핑하는 배열 만들기
2. reversed() 를 이용하여 이전 배열을 뒤집는 새로운 배열을 만들기
3. joined(separator:) 를 이용하여 배열을 문자열로 병합. "\\n" 개행문자를 이용하여 배열의 요소를 분리

이렇게 해서 디버깅에 사용할 수 있는 출력가능한 Stack 타입의 표현이 생성됩니다.

 

푸시와 팝 작업 push and pop operations

Stack에 아래 두가지 작업을 추가하세요

 

public mutating func push(_ element: Element) {
  storage.append(element)
}

@discardableResult
public mutating func pop() -> Element? {
  storage.popLast()
}

매우 간단하죠! 플레이그라운드에서 아래 코드를 작성합니다.

 

example(of: "using a stack") {
  var stack = Stack<Int>()
  stack.push(1)
  stack.push(2)
  stack.push(3)
  stack.push(4)

  print(stack)

  if let poppedElement = stack.pop() {
    assert(4 == poppedElement)
    print("Popped: \(poppedElement)")
  }
}

아래와 같이 출력되어야 합니다.

 

---Example of using a stack---
----top----
4
3
2
1
-----------
Popped: 4

push 와 pop 은 둘 다 시간복잡도가 O(1) 입니다.

 

비필수 작업 Non-essential operations

스택을 더 쉽게 사용할 수 있는 유용한 작업들이 있습니다.  Stack.swift 안에 아래 코드를 Stack에 추가하세요.

 

public func peek() -> Element? {
 storage.last
}

public var isEmpty: Bool {
  peek() == nil
}

스택 인터페이스에는 종종 peek 작업이 포함됩니다. peek 은 안의 콘텐츠를 변경하지 않고 스택의 상단 요소를 살펴보는 것입니다.

 

 

적을수록 좋습니다 Less is more

스택에 스위프트 콜렉션 프로토콜을 적용할 수 있을지 궁금할 것입니다. 스택의 목적은 데이터에 접근하는 방법의 가짓수를 제한하는 것입니다. Collection 과 같은 프로토콜을 채택하는 것은 반복자(iterator)와 아래첨자(subscript)를 통해 모든 요소를 노출하므로 스택의 목적에 반하는 것입니다. 이 경우에는 더 적은 것이 좋습니다.

 

접근 순서를 보장하기 위해 기존의 배열을 취해서 스택으로 변환하고 싶을 수 있습니다. 당연히 모든 배열 요소를 반복하여 각 요소를 push 하는 것은 가능합니다.

 

 private 저장소를 설정하는 생성자를 작성할 수 있으므로, 아래 코드를 스택 구현에 추가합니다.

 

public init(_ elements: [Element]) {
  storage = elements
}

 

아래 예제를 메인 플레이그라운드에 추가합니다.

 

example(of: "initializing a stack from an array") {
  let array = ["A", "B", "C", "D"]
  var stack = Stack(array)
  print(stack)
  stack.pop()
}

 

위 코드는 문자열 스택을 생성하고 최상단 요소 “D”를 내보냅니다. 스위프트 컴파일러는 배열로부터 요소의 타입을 추론할 수 있으므로 Stack<String> 대신에 Stack 을 사용할 수 있습니다.

 

한 단계 더 나아가 배열 리터럴을 통해 스택을 초기화할 수 있도록 만들 수 있습니다. 아래를 스택 구현 시 추가하세요.

 

extension Stack: ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: Element...) {
    storage = elements
  }
}

메인 플레이그라운드로 돌아가 아래 코드를 추가합니다.

 

example(of: "initializing a stack from an array literal") {
  var stack: Stack = [1.0, 2.0, 3.0, 4.0]
  print(stack)
  stack.pop()
}

위 코드는 Double 스택을 생성하고 최상단 값 4.0을 내보냅니다. 다시 말하자면 타입추론을 통해 Stack<Double> 를 입력하지 않아도 됩니다.

 

스택은 트리와 그래프를 검색search하는 문제에 매우 중요합니다. 미로에서 길을 찾는 것을 상상해보세요. 왼쪽, 오른쪽, 직진을 선택해야될 때마다 할 수 있는 모든 결정을 스택에 저장할 수 있습니다. 막다른 골목에 도달하면 스택에서 마지막 결정을 내보냄(pop)으로써 역추적할 수 있고, 다른 막다른 골목에 도달하거나 탈출하기 전까지 이를 계속할 수 있습니다.

 

 

 

핵심 요약 Key points

• 스택은 LIFO, 후입선출 자료구조이다.
• 매우 단순하지만 스택은 많은 문제들의 핵심 자료구조이다.
• 스택의 두가지 필수 작업으료, 요소를 추가하는 push 메서드와 요소를 제거하는 pop 메서드가 있다.

 

 

---

챕터 5. 스택 도전과제 Stack Challenges

스택은 놀라울 정도로 많은 어플리케이션이 있는 단순한 자료구조입니다.

starter 프로젝트를 열어서 아래 도전과제들을 확인할 수 있습니다.

첫번째 도전과제: 배열 반전 Reverse an Array

스택을 사용하여 배열의 요소를 역순으로 출력하는 함수를 만드세요.

두번째 도전과제: 괄호 짝 확인하기 Balance the parentheses

괄호의 짝이 맞는지 확인합니다. 주어진 문자열에서  ( 와 ) 가 있는지 확인하고, 짝이 맞으면 true 을 반환합니다.

 

// 1
h((e))llo(world)() // balanced parentheses

// 2
(hello world // unbalanced parentheses

 

해결책 Solutions

도전과제 1 해결책

스택의 주 이용 사례 중 하나는 역추적을 용이하게 하는 것입니다. 값들의 시퀀스를 스택에 푸시하고, 순차적으로 팝하면 값들을 역순으로 얻게됩니다.

 

func printInReverse<T>(_ array: [T]) {
  var stack = Stack<T>()

  for value in array {
    stack.push(value)
  }

  while let value = stack.pop() {
    print(value)
  }
}

노드를 스택에 푸시하면 시간복잡도는 O(n) 입니다. 스택의 요소를 팝하여 값을 출력하는 것 역시 O(n) 입니다. 최종적으로 위 알고리즘의 시간 복잡도는 O(n) 이 됩니다.

 

스택 컨테이너를 함수 안에 할당하였으므로 공간복잡도 비용으로도 O(n) 이 듭니다.

 

📌 메모: 표준 라이브러리에서 제공하는 reversed() 메서드를 호출하여 배열을 반전할 수 있습니다. 배열에서 이 메서드는 O(1) 의 시간과 공간복잡도입니다. 왜냐하면 원본 콜렉션에서 반전된 뷰만 생성하기 때문입니다. 만약 아이템을 순회하고 모든 요소를 출력하면 시간복잡도는 O(n)이 되고 그 동안 공간복잡도는 O(1)이 됩니다.

 

도전과제 2 해결책

문자열에서 괄호의 짝이 맞는지 확인하기 위해서, 문자열의 각 문자를 확인해야 합니다. 여는 괄호를 만나면 스택에 푸시하고, 반대로 닫는 괄호를 만나면 스택을 팝합니다.

 

코드는 아래와 같습니다.

 

func checkParentheses(_ string: String) -> Bool {
  var stack = Stack<Character>()

  for character in string {
    if character == "(" {
      stack.push(character)
    } else if character == ")" {
      if stack.isEmpty {
        return false
      } else {
        stack.pop()
      }
    }
  }
  return stack.isEmpty

 

위 알고리즘의 시간복잡도는 O(n) 입니다. 여기서 n은 문자열 내의 문자 갯수입니다. 이 알고리즘은 Stack 자료구조의 사용으로 O(n) 의 공간복잡도가 발생합니다.

 

 

 

 

 

---

🔗 번역 시리즈 링크

0️⃣ 섹션 0. 시작하기전에

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 0. 시작하기 전에

1️⃣ 섹션 1. 소개 Introduction

> 챕터 1.왜 자료구조와 알고리즘을 배워야할까요? / 챕터 2. 복잡도  Complexity

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터1. 왜 자료구조와 알고리즘을

> 챕터3. 스위프트 표준 라이브러리 Swift Standard Library

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터3. 스위프트 표준 라이브러리 S

 

1️⃣ 섹션 2. 기초 자료구조 Elementary Data Structure

> 챕터 4. 스택 Stacks /  챕터 5. 스택 도전과제 Stack Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터4~5. 스택, 스택 도전

> 챕터 6-1. 연결리스트 Linked List (연결리스트 정의, 요소 추가, 삭제)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-1. 연결리스트 (정

> 챕터 6-2. 연결리스트 Linked List (스위프트 표준 라이브러리의 콜렉션 프로토콜, 카우 Copy-On-Write,  밸류 시맨틱)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-2. 연결리스트

 

> 챕터 7. 연결리스트 도전과제 Linked List Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터7. 연결리스트 도전

 

---

마치며 

 

오늘도 읽어주셔서 감사합니다.

 

궁금한 점이 있다면 댓글로, 도움이 되셨다면 공감 부탁드립니다.

혹시 수정하거나 피드백하실  내용 있다면 언제든 댓글로 부탁드립니다.

 

감사합니다.