1. 자료구조 기초

0. 자료구조란

자료(데이터)를 어디에 어떻게 관리(검색, 순회(iterate), 저장, 삭제, 변경) 할지

자료를 담는 추상적인 틀

데이터의 형태와 쓰임에 가장 적합한 자료구조를 사용해야 컴퓨터의 자원을 효율적으로 사용 가능하다.

각 자료구조의 특징 / 장점 / 한계를 파악해야한다.

 

  * 알고리즘 : 어떤 문제를 풀기 위한 동작의 절차 Input 값을 통해 Output의 결과를 내는 것

---

1. 빅오 표기법 (자료구조, 알고리즘을 비교한다)

자료구조 또는 알고리즘이 문제를 해결하기 위한 가장 상한(최악)의 시간을 기준으로 한다.

- 가장 큰 영향력이 있는 항만 표시

- 상수항은 무시

 

2. 시간 복잡도(데이터 처리에 소요되는 시간)

 

O(1) : 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘

           (배열의 Random Access, Hash)

 

O(N) : 입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘

            (for 문)

 

O(N2) : 입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘

            (이중 for 문)

 

O(logN) : 이진탐색(Binary Search)

 

O(NlogN) : Merge Sort