알고리즘과 복잡도 분석

작은 입력에서 보이지 않던 문제가 커질 때

개발 중에는 코드가 잘 동작하는 것처럼 보일 때가 많습니다. 테스트 데이터가 10개, 100개 정도라면 대부분의 코드는 즉시 끝납니다. 문제는 데이터가 10만 개, 100만 개로 늘어났을 때 드러납니다. 로컬에서는 빠르던 API가 운영 환경에서 타임아웃되고, 배치 작업이 새벽 안에 끝나지 않으며, 서버 CPU가 갑자기 치솟습니다.

알고리즘 분석은 이런 상황을 설명하는 도구입니다. 여기서 알고리즘은 거창한 수학 문제가 아니라, 입력을 받아 원하는 결과를 만드는 절차입니다. 목록에서 사용자를 찾는 코드, 상품을 가격순으로 정렬하는 코드, 추천 후보를 계산하는 코드 모두 알고리즘입니다.

복잡도 분석은 "이 코드가 몇 초 걸리는가"를 직접 말하지 않습니다. 대신 입력 크기가 커질 때 실행 시간이나 메모리 사용량이 어떤 속도로 증가하는지 말합니다. 그래서 복잡도는 특정 장비의 성능보다 더 오래 남는 판단 기준이 됩니다.

AI 생성 이미지

Big-O는 증가율을 보는 언어다

Big-O 표기법은 입력 크기 n이 커질 때 비용이 얼마나 빠르게 증가하는지 표현합니다. 예를 들어 배열 길이가 n일 때, 처음부터 끝까지 한 번 훑는 코드는 보통 O(n)이라고 합니다. 입력이 두 배가 되면 해야 할 일도 대략 두 배가 됩니다.

자주 등장하는 복잡도는 다음과 같습니다.

• O(1): 입력 크기와 거의 무관하게 일정한 비용

• O(log n): 입력이 커져도 비용이 천천히 증가

• O(n): 입력 크기에 비례해 증가

• O(n log n): 효율적인 정렬 알고리즘에서 자주 등장

• O(n²): 입력이 커지면 비용이 급격히 증가

Big-O는 보통 상수나 낮은 차수의 항을 생략합니다. 3n + 10번 정도의 연산이 필요해도 결국 O(n)으로 봅니다. 입력이 충분히 커지면 3이나 10보다 n이 커지는 방식이 더 중요하기 때문입니다.

다만 실무에서는 Big-O를 기계적으로 해석하면 안 됩니다. O(1)이라고 항상 빠른 것은 아니고, O(n)이라고 항상 느린 것도 아닙니다. 해시 테이블 조회는 평균적으로 O(1)이지만 해시 계산, 충돌 처리, 메모리 접근 비용이 있습니다. 반대로 작은 배열을 순회하는 O(n) 코드는 캐시 효율이 좋아 매우 빠를 수 있습니다.

따라서 Big-O는 "정확한 실행 시간"이 아니라 "데이터가 커질 때 위험해지는 방향"을 알려 주는 지도에 가깝습니다.

선형 탐색과 이진 탐색

가장 단순한 탐색은 선형 탐색입니다. 배열의 첫 원소부터 마지막 원소까지 차례대로 비교합니다.

function contains(arr, target) {
  for (const value of arr) {
    if (value === target) return true;
  }
  return false;
}

이 코드는 최악의 경우 모든 원소를 확인해야 합니다. 찾는 값이 없거나 마지막에 있으면 n번 비교합니다. 그래서 시간 복잡도는 O(n)입니다.

이진 탐색은 다릅니다. 단, 배열이 정렬되어 있어야 합니다. 가운데 값을 확인한 뒤, 찾는 값이 더 작으면 왼쪽 절반만 보고, 더 크면 오른쪽 절반만 봅니다. 한 번 비교할 때마다 후보가 절반으로 줄어듭니다.

function binarySearch(arr, target) {
  let left = 0;
  let 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;
}

이진 탐색의 시간 복잡도는 O(log n)입니다. 데이터가 100만 개여도 약 20번 정도 비교하면 위치를 찾거나 없다고 판단할 수 있습니다. 선형 탐색과 차이가 크게 나는 지점입니다.

하지만 여기에도 조건이 있습니다. 이진 탐색을 하려면 데이터가 정렬되어 있어야 합니다. 한 번만 검색할 데이터라면 정렬 비용이 더 클 수 있습니다. 반대로 같은 목록에서 검색을 수천 번 반복한다면, 처음에 정렬해 두고 이진 탐색을 쓰는 편이 유리할 수 있습니다. 알고리즘 선택은 항상 사용 패턴과 함께 봐야 합니다.

정렬은 비용 차이가 크게 드러나는 대표 사례다

정렬은 복잡도 차이를 체감하기 좋은 예입니다. 단순한 정렬 방식 중에는 모든 원소 쌍을 반복적으로 비교하는 방식이 있습니다. 대표적으로 버블 정렬이나 선택 정렬은 보통 O(n²)입니다.

n이 1,000이면 대략 백만 번 수준의 비교가 필요할 수 있습니다. n이 100,000이면 비교 횟수는 100억 단위로 커집니다. 작은 입력에서는 문제가 없던 코드가 큰 입력에서 무너지는 전형적인 이유입니다.

반면 병합 정렬이나 힙 정렬은 O(n log n)의 시간 복잡도를 가집니다. 퀵 정렬은 평균적으로 O(n log n)이지만, 피벗 선택이 나쁘면 최악의 경우 O(n²)가 될 수 있습니다. 그래서 많은 언어의 표준 정렬 함수는 단순한 알고리즘 하나만 쓰지 않고, 데이터 특성에 따라 최악의 상황을 피하도록 구현되어 있습니다.

실무에서는 직접 정렬 알고리즘을 구현할 일이 많지 않습니다. 그러나 정렬 비용은 자주 마주칩니다. 데이터베이스에서 ORDER BY를 사용할 때, 애플리케이션에서 응답 목록을 정렬할 때, 로그를 시간순으로 병합할 때 모두 정렬 비용이 발생합니다.

정렬 대상이 적으면 문제가 되지 않습니다. 하지만 요청마다 수십만 개의 객체를 메모리에 올려 정렬한다면 이야기가 달라집니다. 이때는 인덱스를 이용해 데이터베이스가 정렬된 순서로 읽게 할지, 페이지네이션을 먼저 적용할지, 정렬 기준을 제한할지 판단해야 합니다.

재귀와 분할 정복: 문제를 작게 쪼개기

재귀는 함수가 자기 자신을 호출하는 방식입니다. 처음 보면 낯설지만 핵심은 단순합니다. 큰 문제를 같은 형태의 작은 문제로 줄이고, 더 이상 줄일 수 없는 기본 조건에서 멈춥니다.

예를 들어 이진 탐색도 재귀적으로 표현할 수 있습니다. "전체 배열에서 찾기"를 "왼쪽 절반에서 찾기" 또는 "오른쪽 절반에서 찾기"로 바꾸는 식입니다.

분할 정복은 재귀적 사고를 알고리즘 설계로 확장한 방식입니다. 문제를 나누고, 각각을 해결한 뒤, 결과를 합칩니다. 병합 정렬이 대표적입니다. 배열을 절반으로 나누고, 각 절반을 정렬한 뒤, 두 정렬된 배열을 합칩니다.

분할 정복이 강력한 이유는 한 번에 모든 경우를 다루지 않기 때문입니다. 정렬, 탐색, 큰 수 계산, 그래프 알고리즘 등 많은 분야에서 "나눌 수 있는 구조"를 찾으면 복잡도를 크게 줄일 수 있습니다.

다만 재귀에는 비용이 있습니다. 함수 호출마다 호출 스택이 쌓입니다. 깊이가 너무 깊으면 스택 오버플로가 발생할 수 있습니다. 또한 같은 부분 문제를 반복해서 계산하면 시간이 폭발적으로 늘어납니다. 재귀가 아름답게 보인다고 항상 효율적인 것은 아닙니다.

동적 계획법: 반복 계산을 저장하기

동적 계획법은 큰 문제를 작은 문제로 나누되, 같은 작은 문제가 여러 번 등장할 때 그 결과를 저장해 재사용하는 방식입니다. 영어로는 Dynamic Programming, 줄여서 DP라고 부릅니다.

대표적인 예는 피보나치 수입니다. 단순 재귀로 작성하면 fib(5)를 구하는 과정에서 fib(3), fib(2) 같은 값을 여러 번 다시 계산합니다.

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

이 코드는 입력이 조금만 커져도 호출 수가 급격히 늘어납니다. 이미 계산한 값을 저장하면 상황이 달라집니다.

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

이 방식은 같은 값을 다시 계산하지 않습니다. 시간을 줄이기 위해 메모리를 사용한 것입니다. 이를 메모이제이션이라고 합니다. 함수 호출 결과를 캐시에 저장해 두고 같은 입력이 들어오면 재사용합니다.

동적 계획법은 단순히 "외우는 알고리즘 유형"이 아닙니다. 실무에서도 같은 패턴이 자주 나옵니다. 같은 사용자 권한을 요청마다 반복 계산하지 않고 캐싱합니다. 비싼 API 호출 결과를 잠시 저장합니다. 복잡한 쿼리 결과를 materialized view나 캐시 서버에 보관합니다. 모두 시간 비용을 줄이기 위해 공간을 사용하는 선택입니다.

시간 복잡도와 공간 복잡도는 함께 봐야 한다

시간 복잡도는 실행 시간이 입력 크기에 따라 어떻게 증가하는지 봅니다. 공간 복잡도는 메모리 사용량이 어떻게 증가하는지 봅니다. 좋은 알고리즘은 빠르기만 한 알고리즘이 아니라, 주어진 제약 안에서 시간과 공간의 균형을 맞추는 알고리즘입니다.

캐싱은 이 균형을 잘 보여 줍니다. 캐시를 사용하면 반복 계산이나 느린 I/O를 줄일 수 있습니다. 대신 메모리를 더 사용합니다. 캐시 크기를 제한하지 않으면 메모리 부족이 발생할 수 있고, 오래된 값을 잘못 재사용하면 데이터 일관성 문제가 생길 수 있습니다.

메모이제이션도 마찬가지입니다. 계산 결과를 저장해 속도를 높이지만, 입력 종류가 너무 많으면 저장 공간이 계속 증가합니다. 웹 서버에서 요청 파라미터별 결과를 무제한 캐싱하면 처음에는 빨라지지만, 시간이 지나면 메모리 사용량 때문에 장애가 날 수 있습니다.

따라서 알고리즘을 평가할 때는 다음 질문을 함께 던져야 합니다.

• 입력 크기는 최대 어느 정도인가?

• 이 코드는 요청마다 실행되는가, 배치에서 한 번 실행되는가?

• 계산이 병목인가, 네트워크나 디스크 I/O가 병목인가?

• 메모리를 더 써도 되는가?

• 결과를 저장했을 때 오래된 데이터 문제가 생기지 않는가?

복잡도 분석은 코드 한 줄을 빠르게 만드는 기술이 아닙니다. 시스템이 커졌을 때 어떤 부분이 먼저 한계에 도달할지 예측하는 방법입니다.

복잡도는 설계 판단의 언어다

개발자는 매번 완벽한 알고리즘을 선택할 필요는 없습니다. 데이터가 20개뿐인 관리자 화면에서 복잡한 최적화를 할 이유는 없습니다. 단순한 코드가 더 좋은 선택일 수 있습니다.

하지만 입력 크기가 커질 가능성이 있거나, 요청 빈도가 높거나, 비용이 비싼 작업이 반복된다면 복잡도를 반드시 봐야 합니다. O(n²) 코드는 처음에는 조용히 숨어 있다가 데이터가 늘어나는 순간 장애의 원인이 됩니다. 반대로 적절한 자료구조, 정렬 전략, 캐싱, 메모이제이션은 같은 하드웨어에서도 훨씬 많은 요청을 처리하게 해 줍니다.

중요한 것은 표기법을 외우는 것이 아니라 증가율을 감지하는 감각입니다. 중첩 반복문이 입력 크기에 따라 얼마나 반복되는지, 같은 계산을 반복하고 있지는 않은지, 메모리를 써서 시간을 줄일 수 있는지, 정렬이나 검색 조건을 바꿀 수 있는지 보는 능력입니다.

알고리즘과 복잡도 분석은 실무 코드의 미래 비용을 읽는 방법입니다. 작은 입력에서 잘 동작하는 코드를 넘어서, 큰 입력에서도 버티는 코드를 설계하게 해 줍니다.