알고리즘 기초

1. 시간/공간 복잡도 (Big-O Notation)

// O(1): 항상 1번 실행
function accessFirstElement(arr) {
  return arr[0];
}

// O(n): 배열 순회
function printAll(arr) {
  arr.forEach(item => console.log(item));
}

// O(n²): 이중 반복문
function doubleLoop(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

📌 예시: 스택 (Stack)

왜 써야 하나?

• 최근 데이터가 먼저 나가야 하는 상황에서 필수.
• 예: 괄호 검사, 웹 브라우저 '뒤로가기', 재귀 함수 호출 추적 등.

왜 push와 pop만 쓰는 구조인가?

• 스택은 데이터의 순서를 제한적으로만 다루게 해서,
  명확하고 간결한 제어 흐름을 보장합니다.
• 예를 들어 괄호 짝 검사는 "최근 열린 괄호가 먼저 닫혀야 함" → 후입선출 구조가 딱 맞습니다.

구현 이유

const stack = [];

stack.push("(");
stack.push("(");
stack.pop(); // 닫힘 괄호와 비교
stack.pop(); // 또 비교

• push()는 새로운 상태를 저장
• pop()은 가장 나중에 넣은 것을 꺼내어 현재 상황과 비교하거나 처리
• 즉, 스택은 상태 추적용 저장소로 사용됨

---

📌 예시: 큐 (Queue)

왜 써야 하나?

• 작업이 순차적으로 들어와 순차적으로 처리돼야 할 때
• 예: 프린터 대기열, BFS, 네트워크 요청 처리

왜 shift()로 꺼내는 구조인가?

• 처리 순서를 유지하기 위해서
• 나중에 들어온 게 먼저 처리되면 처리 순서가 엉망이 됨

구현 이유

const queue = [];

queue.push("요청1");
queue.push("요청2");
const current = queue.shift(); // "요청1" 처리

• push()는 대기열에 추가
• shift()는 제일 먼저 들어온 요청부터 처리

→ 이 구조를 안 지키면 사용자 경험이 무너질 수 있음
(ex: 나중에 들어온 요청이 먼저 응답되는 웹 앱)

---

📌 예시: DFS & BFS

왜 DFS는 재귀 기반이고, BFS는 큐 기반인가?

• DFS는 한 방향으로 끝까지 파고드는 방식이기 때문에
  → 재귀적으로 탐색 깊이를 따라가는 구조에 자연스럽게 맞음

• BFS는 가까운 노드부터 넓게 탐색하므로
  → 방문 순서를 큐에 저장해서 순차 처리해야 함

DFS 예시

function dfs(node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const neighbor of graph[node]) {
    dfs(neighbor, visited);
  }
}

• 깊이 우선 → 함수 호출 스택이 곧 탐색 경로 기록지

BFS 예시

function bfs(start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length) {
    const node = queue.shift();
    if (visited.has(node)) continue;
    visited.add(node);
    for (const neighbor of graph[node]) {
      queue.push(neighbor);
    }
  }
}

• 큐를 사용하지 않으면 넓이 우선 탐색의 순서 유지 불가
• queue.push(neighbor)는 다음에 방문해야 할 노드를 대기열에 등록

---

📌 예시: 동적 계획법 (DP)

왜 쓰나?

• 피보나치 수열처럼 중복 계산이 너무 많은 문제에서
  → 이전 계산 결과를 기억해두면 시간복잡도 감소

재귀 방식 (비효율적)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // O(2ⁿ)
}

효율적 방식

function fibDP(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // O(n)
  }
  return dp[n];
}

• dp[i]는 이전 두 항의 합을 미리 저장해두고 쓰는 방식
• 메모이제이션 or 보텀업 방식은 중복 호출을 제거하여 성능을 수백 배 개선

---

✍️ 요약 정리

알고리즘/자료구조	왜 사용하나 (상황)	왜 그렇게 구현하나 (핵심 원리)
스택	최근 상태 먼저 처리 (괄호검사, 되돌리기)	후입선출 구조 필요 → push/pop 사용
큐	순차 처리 필요 (BFS, 대기열)	선입선출 유지 → push/shift 구조로 구현
DFS	깊이 우선 탐색 (끝까지 파고들기)	재귀 호출이 깊이 탐색과 자연스럽게 연결됨
BFS	가까운 노드부터 탐색 (최단거리)	순서대로 방문 → 큐 사용해 대기 노드 관리
DP	중복 계산 제거 (피보나치, 최적화 문제)	계산 결과를 배열/객체에 저장하여 재사용 (메모이제이션)

---