알고리즘 (Algorithms)

목차

알고리즘이란

알고리즘(Algorithms) 은 문제를 해결하기 위한 절차와 규칙입니다.

백엔드 면접에서 알고리즘은 코딩 테스트로만 끝나지 않습니다.
대용량 데이터 처리, 검색 최적화, 작업 스케줄링, 경로 탐색 같은 실무 문제도 결국 어떤 절차로 풀지의 문제로 이어집니다.

중요한 점은 “정답 패턴을 얼마나 많이 외웠는가”보다 다음을 보여주는 것입니다.

  • 문제를 연산 단위로 바꿔 보는가
  • 브루트포스보다 나은 구조를 떠올리는가
  • 시간과 메모리 비용을 설명할 수 있는가
  • 입력 크기에 따라 어느 접근이 터지는지 판단하는가

즉, 알고리즘은 코드를 빨리 쓰는 기술이라기보다 문제를 계산 가능한 형태로 바꾸는 사고 방식에 가깝습니다.

면접에서 알고리즘을 보는 이유

면접관은 보통 알고리즘 문제를 통해 다음을 봅니다.

  • 문제 이해 능력: 요구사항을 잘못 해석하지 않는가
  • 추상화 능력: 배열, 그래프, 문자열, 구간 문제로 바꿔 볼 수 있는가
  • 개선 능력: 단순 풀이에서 더 나은 풀이로 줄여 갈 수 있는가
  • 검증 습관: 반례와 edge case를 스스로 점검하는가

좋은 답변은 바로 최적해를 말하는 것이 아니라,
단순한 접근 → 병목 파악 → 개선된 접근 순서로 사고 과정을 보여주는 답변입니다.

시간 복잡도와 공간 복잡도

알고리즘을 설명할 때는 항상 복잡도 이야기가 붙습니다.

  • 시간 복잡도: 입력 크기 N이 커질 때 연산 수가 얼마나 늘어나는가
  • 공간 복잡도: 추가 메모리가 얼마나 필요한가

면접에서는 보통 다음 구분이 중요합니다.

  • 입력 크기가 작은가: 단순한 O(N^2)도 충분할 수 있음
  • 입력 크기가 큰가: 정렬, 해시, 이분 탐색, DP 같은 개선이 필요
  • 메모리 제약이 큰가: 빠른 알고리즘이더라도 메모리를 너무 많이 쓰면 곤란

예를 들어:

  • 단순 중복 검사: 이중 루프는 O(N^2)
  • 해시 사용: 평균적으로 O(N)에 가깝게 개선 가능

즉, 복잡도는 수식 암기가 아니라 어떤 병목을 줄였는지 설명하는 언어입니다.

정렬과 탐색 기본기

정렬과 탐색은 가장 기본적인 알고리즘 축입니다.

정렬을 알고 있어야 하는 이유:

  • 데이터 순서를 맞추면 탐색이 쉬워짐
  • 중복 제거, 구간 처리, 투포인터, 이분 탐색으로 연결됨
  • 단순 문제를 더 구조화해서 볼 수 있음

탐색은 보통 다음 형태로 나뉩니다.

  • 선형 탐색: 처음부터 끝까지 확인
  • 이분 탐색: 정렬된 데이터에서 절반씩 버리며 탐색
  • 해시 탐색: 키 기반으로 평균 빠른 조회

면접에서 중요한 것은 정렬 알고리즘 이름을 많이 나열하는 것보다, 정렬이 왜 필요한 전처리인지와 이분 탐색이 어떤 조건에서 가능한지를 설명하는 것입니다.

DFS와 BFS

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프와 트리 문제에서 가장 기본적인 탐색 방식입니다.

탐색 방식 핵심 아이디어 잘 맞는 경우
DFS 한 방향으로 깊게 내려감 경로 존재 여부, 백트래킹, 연결 요소 탐색
BFS 가까운 노드부터 넓게 탐색 최단 거리, 레벨 순회, 최소 단계 문제

DFS가 잘 맞는 경우:

  • 가능한 경우의 수를 끝까지 내려가며 확인해야 함
  • 재귀나 스택 구조가 자연스러움
  • 그래프 연결 요소나 사이클 검사에 활용

BFS가 잘 맞는 경우:

  • 시작점에서 가까운 순서가 중요함
  • 최소 이동 횟수, 최소 단계 수를 구해야 함
  • 레벨 단위 탐색이 필요함

면접에서는 DFS/BFS를 외운 패턴으로 말하기보다,
깊이가 중요한지, 거리와 단계가 중요한지로 선택 기준을 설명하는 편이 좋습니다.

투포인터와 이분 탐색

두 패턴은 면접에서 매우 자주 등장합니다.

투포인터

배열이나 문자열에서 두 인덱스를 움직이며 조건을 만족하는 구간을 찾는 방식입니다.

  • 잘 맞는 경우: 정렬 배열의 합 문제, 슬라이딩 윈도우, 중복 제거
  • 장점: 이중 루프를 단일 스캔 수준으로 줄일 수 있음
  • 주의점: 포인터 이동 조건을 명확히 못 세우면 쉽게 꼬임

이분 탐색

정렬된 조건 공간에서 답이 절반씩 줄어드는 문제에 사용합니다.

  • 잘 맞는 경우: 정렬 배열 탐색, lower/upper bound, 파라메트릭 서치
  • 장점: O(log N)으로 빠름
  • 주의점: 정렬 조건 또는 단조성이 있어야 함

좋은 답변은 “이건 이분 탐색 문제입니다”가 아니라,
답의 범위가 단조적으로 줄어드니 이분 탐색이 가능하다처럼 조건을 먼저 설명하는 답변입니다.

그리디와 동적 계획법

그리디 (Greedy)

매 단계에서 가장 좋아 보이는 선택을 하는 방식입니다.

  • 장점: 구현이 단순하고 빠른 경우가 많음
  • 주의점: 지역 최적이 항상 전역 최적이 되는 것은 아님
  • 잘 맞는 경우: 선택의 정당성을 증명할 수 있는 문제

동적 계획법 (Dynamic Programming)

겹치는 부분 문제와 최적 부분 구조를 이용해 답을 재사용하는 방식입니다.

  • 장점: 지수 시간 문제를 다항 시간으로 줄일 수 있음
  • 주의점: 상태 정의를 잘못 잡으면 구현이 어려워짐
  • 잘 맞는 경우: 부분 문제의 답을 누적해 전체 답을 만들 수 있는 문제

면접에서는 DP를 “점화식 외우기”보다,
상태(state), 점화식(transition), 초기값(base case) 을 어떻게 정의했는지 설명하는 편이 좋습니다.

문제를 어떻게 분해할까

알고리즘 면접에서 가장 중요한 습관은 문제 분해입니다.

보통 다음 순서로 가면 안정적입니다.

  1. 입력 크기와 제약 확인
    • N이 100인지, 100만인지 먼저 본다
  2. 단순 풀이를 말해 본다
    • 완전탐색이 왜 느린지 기준점을 만든다
  3. 핵심 병목을 찾는다
    • 중복 탐색인가, 정렬이 필요한가, 범위가 줄어드는가
  4. 자료구조나 패턴을 연결한다
    • 해시, 정렬, 투포인터, BFS, DP 중 무엇이 맞는가
  5. 반례를 확인한다
    • 빈 입력, 중복 값, 음수, 오버플로 가능성

좋은 답변은 정답 코드보다 왜 이 접근이 제약을 만족하는지를 설명하는 답변입니다.

코드 예시

아래 예시는 정렬된 배열에서 이분 탐색으로 목표 값을 찾는 기본 패턴입니다.

function binarySearch(values, target) {
  let left = 0;
  let right = values.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (values[mid] === target) {
      return mid;
    }

    if (values[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

이 예시에서 중요한 포인트는 다음과 같습니다.

  • 이분 탐색은 정렬된 입력이 전제입니다.
  • 매 단계에서 탐색 범위를 절반으로 줄입니다.
  • 단순 선형 탐색보다 큰 입력에서 훨씬 유리합니다.

면접 포인트

  • 알고리즘 면접의 핵심은 패턴 암기보다 문제를 연산 구조로 분해하는 능력입니다.
  • 복잡도는 정답을 포장하는 수식이 아니라, 왜 이 접근이 제약을 만족하는지 설명하는 근거입니다.
  • DFS/BFS, 투포인터, 이분 탐색은 선택 조건을 말할 수 있어야 제대로 아는 것입니다.
  • 그리디는 정당화가 필요하고, DP는 상태와 전이를 정의할 수 있어야 합니다.
  • 좋은 답변은 단순 풀이에서 더 나은 풀이로 개선하는 과정을 보여줍니다.

참고 자료