같은 문제도, 방법에 따라 속도가 다르다

🧩 자료구조 = 그릇, 알고리즘 = 방법 자료구조(Data Structure) — 데이터를 어떻게 담고 관리할지를 정한 방식이에요. 배열·스택·큐·해시·트리 등이 있고, 각자 잘하는 일이 달라요.
알고리즘(Algorithm) — 문제를 푸는 절차·방법이에요. 정렬·탐색·재귀 같은 것들이죠. 💡 요리로 치면 자료구조는 재료를 담는 그릇, 알고리즘은 조리법이에요. 좋은 그릇과 좋은 조리법을 고르는 게 이 과목의 핵심이에요.

🐢 방법 A — 하나씩 다 더하기

function sumA(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {  // n번 반복
    total += i;
  }
  return total;
}

n이 100만이면 100만 번 더해요. n에 비례해서 일이 늘어요 → O(n).

🐇 방법 B — 공식으로 한 방에

function sumB(n) {
  return n * (n + 1) / 2;   // 반복 없이 계산 한 번
}

n이 아무리 커도 계산 한 번이면 끝나요 → O(1). 💡 같은 정답인데, n이 커질수록 방법 B가 압도적으로 빨라요. 이렇게 "방법의 효율"을 재는 자가 바로 시간복잡도예요.

🎯 세 가지 약속 1. 큰 흐름만 본다 — 컴퓨터·언어마다 실제 속도는 다르니, "커질수록 어떤 곡선을 그리나"라는 추세만 봐요.
2. 최악의 경우 기준 — 보통 가장 나쁜 상황(worst case)을 기준으로 표기해요. (배열에서 찾는 값이 맨 끝에 있을 때 등)
3. 상수·낮은 항은 버린다 — O(2n + 3)은 그냥 O(n). n이 커지면 가장 빨리 자라는 항만 중요해요.

📏 규칙 1 — 반복문을 보면 감이 와요 반복문 한 개(n번 돌면) → O(n)
중첩 반복문 두 개(n × n) → O(n²)
반복 없이 계산/접근 → O(1)
절반씩 줄이는 구조 → O(log n)

📏 규칙 2 — 상수와 계수는 버려요 O(2n + 3) → O(n) · O(n² + n) → O(n²) n이 아주 커지면 가장 빨리 자라는 항만 결과를 좌우해요. 그래서 상수·계수·낮은 차수는 무시해요.