###### 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 제공


- Mutability - 가변성 여부

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

- Usage

    // 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)에 가능