자료구조란?

• 메모리를 효율적으로 사용하면서 데이터를 빠르고 안정적으로 처리하는 것이 목표
• 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있음 ⇒ 상황에 맞는 올바른 자료구조를 선택해야함
• 즉, 자료구조는 일차원인 컴퓨터 메모리를 현실에 대응되도록 만든 구조

자료구조의 종류

단순 구조

• 정수
• 실수
• 문자열
• 논리

선형 구조

선형 구조: 한 원소 뒤에 하나의 원소 만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조

• 배열: 추가와 삭제가 반복되는 로직이면 권장하지 않음, 탐색이 많은 경우에 유리한 자료구조
• 연결 리스트: 추가와 삭제가 반복되는 로직에 권장됨
• 스택: LIFO(Last In First Out)
• 큐

비선형 구조

비선형 구조: 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적합

• 트리
• 그래프

알고리즘

• 특정 문제를 효율적이고 빠르게 하는 것이 목표
• 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것

자료구조 + 알고리즘 = 프로그램!

시간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미함
• 프로그램의 성능을 정확히 파악하는 것은 불가능 ⇒ 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용함

문제의 크기

• 문제의 크기란? 예) 쇼핑몰 장바구니 물건의 개수, 게임 동시 접속자의 수 등
  이러한 문제의 크기를 보통 N이라고 하고, 문제의 크기 N에 따라 걸리는 시간이 다르다.
• 문제를 해결할 때 문제의 크기에 따라 알맞는 방법을 선택하는 것이 중요

빅오표기법(Big O notation)

빅오 표기법	n = 1	n = 4	n = 8
O(1)	1	1	1
O(logn)	0	2	3
O(n)	1	4	8
O(nlogn)	2	8	24
O(n^2)	1	16	64
O(2^n)	2	16	256
O(n!)	1	24	40,326

빅오표기법 4가지 법칙

1. 계수 법칙: 이 무한에 가까울 수록 k의 크기는 의미가 없음
2. 합의 법칙: 빅오는 더해질 수 있음
3. 곱의 법칙: 빅오는 곱해질 수 있음
4. 다항 법칙: f(n)이 k차 다항식이면 f(n)은 O(n^k)

시간 복잡도 계산하기

• 상수는 버림 ex) O(5) = O(1), O(3N^2) = O(N^2)
• 두가지 항이 있을 때, 변수가 같으면 큰것만 빼고 다 버림 ex) O(N^2 + N) = O(N^2), O(N^2 + NlgN) = O(N^2)
• 두가지 항이 있는데 변수가 다르면 놔둠 ex) O(N^2 + M)

공간 복잡도

• 알고리즘의 실행 중에 사용되는 메모리 공간의 양을 나타내는 것
• 보통 가장 많은 공간을 사용하는 것은 배열(배열이 사용한 공간: 배열의 크기 X 자료형의 크기)
• 일반적으로 공간 복잡도는 추가적인 입력 데이터를 저장하는 데 필요한 공간과 알고리즘이 실행되는 동안 생성되는 임시 데이터를 저장하는 데 필요한 공간으로 구성됨

JS의 Date 객체로 성능 측정

const start = new Date().getTime();
const N = 1000000000;

let total = 0;
for (let i = 0; i < N; i += 1) {
  total += 1;
}

const end = new Date().getTime();
console.log(end - start);