자료구조 기본 중에 기본

효율적인 자료구조 설계를 위해서는 알고리즘 지식이 필요하다.
효율적인 알고리즘을 작성하기 위해서 문제 상황에 맞는 적절한 자료구조가 사용되어야 한다.
따라서 프로그램을 작성할 때는 자료구조와 알고리즘을 모두 고려해야 한다❗️

---

자료구조의 종류

📍 자료구조란?

• 다수의 자료(data)를 담기 위한 구조
• 데이터의 수가 많아질수록 효율적인 자료구조 필요

1. 선형 구조 (linear data structure)

하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조로, 데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다.

• 배열(array)
• 연결 리스트(linked list)
• 스택(stack)
• 큐(queue)

2. 비선형 구조(non-linear data structure)

하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조로, 데이터가 일직선상으로 연결되어 있지 않아도 된다.

• 트리(tree)
• 그래프(graph)

프로그램의 성능 측정 방법

• 시간 복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정한다.
• 공간 복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정한다.

Big-O 표기법

• 복잡도를 표현할 때는 Big-O 표기법을 사용한다.
  1️⃣ 특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있다.
  2️⃣ 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

• 다음 알고리즘은 $O(n)$ 의 시간 복잡도를 가진다.

let n = 10;
let summary = 0;

for (let i = 0; i < n; i++) {
  summary += i;
}
console.log(summary);

• 다음 알고리즘은 $O(n^2)$ 의 시간 복잡도를 가진다.

let n = 9;

for (let i = 1; i <= n; i++) { 
  for (let j = 1; j <= n; j++) {
    console.log(`${i} X ${j} = ${i * j}`);
  }
}

• 일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요된다.

• Big-O 표기법으로 시간 복잡도를 표기할 때는 가장 큰 항만을 표시한다.

• 가장 큰 항에 붙어있는 계수는 제거한다.

$O(3n^2 + n) = O(n^2)$

✏️ $n = 1,000$ 일 경우...

• $O(n)$ → 약 1,000번의 연산

• $O(nlogn)$ → 약 10,000번의 연산

• $O(n^2)$ → 약 1,000,000번의 연산

• $O(n^3)$ → 약 1,000,000,000번의 연산

  

  출처: Big O notation

---

현실 세계에서는 동작 시간이 1초 이내인 알고리즘을 설계해야 한다.
취업을 하기 위해서 필수적인 코딩 테스트에서 메모리의 크기를 나타낼 때는 일반적으로 MB 단위로 표기한다.