---
# System prepended metadata

title: Day03-학습정리
tags: [2020 Boostcamp]

---

###### tags: `2020 Boostcamp`
# Day03-학습정리

## 스스로 확인할 사항

- **Big-O 표기법을 포함해서 여러 가지 복잡도에 대해 학습하고 정리한다.**

  - 알고리즘: 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미
  - 시간 복잡도: 알고리즘이 문제를 해결하기 위한 시간(연산의 횟수) 의미
  - 공간 복잡도: 알고리즘이 문제를 해결하기 위해 사용하는 메모리 양
  - Asymptotic notation (점근적 표기법): 입력값의 크기에 따른 함수의 증가량 즉 성장률
    - Big-Ω (오메가 표기법): 최상의 경우 - Upper Bound
    - Big-θ (세타 표기법): 평균의 경우 - 빅오메가와 빅오의 교집합
    - Big-O(빅오 표기법): 최악의 경우 - Lower Bound
      1. O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함
      2. O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
      3. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐
      4. O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가짐 (선형로그형)
      5.  O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
      6. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱

- **연속 배열과 링크드 리스트의 차이점에 대해 이해하고, 언제 사용하는 것이 더 효율적인지 비교해서 정리한다.**

  |           |                   Array                   |                       Linked-List                        |
  | --------- | :---------------------------------------: | :------------------------------------------------------: |
  | 구조      | 논리적 저장순서와 물리적 저장 순서가 일치 | 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조 |
  | 삽입/삭제 |                   O(N)                    |                           O(N)                           |
  | 접근      |                   O(1)                    |                           O(N)                           |
  | 메모리    |   Stack에 할당(정적할당 - Compile time)   |             Heap에 할당(동적할당 - Run time)             |
  | 사이즈    |                  Static                   |                         Dynamic                          |

  * 삽입과 삭제 빈번할 때: Linked-List
  * 데이터 접근이 빈번할 때: Array

- **본인이 작성한 리스트에 추가할 때 시간 복잡도는 어떠한가? 더 개선할 부분이 있는가?**

  - head와 tail 추가 시 O(1), 나머지 경우 O(N)
  - 최적이다

- **본인이 작성한 리스트에서 삭제할 때 시간 복잡도는 어떠한가? 더 개선할 부분이 있는가?**

  - head 삭제 시 O(1), 나머지 경우 O(N)
  - 파라미터로 넘어온 id값을 비교하며 탐색해야 하므로 최적이다

- **본인이 작성한 리스트에서 탐색할 때 시간 복잡도는 어떠한가? 더 개선할 부분이 있는가?**

  - O(N)으로 최적이다

## 다같이 확인할 사항

- **자신이 사용하는 언어와 프레임워크에서는 배열과 리스트를 각각 어떻게 활용하고 있는지 정리한다.**

  - Swift Collection type: Array, Set, Dictionary 제공

    ![](https://i.imgur.com/vHSXL52.png)

  - Mutability - 가변성 여부

    - var - 배열의 크기, 원소가 변할 수 있다
    - let - 배열의 크기, 원소 변할 수 없다

  - Usage

    ```swift
    // A mutable array of Strings, initially empty.
    var arrayOfStrings: [String] = []
    var arrayOfStrings = [String]()  
    var arrayOfStrings = Array<String>()
    
    // Create an immutable array of type [Int] containing 2, 4, and 7
    let arrayOfInts = [2, 4, 7]
    
    // An immutable array of type [String], containing ["Example", "Example", "Example"]
    let arrayOfStrings = Array(repeating: "Example",count: 3)
    ```

  - Copy-on-write

    - 배열 a를 배열 b로 할당할 때 바로 할당되는 것이 아니라 두 값중 하나가 변경될 때 할당된다

- **Queue에 대해 학습하고 링크드 리스트로 구현한다면 어떻게 구현할 수 있는지 설계한다.**

  - Queue: 먼저 넣은 데이터가 먼저 나오는 FIFO 구조의 저장 형식
    - push(): queue에 원소를 추가한다 - linkedlist의 tail에 원소 추가 (O(1))
    - pop(): queue의 front 원소를 꺼내고 queue에서 삭제한다 - linkedlist의 head를 삭제하고 value 반환 (O(1))

- **Deque에 대해 학습하고 링크드 리스트로 구현한다면 어떻게 구현할 수 있는지 설계한다.**

  - Deque: 양쪽 끝에서 삽입 삭제가 모두 가능한 자료구조
    - push_front(), push_back(): 앞이나 뒤에 원소를 추가한다
    - pop_front(), pop_back(): 앞이나 뒤 원소를 꺼내고 deque에서 삭제한다
    - Double linked list로 구현하면 모든 기능 O(1)에 가능

