알고리즘과 복잡도

🎯 학습 목표

이 강을 마치면 알고리즘이 무엇이고 왜 효율을 따져야 하는지 설명할 수 있습니다. 그리고 시간 복잡도와 공간 복잡도를 빅오 표기법으로 나타낼 수 있으며, 같은 문제를 푸는 두 코드 중 어느 쪽이 더 효율적인지 실행해 보기 전에 판단할 수 있게 됩니다.

코딩 테스트에서 가장 흔한 실패는 답이 틀리는 것이 아닙니다. 답은 맞는데 시간이 초과되는 것입니다. 이 강은 그 문제를 다룹니다.

💡 알고리즘이란 무엇인가

알고리즘은 어떤 문제를 풀기 위한 명확한 절차입니다. 입력을 받아 정해진 단계를 거쳐 출력을 내놓고, 반드시 유한한 시간 안에 끝나야 합니다.

이 정의만 보면 요리 레시피와 다를 게 없어 보입니다. 실제로 비슷합니다. 다만 컴퓨터에서 중요한 것이 하나 더 있습니다. 같은 결과를 내는 절차가 여러 개일 때, 어느 것이 더 빠른가입니다.

예를 들어 1부터 100까지 더하는 문제를 생각해 봅시다. 방법은 최소한 두 가지입니다.

• 방법 A — 1부터 100까지 하나씩 더한다. 덧셈을 100번 한다.
• 방법 B — 공식 n * (n + 1) // 2를 쓴다. 연산을 3번 한다.

100까지라면 둘 다 순식간에 끝나므로 차이를 못 느낍니다. 그런데 1부터 1억까지라면 어떨까요. 방법 A는 덧셈을 1억 번 하고, 방법 B는 여전히 3번입니다. 입력이 커질 때 비로소 차이가 드러납니다.

그래서 알고리즘의 효율은 "입력 크기가 커질 때 연산량이 어떻게 늘어나는가"로 따집니다. 입력 크기를 보통 n이라고 부릅니다.

코딩 테스트에서 이것이 결정적인 이유가 있습니다. 문제에는 대개 입력 범위가 적혀 있습니다. "n은 100,000 이하"라고 되어 있다면, 출제자는 n번 정도 도는 풀이를 기대한다는 신호입니다. n을 두 번 겹쳐 도는 풀이를 내면 100억 번 연산이 되어 제한 시간을 넘깁니다.

📖 빅오 표기법 — 증가 속도만 남긴다

빅오 표기법(Big-O notation)은 입력이 커질 때 연산량이 어떤 속도로 증가하는지만 남겨서 표현하는 방법입니다. 핵심 규칙은 두 가지입니다.

• 상수는 버린다. 연산이 3n번이든 100n번이든 전부 O(n)입니다.
• 가장 빨리 커지는 항만 남긴다. n² + 5n + 100은 O(n²)입니다.

왜 이렇게 거칠게 다루는지 의아할 수 있습니다. 이유는 n이 충분히 커지면 나머지가 무의미해지기 때문입니다. n이 100,000일 때 n²은 100억이고, 5n은 50만입니다. 5n은 있으나 마나 한 수준입니다.

n이 커질 때 연산량이 늘어나는 모습

  n            O(log n)   O(n)        O(n log n)    O(n²)
  ────────────────────────────────────────────────────────────
  10               3         10             33            100
  1,000           10      1,000         10,000      1,000,000
  100,000         17    100,000      1,700,000   10,000,000,000
  1,000,000       20  1,000,000     20,000,000  1,000,000,000,000

  ▲ n이 100,000일 때
    O(n)   은 10만 번
    O(n²)  은 100억 번  ← 같은 문제, 10만 배 차이

  ※ log는 밑이 2인 로그 기준의 대략적인 값이다.

자주 나오는 복잡도를 빠른 순서로 정리하면 다음과 같습니다.

표기	이름	대표 예	n이 커질 때
O(1)	상수	리스트 인덱스 접근, 딕셔너리 조회	변하지 않습니다
O(log n)	로그	이분 탐색	거의 안 늘어납니다
O(n)	선형	리스트 전체 순회	비례해서 늘어납니다
O(n log n)	선형 로그	정렬	완만하게 늘어납니다
O(n²)	제곱	이중 반복문	급격히 늘어납니다
O(2ⁿ)	지수	모든 부분집합 나열	n이 조금만 커져도 불가능합니다

여기에 공간 복잡도도 같은 방식으로 따집니다. 시간 복잡도가 "연산을 몇 번 하는가"라면, 공간 복잡도는 "메모리를 얼마나 추가로 쓰는가"입니다. 크기 n인 리스트를 새로 만들면 O(n), 변수 몇 개만 쓰면 O(1)입니다.

대개는 시간이 더 급한 제약이지만, 메모리 제한이 빡빡한 문제에서는 공간 복잡도가 당락을 가릅니다. 그리고 두 값은 맞바꿀 수 있는 경우가 많습니다. 미리 계산해 저장해 두면(공간 ↑) 매번 계산하지 않아도 됩니다(시간 ↓).

💻 실전 예제 — 같은 문제, 다른 복잡도

리스트 안에 특정 값이 있는지 확인하는 문제로 차이를 직접 보겠습니다.

import time
import random

n = 200_000
data = list(range(n))          # 0 ~ 199,999
targets = [random.randint(0, n - 1) for _ in range(1000)]

# 방법 A : 리스트에서 찾기 → 한 번 찾을 때 O(n)
start = time.perf_counter()
count_a = 0
for t in targets:
    if t in data:              # 리스트를 앞에서부터 훑는다
        count_a += 1
time_a = time.perf_counter() - start

# 방법 B : 집합에서 찾기 → 한 번 찾을 때 평균 O(1)
data_set = set(data)           # 집합으로 변환 (O(n), 한 번만)
start = time.perf_counter()
count_b = 0
for t in targets:
    if t in data_set:          # 해시로 바로 찾는다
        count_b += 1
time_b = time.perf_counter() - start

print(count_a, count_b)                    # 결과는 같다
print(f"list: {time_a:.3f}s / set: {time_b:.3f}s")

코드를 줄 단위로 보겠습니다.

• data = list(range(n)) — 20만 개짜리 리스트를 만듭니다. 200_000처럼 밑줄을 넣으면 읽기 쉬워지고, 값은 200000과 같습니다.
• if t in data — 리스트에서의 in은 앞에서부터 하나씩 비교합니다. 최악의 경우 20만 번 비교하므로 O(n)입니다. 이 작업을 1,000번 반복하니 전체는 O(n × 1000)이 됩니다.
• data_set = set(data) — 집합으로 변환합니다. 이 변환 자체는 O(n)이지만 한 번만 합니다.
• if t in data_set — 집합에서의 in은 해시값으로 위치를 바로 계산하므로 평균 O(1)입니다. 1,000번 반복해도 전체가 O(1000) 수준입니다.
• time.perf_counter() — 경과 시간 측정에 쓰는 함수입니다. 두 지점의 값을 빼면 걸린 시간(초)이 나옵니다.

실행해 보면 두 결과값 count_a와 count_b는 항상 같습니다. 답은 똑같은데 걸리는 시간만 크게 차이 납니다. 정확한 초는 컴퓨터마다 다르지만, 집합 쪽이 압도적으로 빠르다는 결과는 어디서 돌려도 동일합니다.

이것이 파이썬 자료형별 복잡도를 알아야 하는 이유입니다. 공식 문서(Python Wiki의 TimeComplexity 문서)에 정리된 주요 연산은 다음과 같습니다.

연산	list	set / dict
x in s (포함 확인)	O(n)	평균 O(1)
맨 뒤에 추가	O(1) (상각)	평균 O(1)
중간 삽입 insert	O(n)	-
맨 뒤 삭제 pop()	O(1)	-
정렬 sort	O(n log n)	-

포함 확인이 잦다면 리스트 대신 집합이나 딕셔너리를 쓴다. 이 한 줄이 코딩 테스트에서 시간 초과를 막아 주는 가장 흔한 처방입니다.

⚠️ 자주 하는 실수

첫째, 입력 범위를 안 보고 코드부터 씁니다. 문제의 제약 조건은 어떤 복잡도까지 허용되는지를 알려 주는 힌트입니다. n이 1,000 이하라면 O(n²)도 괜찮지만, n이 100,000이라면 O(n log n) 이하로 풀어야 합니다. 코드를 쓰기 전에 범위를 먼저 확인하는 습관을 들이세요.

참고로 "1초에 대략 1억 번 연산" 정도를 기준으로 감을 잡는 경우가 많지만, 이는 언어·채점 환경·연산 종류에 따라 크게 달라지는 어림값입니다. 특히 파이썬은 이보다 훨씬 느릴 수 있으므로 여유를 두고 판단해야 합니다.

둘째, 반복문 안에 숨은 O(n) 연산을 못 봅니다. 겉보기에는 반복문이 하나뿐인데 그 안에 in이나 insert(0, x) 같은 O(n) 연산이 들어 있으면 전체는 O(n²)이 됩니다. 반복문 안의 각 줄이 몇 번 도는지를 따져 보세요.

셋째, 상수를 신경 쓰느라 큰 그림을 놓칩니다. 초보자일수록 2n을 n으로 줄이는 데 시간을 씁니다. 그런데 정작 중요한 것은 O(n²)를 O(n log n)으로 바꾸는 것입니다. 상수 개선은 몇 배지만 복잡도 개선은 수천 배입니다.

넷째, 빅오가 항상 실제 속도를 보장한다고 믿습니다. 빅오는 n이 충분히 클 때의 경향입니다. n이 작으면 O(n²) 알고리즘이 O(n log n)보다 빠를 수도 있습니다. 상수와 구현 방식이 영향을 주기 때문입니다. 다만 코딩 테스트는 대개 n을 크게 주므로 빅오 기준으로 판단하면 됩니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	알고리즘은 유한한 시간에 끝나는 명확한 절차다
2	효율은 입력이 커질 때 연산량이 늘어나는 속도로 따진다
3	빅오는 상수를 버리고 가장 큰 항만 남긴다
4	공간 복잡도는 추가로 쓰는 메모리. 시간과 맞바꿀 수 있다
5	포함 확인은 list는 O(n), set·dict는 평균 O(1)
6	코드를 쓰기 전에 입력 범위부터 확인한다

지금 해 볼 것은 위 예제 코드를 직접 실행해 보는 것입니다. 숫자로 확인하면 복잡도가 추상적인 개념이 아니라 체감되는 차이가 됩니다.

다음 2강 「빅오 표기 자세히」에서는 이번 강에서 직관적으로 다룬 빅오를 더 정확히 봅니다. 반복문 구조만 보고 복잡도를 세는 방법, 최선·평균·최악의 구분, 그리고 재귀 호출의 복잡도를 어떻게 세는지까지 다루겠습니다.

📚 참고 자료

• TimeComplexity — Python Wiki
• Data Structures — Python 공식 문서
• time.perf_counter() — Python 공식 문서