[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터1. 왜 자료구조와 알고리즘을 배워야할까요? 챕터2. 복잡도

 

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

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

 

---

 

 

섹션 1. 소개 Introduction

챕터1. 왜 자료구조와 알고리즘을 배워야할까요?

자료구조 연구는 효율성의 하나입니다. 특정 목표를 달성하기 위해 정해진 양을 저장하는 가장 좋은 방법은 무엇일가요?

 

프로그래머는 배열과 딕셔너리, 세트와 같이 콜렉션 타입을 정기적으로 사용합니다. 이것들은 데이터 콜렉션을 보유하는 자료구조로 각 구조에는 고유한 성능 특성이 있습니다.

 

예를 들어, 배열과 세트에 차이점을 고려해보세요. 둘 다 콜렉션이지만 세트에서 요소를 찾는 것보다 배열에서 찾는 것은 훨씬 더 오래 걸립니다. 반면에 배열의 요소는 순서를 정할 수 있지만 세트는 그러지 못합니다.

 

자료구조는 잘 연구된 분야로, 이 개념은 언어에 구애(language agnostic)받지 않습니다. C의 자료구조는 기능적으로나 개념적으로나 Swift와 같은 다른 언어와 동일합니다. 동시에 Swift의 고수준의 표현력은 성능을 희생하지않으면서도 이러한 핵심 개념을 익히는 데 이상적인 선택을 할 수 잇게 합니다.

 

반면 알고리즘은 작업을 수행하는 일련의 행위의 모음입니다. 데이터를 순서대로 정렬하는 정렬 알고리즘이 되거나 8K 사이즈의 사진을 다룰 수 있는 크기로 압축하는 알고리즘이 될 수도 있습니다. 알고리즘은 소프트웨어에 매우 필수적이며, 유용한 프로그램을 만들기 위한 블록으로써 만들어졌습니다.

 

그렇다면, 왜 자료구조와 알고리즘을 배워야 할까요?

 

면접

알고리즘 기술을 높이 유지해야 하는 가장 중요한 이유는 면접을 준비하기 위해서입니다. 대부분의 회사는 엔지니어의 능력을 시험하기 위해 최소 한두개의 알고리즘 질문을 합니다. 자료구조와 알고리즘에 대한 단단한 기초는 소프트웨어 엔지니어링의 기준이 됩니다.

 

업무

많은 데이터를 다룰 때 적절한 자료구조를 사용하는 것이 매우 중요합니다. 맞는 알고리즘을 사용하는 것은 소프트웨어의 성능과 확장성에 중요한 역할을 하게 됩니다. 모바일 앱의 반응성과 배터리 수명이 저욱 향상됩니다. 서버앱은 더 많은 동시 요청을 처리하고 더 적은 에너지를 사용하게 됩니다. 알고리즘에는 더 나은 소프트웨어를 구축하는데 활용하기 위한 정확성 증명(The proof of correctiveness)가 포함됩니다.

올바른 자료구조를 사용하는 것은 독자에게 컨텍스트를 제공하는데도 도움이 됩니다. 예를 들어 코드 베이스에서 Set을 발견할 수 있습니다. 그 즉시 여러분은 아래와 같은 사항을 추론할 수 있습니다.

1. Set을 사용하게 되면 요소에 대한 순서는 상관하지 않는다. Set은 정렬되지 않는 컬렉션이기 때문에.
2. Set은 또한 중복된 값이 없다. 사용자가 고유한 데이터로 작업하는 것을 가정할 수 있다.
3. Set은 Value Membership을 체크하기 적합하므로 엔지니어가 이러한 목적으로 도임한 것을 알 수 있다.

다양한 자료구조에 익숙해지면, 자료구조를 하나의 단서로써 사용하여 코드의 부가적인 맥락을 추출할 수 있게 됩니다. 이것은 소프트웨어가 어떻게 작동하는지 이해할 수 있도록 도와주는 강력한 스킬이 될 것입니다.

 

 

자기개발

까다로운 문제 해결을 위해 알고리즘이 사용하는 전략을 알게되면, 코드 개선을 위한 아이디어를 얻을 수 있습니다. Swift의 표준 라이브러리는 범용의 콜렉션 타입의 작은 세트가 있습니다. 이것들이 모든 경우를 다루지는 않습니다.

 

그리고, 앞으로 보게 되겠지만, 이러한 기본타입은 더욱 복잡하고 특별한 형태의 추상화를 구축하기 위한 훌륭한 출발점이 될 수 있습니다. 표준 배열과 딕셔너리 보다 더 많은 자료구조를 알게되면 앱을 구축하는 데 더 많은 도구의 콜렉션을 얻게 될 것입니다.

 

어느 현명한 사람이 말하길, 알고리즘을 연습하는 것은 음악가가 스케일을 연습하는 방법과 유사하다고 합니다. 기초가 더 다듬어질수록 더욱 복잡한 소프트웨어를 다루는 것이 나아질 것입니다.

 

이 책의 목표

이 책은 참고서이자 연습서입니다. raywenderlich.com의 다른 책에 익숙하하다면, 집에 있는 것처럼 느껴질 것입니다. 각 챕터는 몇가지 챌린지가 있는 짧은 챕터로 이어집니다. 각 챕터의 맨 마지막에서 챌린지의 해답을 볼 수 있습니다. 해답을 보기 전에 최대한 진지하게 문제해결을 하도록 노력해보세요.

이 책은 5개의 섹션으로 이루어져있습니다. 각각 아래와 같은 주제를 다루고 있습니다.

1. 소개
2. 자료구조 기본
3. 트리
4. 정렬
5. 그래프

이 책은 쓰여진 순서대로 읽는 것이 가장 좋지만, 참고용으로 건너뛰어도 괜찮습니다.

만약 알고리즘과 자료구조 공부가 처음이라면, 책의 일부 자료들이 어렵게 느껴질 수 있습니다. 하지만 끝까지 잘 따라온다면 Swift의 자료구조와 알고리즘 마스터가 되는 길을 잘 갈 수 있을 것입니다. 이제 시작하겠습니다.

 

---

 

챕터 2. 복잡도 Complexity

“규모가 커질까요?”

이 오래된 질문은 소프트웨어 개발의 설계단계에서 항상, 또 다양한 형태로 묻게 되는 질문입니다. 아키텍처 관점에서 확장성은 앱을 변경하는 것이 얼만나 쉬운가입니다. 데이터베이스 관점에서 확장성은 데이터베이스에서 데이터를 저장하고 검색(retrieve)하는 시간입니다.

 

알고리즘에서 확장성은 인풋의 사이즈가 커질수록 알고리즘의 실행시간과 메모리 사용 측면에서 알고리즘이 수행하는 방식을 일컫습니다.

 

적은 양의 데이터로 수행할 경우, 비싼 알고리즘은 빠르게 느껴질 수 있지만, 데이터의 양이 증가할 수록 비싼 알고리즘은 장애(crippling)가 됩니다. 얼마나 나빠질 수 있을까요? 정량적으로 측정하는 법을 이해하는 것은 여러분이 알아야 될 중요한 기술입니다.

이번 챕터에서는 Big O 표기법에 대해서 행시간과 메모리 사용량이라는 두 차원의 다른 확장성 레벨에서 살펴볼 것입니다.

 

시간 복잡도 Time Complexity

적은 양의 데이터에서는 가장 비싼 알고리즘이더라도 요즘의 하드웨어 속도로 인해 빠르게 보일 수 있습니다. 하지만 데이터가 증가할 수록 비싼 알고리즘의 비용은 명백하게 증가할 것입니다. 시간 복잡도는 인풋 사이즈가 증가할 수록 알고리즘을 실행하는 데 걸리는 시간을 측정하는 것입니다. 이번 섹션에서 가장 일반적인 타입 복잡도에 대해 알아보고 이를 식별하는 방법을 배웁니다.

 

상수시간 Constant time

상수시간 알고리즘은 인풋의 사이즈와 상관없이 수행 시간이 동일한 알고리즘입니다. 아래 코드를 살펴보세요.

 

func checkFirst(names: [String]) {
  if let first = names.first {
    print(first)
  } else {
    print("no names")
  }
}

names 배열의 사이즈는 이 함수의 실행시간에 영향을 미치지 못합니다. 인풋이 10든, 1천만개가 되든, 이 함수는 오직 배열의 첫번째 요소만 검사합니다. 여기 시간 복잡도를 시각화한, 시간과 데이터 사이즈의 그래프입니다.

 

인풋 데이터가 증가해도 알고리즘이 수행하는 시간은 변하지 않습니다.

간결함을 위해서, 프로그래머는 Bit O 표기법을 이용하여 다양한 규모의 시간복잡도를 나타냅니다. 상수시간의 Big O 표기법은 O(1)입니다.

 

선형시간 Linear time

아래 코드를 한 번 봅시다.

func printNames(names: [String]) {
  for name in names {
    print(name)
  }
}

이 함수는 String 배열 안에 있는 모든 이름을 출력합니다. 인풋 배열의 사이즈가 증가할수록, for 반복분의 반복횟수도 같은 양으로 증가합니다. 이를 선형시간 복잡도라고 합니다.

 

 

선형시간 복잡도는 이해하기 가장 쉽습니다. 데이터의 양이 늘어나면 실행시간도 같은 양으로 늘어납니다. 위에 선형 그래프는 이를 나타냅니다. Bit O 표기법으로 선형시간은 O(n) 입니다.

모든 데이터에 대해 2개의 반복문이 있고, 여섯개의 O(1) 메서드를 호출하는 함수는 O(2n + 6)일까요?

시간 복잡도는 높은 수준의 성능 형태만 제공합니다. 때문에 정해진 횟수만큼 반복되는 것은 계산에 포함되지 않습니다. 모든 상수는 최종 Big O 표기법에서 삭제됩니다. 즉, O(2n+6)은 놀랍게도 O(n)과 동일합니다.이 책의 주요 관심사는 아니지만, 절대적인 효율성을 최적화하는 것도 중요합니다. 회사들은 Big O 표기법에서 무시되는 상수의 기울기를 줄이기 위해 수백만 달러의 R&D에 투자합니다. 예를 들어 GPU의 최적화된 버전의 알고리즘은 기본 CPU의 버전보다 100배 더 빠르게 작동하지만, 여전히 O(n)을 유지합니다. 우리는 이러한 종류의 최적화와 속도향상에 대해서는 무시하고 진행할 것입니다.

 

평방시간(2차시간) Quadratic time

더 일반적으로는 n 제곱이라고 하는 이 시간 복잡도는 인풋 사이즈의 제곱에 비례하는 시간이 걸립니다. 아래 코드를 살펴보세요.

func printNames(names: [String]) {
  for _ in names {
    for name in names {
      print(name)
    }
  }
}

이번에는 함수가 배열에 있는 모든 이름 배열에 대한 이름을 출력합니다. 만약 10개의 데이터가 있는 배열이라면 10개의 이름이 있는 전체목록을 10번씩 출력할 것입니다. 100개의 출력문이 되는 것입니다.

 

만약 인풋 사이즈가 하나 증가하면, 11개의 이름을 11번 출력하고, 121개의 출력문이 나오게 됩니다. 선형시간 동안 수행되는 이전 함수와 다르게, n 제곱 알고리즘은 데이터 사이즈가 증가할 수록 더 빠르게 통제를 잃을 수 있습니다.

 

이를 나타내는 그래프는 아래와 같습니다.

 

인풋 데이터의 사이즈가 증가할 수록, 알고리즘을 수행하는 시간은 급격하게 증가합니다. 때문에 n 제곱 알고리즘은 규모에 따라 잘 수행되지 않습니다.

Big O 표기법으로 2차시간은 O(n²) 입니다.

선형 시간 O(n) 알고리즘이 아무리 비효율적으로 쓰였더라도, (다중 패스 등) 충분히 큰 n에 대해서 선형 알고리즘은 최적화된 2차시간 알고리즘보다 빠릅니다. 언제나.

 

로그 시간 Logarithmic time

여태까지 우리는 인풋의 모든 요소가 최소 한번씩 검사되는 선형복잡도와 2차시간 복잡도에 대해 배웠습니다. 그러나 인풋의 서브셋만 검사하는 시나리오도 있습니다. 실행시간이 더 빠르고요.

 

이러한 카테고리에 속하는 시간복잡도 알고리즘은 입력 데이터에 대해 몇가지 가정을 함으로써 몇가지 지름길을 활용할 수 있는 알고리즘입니다. 예를 들어 정렬된 정수 배열이 있다면, 특정값이 있는지 확인하는 가장 빠른 방법은 무엇일가요?

 

가장 단순한 솔루션은 결론에 도달하기 전까지 처음부터 끝까지 배열의 모든 요소를 검사하는 것입니다. 모든 요소를 한 번씩 검사한다면 O(n) 알고리즘이 될 것입니다. 선형시간 알고리즘도 물론 좋지만 더 잘할 수 있습니다. 인풋 배열이 정렬되어 있다면, 최적화할 수 있는 방법이 있습니다. 아래 코드를 살펴보세요.

 

let numbers = [1, 3, 56, 66, 68, 80, 99, 105, 450]

func naiveContains(_ value: Int, in array: [Int]) -> Bool {
  for element in array {
    if element == value {
      return true
    }
  }

  return false
}

숫자 451이 있는지 찾기 위해서는, 단순한 알고리즘에서는 처음부터 끝까지 반복하는 것입니다. 9개의 값이 있는 배열에서는 9번의 검사가 이루어질 것입니다. 하지만 배열이 정렬되어 있다면 중간값을 검사해서 필요에 따라 값의 절반을 삭제할 수 있습니다.

 

func naiveContains(_ value: Int, in array: [Int]) -> Bool {
  guard !array.isEmpty else { return false }
  let middleIndex = array.count / 2

  if value <= array[middleIndex] {
    for index in 0...middleIndex {
      if array[index] == value {
        return true
      }
    }
  } else {
    for index in middleIndex..<array.count {
      if array[index] == value {
        return true
      }
    }
  }

  return false
}

위 함수는 결론까지 가기 위해 배열의 절반만을 검사하는 작지만 의미있는 최적화를 거쳤습니다.

 

이 알고리즘은 맨 처음으로 원하는 값과 배열의 중간값을 체크합니다. 만약 중간값이 원하는 값보다 크다면 알고리즘은 배열의 오른쪽 값을 살펴보지 않습니다. 배열이 정렬되어 있기 때문에 중간 값의 오른쪽 값들은 커질 뿐입니다.

 

반면에, 중간 값이 찾는 값보다 작다면 알고리즘은 배열의 왼쪽 값을 확인하지 않습니다. 이는 비교횟수를 절반으로 줄이는, 작지만 의미있는 최적화입니다.

 

이 방법을 통해 이 최적화를 반복으로 수행한다면 어떨까요? 챕터 20에서 다루는 “이진 탐색 Binary Search”에서 살펴볼 수 있습니다.

필요한 비교를 반복적으로, 절반으로 낮추는 알고리즘은 로그 시간 복잡도를 가집니다. 아래 그래프는 인풋 데이터가 증가할수록 로그 시간 알고리즘이 어떻게 수행되는지 보여줍니다.

 

인풋 데이터가 증가해도 알고리즘을 실행하는 시간은 적은 비율로 증가합니다. 자세히 보면 위 그래프는 점근적인 모양새를 나타내고 있습니다.

💡 역주 : https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

 

수행해야되는 비교횟수를 절반으로 줄이는 것의 영향을 고려하여 설명할 수 있습니다.

인풋 사이즈가 100일 경우, 비교횟수를 50번 아낄 수 있습니다. 만약 인풋 사이즈가 10만일 경우 비교횟수로 5만을 아낄 수 있습니다. 더 많은 데이터가 있을수록, 반감효과도 커집니다. 때문에 위 그래프가 수평에 가까워지는 것을 볼 수 있습니다.

 

이런 종류의 알고리즘은 매우 없지만, 사용되는 경우 매우 강력합니다. 로그시간 알고리즘의 Big O 표기법은 O(log n) 입니다.

로그 밑이 2인가요? 10인가요? 아니면 자연로그인가요?

위의 예제에서는 로그 밑이 2입니다. 그러나 Big O 표기법은 성능의 형태에만 초점을 맞추기 때문에, 로그의 실제 밑은 신경쓰지 않습니다.

 

유사 선형 시간(준선형시간) Quasilinear time

여러분이 만나볼 또 다른 시간 복잡도는 유사선형 시간입니다. 유사선형 시간 알고리즘은 선형시간보다 성능이 나쁩니다. 하지만 평방 시간보다는 극적으로 좋습니다. 이는 여러분이 다루게 될 가장 일반적인 알고리즘 중 하나입니다. 유사 선형시간의 한 예로는 Swift의 sort 메서드가 있습니다.

 

유사선형시간의 Big O 표기법은 O(n log n) 입니다. 선형시간과 로그시간 알고리즘을 곱한 형태입니다. 때문에 유사 선형시간은 로그 시간과 선형시간 사이에 딱 맞습니다. 선형시간보다 성능이 나쁘지만 앞으로 보게 될 많은 다른 복잡도보다는 낫습니다. 그래프는 아래와 같습니다.

 

 

유사선형시간 복잡도는 평방 시간 복잡도와 유사한 형태의 곡선을 공유합니다. 하지만 그렇게 빠르게 올라가지 않으므로 대규모의 데이터를 다루는 데 더욱 탄력적입니다.

 

다른 시간복잡도 Other time complexities

여태까지 만난 5개의 시간복잡도가 책에서 다룰 시간복잡도입니다. 다항식 시간(Polynomial Time), 지수 시간(Exponential Time), 계승 시간(Factorial Time) 등, 다른 시간 복잡도들도 있지만, 훨씬 덜 일반적이고 이 책에서는 논의되지 않은 더 복잡한 문제들을 다루고 있습니다.

 

중요한 것은, 시간 복잡도가 성능에 대한 높은 수준의 대요이며, 일반적인 순위체계를 넘는 알고리즘을 속도로 판단하지 않는다는 것입니다. 이 말은, 두 알고리즘이 동일한 시간복잡도를 가지더라도 하나가 다른 하나보다 월등히 빠를 수 있다는 것입니다. 또한, 작은 데이터 세트에서 시간 복잡도는 실제 속도를 측정하는 데 정확하지 않을 수 있습니다.

 

예를 들어, 삽입 정렬과 같은 평방시간 알고리즘은 병합정렬과 같은 유사선형 알고리즘보다 빠를 수 있습니다. 그 이유는 삽입 정렬은 알고리즘을 수행하는데 추가적인 메모리 할당이 필요하지 않기 때문입니다. 반면 병합 정렬은 여러 배열을 할당해야 합니다. 작은 데이터세트에서 메모리 할당은 알고리즘이 건드리는 요소의 수와 관련하여 비싸질 수 있습니다.

 

시간복잡도 비교 Comparing time complexity

1부터 n까지 합을 찾는 아래와 같은 코드를 작성한다고 합시다.

func sumFromOne(upto n: Int) -> Int {
  var result = 0
  for i in 1...n {
    result += i
  }
  return result
}

sumFromOne(upto: 10000)

 

위 코드는 1만번 반복하고 값 50005000을 반환할 것입니다. O(n)입니다. 반복문과 출력결과를 인쇄하므로 플레이그라운드에서 실행하는 데 시간이 좀 걸릴 것입니다.

 

여기 다른 버전의 코드가 있습니다.

func sumFromOne(upto n: Int) -> Int {
  (1...n).reduce(0, +)
}
sumFromOne(upto: 10000)

이 코드는 플레이그라운드에서 더 빨리 돌아갈 것입니다. 왜냐하면 이 코드는 표준 라이브러리에서 컴파일된 코드를 불러오기 때문입니다.

하지만 만약 시간복잡도를 줄이고자 한다면, 위 코드 역시 + 메소드를 n번 호출한다는 점에서 O(n) 임을 알게될 것입니다. 두 코드 Big O 표기법이 동일하지만 위 코드는 이미 컴파일된 코드이기 때문에, 더 작은 상수를 가지고 있습니다.

 

최종적으로 아래와 같이 작성할 수 있습니다.

 

func sumFromOne(upto n: Int) -> Int {
  (n + 1) * n / 2
}
sumFromOne(upto: 10000)

 

이 버전의 함수는 프레드릭 가우스(Fredrick Gauss)가 초등학교때 알아차린 트릭을 사용합니다. 즉 여러분은 단순한 산술로 이 모든 덧셈을 계산할 수 있게 됩니다. 이 버전의 알고리즘은 O(1) 으로 어떤 알고리즘도 이길 수 없습니다. 상수시간 알고리즘은 언제나 가장 선호됩니다. 이 버전을 반복문 안에 넣을 경우, 선형시간으로 끝나지만 이전의 O(n) 버전은 느린 평방시간의 하나의 외부 반복문(just one outer loop away)이 될 것입니다.

 

---

공간복잡도 Space complexity

알고리즘의 시간복잡도는 확장성을 예측하는데 도움이 되지만, 유일한 지표는 아닙니다. 공간복잡도는 알고리즘이 실행되는 데 필요한 자원을 측정하는 방법으로, 컴퓨터 상에서 알고리즘을 위한 자원은 바로 메모리가 됩니다. 아래 코드를 살펴보세요.

 

func printSorted(_ array: [Int]) {
  let sorted = array.sorted()
  for element in sorted {
    print(element)
  }
}

 

위 함수는 정렬된 복사본을 만들어 출력하는 함수입니다. 공간 복잡도를 계산하기 위해서는 해당 함수의 메모리 할당을 분석하게 됩니다.

array.sorted() 메서드가 array 와 동일한 사이즈의 새 배열을 만드므로, printSorted  의 공간복잡도는 O(n)이 됩니다. 이 함수도 물론 간단하고 우아하지만, 메모리를 가능한 적게 할당하고 싶은 상황이 생길수도 있습니다. 이 때 위 함수를 아래처럼 수정할 수 있을 것입니다.

 

func printSorted(_ array: [Int]) {
  // 1
  guard !array.isEmpty else { return }

  // 2
  var currentCount = 0
  var minValue = Int.min

  // 3
  for value in array {
    if value == minValue {
      print(value)
      currentCount += 1
    }
  }

  while currentCount < array.count {

    // 4
    var currentValue = array.max()!

    for value in array {
      if value < currentValue && value > minValue {
        currentValue = value
      }
    }

    // 5
    for value in array {
      if value == currentValue {
        print(value)
        currentCount += 1
      }
    }

    // 6
    minValue = currentValue
  }
}

위에서 구현한 코드는 공간제약을 염두하였습니다. 목표는 배열을 여러번 반복하고, 각 반복에서 가장 작은 값을 출력하는 것입니다.

이 알고리즘이 하는 일은 다음과 같습니다.

1. 만약 배열이 비었을 경우를 체크합니다. 비었다면 아무것도 출력하지 않습니다.
2. currentCount 는 출력문의 숫자를 추적하고, minValue 는 마지막으로 출력한 값을 저장합니다.
3. 알고리즘은 minValue 에 일치하는 모든 값을 출력하고, 출력문의 숫자에 따라 currentCount 의 값을 업데이트합니다.
4. while 반복문에서, 알고리즘은 minValue 보다는 큰, 가장 작은 값을 찾고, 이를 currentValue 에 저장합니다.
5. currentCount를 업데이트 하면서 배열 내부의 모든 currentValue 값을 출력합니다.
6. minValue 가 currentValue 로 세팅되면 다음 반복에서는 그 다음 최소값을 찾습니다.

위 알고리즘은 적은 수의 변수를 추적하기 위한 메모리만 할당합니다. 때문에 공간복잡도는 O(1)이 됩니다. 소스배열의 정렬된 형태를 만들기 위해 배열 전체를 할당하는 이전 함수와 대조적이 됩니다.

 

 

---

다른 표기법 Other notations

이제까지 Big O 표기법을 사용하여 알고리즘을 측정하였습니다. 현재까지 프로그래머들이 측정할 때 사용하는 가장 일반적인 측정법입니다. 하지만 이외에도 다른 표기법이 존재합니다.

Big Omega 표기법은 알고리즘의 최상의 실행시간을 측정하는데 사용합니다. 최상의 케이스를 찾는 것이 때로 쉽지 않기 때문에 Big O 표기법만큼 유용하지는 않습니다.

Big Theta 표기법은 최상의 경우와 최악의 경우가 같을 경우 런타임을 측정하는데 사용됩니다.

 

 

플레이그라운드 행기반 실행 버그 Playground line-based execution bug

이 책에서는 플레이그라운드를 광범위하게 사용합니다. 특정 조건하에서 Xcode13에서 행 기반 실행이 잘못 비활성화하는 것을 발견할 수 있습니다. 그럴 경우, 플레이그라운드 창 하단에 위치한 실행제어 (execution control) 버튼을 눌러서 전체 플레이그라운드를 실행시키면 됩니다.

 

 

핵심 요약 Key points

• 시간복잡도는 인풋 사이즈가 증가할수록, 알고리즘을 실행하는데 필요한 시간을 측정하는 기법입니다.
• 상수시간, 로그시간, 선형시간, 유사선형시간, 평방시간을 알고 이를 비용순으로 정렬할 수 있어야합니다.
• 공간복잡도는 알고리즘을 수행하는데 필요한 자원을 측정하는 기법입니다.
• Big 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. 연결리스트 도전

 

 

---

마치며 

 

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

 

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

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

 

감사합니다.