기술 면접 대비 — 자료구조와 알고리즘 핵심 정리

자료구조 핵심 정리

기술 면접에서는 자료구조의 특성을 이해하고 문제에 적합한 자료구조를 선택할 수 있는 능력을 평가합니다. 각 자료구조의 시간복잡도와 활용 시나리오를 정확히 파악해야 합니다.

시간복잡도 비교

해시맵 활용 패턴

// Two Sum — 해시맵으로 O(n) 풀이
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

// 빈도 수 세기
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) {
    freq.set(n, (freq.get(n) || 0) + 1);
  }
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

// 애너그램 그룹화
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

이진 탐색 패턴

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

function lowerBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

DFS/BFS 그래프 탐색

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const distance = { [start]: 0 };

  while (queue.length > 0) {
    const node = queue.shift();
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distance[neighbor] = distance[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distance;
}

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

슬라이딩 윈도우

function maxSumSubarray(arr, k) {
  let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;

  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

function lengthOfLongestSubstring(s) {
  const seen = new Map();
  let maxLen = 0, left = 0;

  for (let right = 0; right < s.length; right++) {
    if (seen.has(s[right]) && seen.get(s[right]) >= left) {
      left = seen.get(s[right]) + 1;
    }
    seen.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

면접 대비 핵심 알고리즘 패턴

• 해시맵: Two Sum, 빈도 수, 중복 제거 — O(n) 탐색이 필요할 때
• 투 포인터: 정렬된 배열에서 쌍 찾기, 부분 배열 문제
• 슬라이딩 윈도우: 연속 부분 배열/문자열 최적화
• 이진 탐색: 정렬된 데이터에서 O(log n) 탐색
• DFS/BFS: 그래프, 트리 순회, 최단 경로
• 동적 프로그래밍: 최적 부분 구조 + 중복 부분 문제
• 그리디: 매 단계 최선의 선택이 전체 최적인 문제

자료구조와 알고리즘은 기술 면접의 기초 체력입니다. 각 패턴별 대표 문제를 직접 구현해보고, 시간복잡도를 분석하는 습관을 들이면 면접에서 자신감을 가질 수 있습니다.