Algorithm 성능 최적화 완벽 가이드

알고리즘의 성능을 극대화하는 실전 최적화 기법을 학습합니다. 시간복잡도 개선부터 메모이제이션, 공간복잡도 트레이드오프까지 중급 개발자를 위한 핵심 최적화 패턴을 다룹니다.

---

---

들어가며

이 글에서는 Algorithm 성능 최적화 완벽 가이드에 대해 상세히 알아보겠습니다. 총 10가지 주요 개념을 다루며, 각각의 개념에 대한 설명과 실제 코드 예제를 함께 제공합니다.

목차

1. 메모이제이션으로_중복_계산_제거
2. 투_포인터로_중첩_루프_제거
3. 해시맵으로_조회_성능_최적화
4. 슬라이딩_윈도우로_부분_배열_처리
5. 조기_종료로_불필요한_연산_스킵
6. 비트_연산으로_산술_연산_가속화
7. 공간복잡도_트레이드오프_활용
8. 배치_처리로_함수_호출_오버헤드_감소
9. 정렬_사전처리로_검색_최적화
10. 지연_평가로_불필요한_계산_회피

---

1. 메모이제이션으로 중복 계산 제거

개요

동일한 계산을 반복하지 않도록 결과를 캐싱하여 성능을 획기적으로 개선하는 기법입니다.

코드 예제

function fibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}
// O(2^n) → O(n)으로 개선
console.log(fibonacci(50)); // 빠른 실행

설명

memo 객체에 계산 결과를 저장하여 중복 계산을 방지합니다. 지수 시간에서 선형 시간으로 극적인 성능 향상을 얻습니다.

---

2. 투 포인터로 중첩 루프 제거

개요

정렬된 배열에서 두 개의 포인터를 사용하여 O(n^2)을 O(n)으로 줄이는 최적화 기법입니다.

코드 예제

function twoSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    sum < target ? left++ : right--;
  }
  return null;
}

설명

양 끝에서 시작한 두 포인터가 조건에 따라 이동하며 한 번의 순회로 답을 찾습니다. 이중 루프 대비 시간복잡도가 절반으로 감소합니다.

---

3. 해시맵으로 조회 성능 최적화

개요

배열 검색을 O(n)에서 O(1)로 개선하기 위해 해시맵 자료구조를 활용합니다.

코드 예제

function findPairs(arr, target) {
  const map = new Map();
  const result = [];
  for (const num of arr) {
    if (map.has(target - num)) {
      result.push([target - num, num]);
    }
    map.set(num, true);
  }
  return result;
}

설명

Map을 사용하여 각 요소를 O(1)에 조회합니다. 배열 검색 대신 해시맵을 사용하면 전체 시간복잡도가 O(n^2)에서 O(n)으로 향상됩니다.

---

4. 슬라이딩 윈도우로 부분 배열 처리

개요

고정된 크기의 윈도우를 이동시키며 중복 계산을 제거하여 효율적으로 부분 배열을 처리합니다.

코드 예제

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

설명

윈도우를 한 칸씩 이동하며 새 요소를 더하고 오래된 요소를 빼는 방식으로 매번 전체 합을 다시 계산하지 않습니다.

---

5. 조기 종료로 불필요한 연산 스킵

개요

조건을 만족하는 순간 즉시 반환하여 불필요한 반복을 방지하는 최적화 기법입니다.

코드 예제

function isPrime(n) {
  if (n < 2) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  for (let i = 3; i <= Math.sqrt(n); i += 2) {
    if (n % i === 0) return false;
  }
  return true;
}

설명

제곱근까지만 검사하고 짝수를 먼저 필터링하여 연산량을 대폭 줄입니다. 조기 종료 패턴으로 평균 성능이 크게 향상됩니다.

---

6. 비트 연산으로 산술 연산 가속화

개요

곱셈, 나눗셈 대신 비트 시프트 연산을 사용하여 CPU 레벨에서 성능을 최적화합니다.

코드 예제

function fastMultiplyBy2(n) {
  return n << 1; // n * 2
}
function fastDivideBy2(n) {
  return n >> 1; // Math.floor(n / 2)
}
function isEven(n) {
  return (n & 1) === 0; // n % 2 === 0
}

설명

비트 연산은 CPU에서 직접 처리되어 일반 산술 연산보다 훨씬 빠릅니다. 특히 2의 거듭제곱 연산에서 큰 효과를 발휘합니다.

---

7. 공간복잡도 트레이드오프 활용

개요

메모리를 추가로 사용하여 시간복잡도를 개선하는 최적화 전략입니다.

코드 예제

function uniqueElements(arr) {
  const seen = new Set();
  return arr.filter(item => {
    if (seen.has(item)) return false;
    seen.add(item);
    return true;
  });
}
// O(n^2) → O(n)

설명

Set 자료구조로 O(n) 공간을 사용하지만 중복 확인을 O(1)에 처리합니다. 공간을 희생하여 시간을 절약하는 전형적인 트레이드오프입니다.

---

8. 배치 처리로 함수 호출 오버헤드 감소

개요

여러 번의 함수 호출을 하나로 묶어 호출 오버헤드를 줄이는 최적화 기법입니다.

코드 예제

function batchProcess(items, batchSize = 100) {
  const results = [];
  for (let i = 0; i < items.length; i += batchSize) {
    const batch = items.slice(i, i + batchSize);
    results.push(...batch.map(processItem));
  }
  return results;
}
function processItem(item) { return item * 2; }

설명

대량의 데이터를 배치 단위로 처리하여 함수 호출 횟수를 줄입니다. 특히 I/O 작업이나 비용이 큰 연산에서 효과적입니다.

---

9. 정렬 사전처리로 검색 최적화

개요

데이터를 미리 정렬하여 이진 탐색 등 효율적인 알고리즘을 적용할 수 있게 합니다.

코드 예제

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;
    arr[mid] < target ? left = mid + 1 : right = mid - 1;
  }
  return -1;
}

설명

정렬된 배열에서 이진 탐색을 사용하면 O(log n)에 검색이 가능합니다. 정렬 비용 O(n log n)을 한 번만 지불하고 여러 번 빠른 검색을 할 수 있습니다.

---

10. 지연 평가로 불필요한 계산 회피

개요

실제로 필요할 때까지 계산을 미루어 불필요한 연산을 방지하는 기법입니다.

코드 예제

function* lazyRange(start, end) {
  for (let i = start; i <= end; i++) {
    yield i;
  }
}
const range = lazyRange(1, 1000000);
for (const num of range) {
  if (num > 10) break; // 11개만 생성됨
}

설명

제너레이터를 사용하여 필요한 값만 즉석에서 생성합니다. 전체 배열을 미리 만들지 않아 메모리와 시간을 절약합니다.

---

마치며

이번 글에서는 Algorithm 성능 최적화 완벽 가이드에 대해 알아보았습니다. 총 10가지 개념을 다루었으며, 각각의 사용법과 예제를 살펴보았습니다.

관련 태그

#JavaScript #Algorithm #Optimization #Memoization #TimeComplexity