![[CS 기초 01] 자료구조 - 왜 배우는지와 복잡도 감 잡기](https://img.thenullpage.com/posts/8223/8223_1_a59431.webp)
1. 자료구조라는 말이 낯설게 느껴지는 이유
자료구조라는 단어는 프로그래밍을 처음 배울 때 가장 낯설게 느껴지는 개념 중 하나입니다. 사실 거창한 개념이 아니라 데이터를 메모리에 어떤 방식으로 저장하고 정리할 것인가에 대한 약속일 뿐입니다. 초보 개발자는 대부분 리스트 하나로 모든 문제를 해결하려고 합니다. 데이터 양이 작을 때는 문제가 없지만 수만, 수십만 개로 늘어나는 순간 이야기가 달라집니다. 로직은 똑같은데 어떤 코드는 순식간에 끝나고 어떤 코드는 몇 분이 지나도 끝나지 않는 상황을 직접 겪게 됩니다. 이 차이를 만드는 것이 바로 자료구조 선택입니다.
이번 편에서는 자료구조가 왜 필요한지, 그리고 그 필요성을 설명할 때 쓰이는 복잡도라는 척도가 대략 무엇인지 실제 파이썬 코드로 확인해 보겠습니다.
2. 같은 문제를 두 가지 방식으로 풀어보기
십만 개의 숫자 중에 특정 숫자 하나가 들어 있는지 확인하는 문제를 리스트와 셋(set) 두 가지 방식으로 풀어보겠습니다. 먼저 리스트를 그대로 쓰는 방법입니다.
import time
data_list = list(range(100000))
target = 99999
start = time.time()
result = target in data_list
end = time.time()
print("리스트에서 찾음", result, end - start)
리스트에서 찾음 True 0.003812
이번에는 같은 데이터를 셋에 담아 똑같이 찾아보겠습니다.
data_set = set(data_list)
start = time.time()
result = target in data_set
end = time.time()
print("셋에서 찾음", result, end - start)
셋에서 찾음 True 0.000001
담긴 값은 완전히 같은데 걸린 시간은 수천 배 차이가 납니다. 리스트는 값을 찾을 때 처음부터 하나씩 비교해야 하지만, 셋은 값을 넣는 순간 해시라는 계산을 거쳐 있어야 할 자리를 미리 정해 두기 때문에 그 자리만 확인하면 됩니다.
3. 복잡도라는 척도로 성능 이야기하기
이 시간 차이를 설명할 때 개발자들은 초 단위 숫자보다 빅오(Big O)라는 표기법을 씁니다. 입력 크기 n이 커질 때 연산 횟수가 어떤 비율로 늘어나는지를 나타내는 표기법입니다.
인덱스로 값 하나를 꺼내는 연산은 데이터가 열 개든 백만 개든 걸리는 시간이 거의 같아서 O(1)이라고 씁니다. 하나씩 비교하며 찾는 연산은 데이터가 늘어난 만큼 확인 횟수도 늘어나서 O(n)이라고 씁니다. 반복문 안에서 또 반복문을 돌리면 연산 횟수가 n의 제곱만큼 늘어나는데 이런 경우를 O(n^2)이라고 씁니다. 데이터가 백만 개라면 O(n)은 백만 번이면 끝나지만 O(n^2)은 일조 번에 가까운 연산이 필요합니다. 컴퓨터가 아무리 빨라져도 이 비율 자체를 뒤집을 수는 없습니다. 정렬된 데이터에서 가운데 값과 비교해 범위를 절반씩 줄여 나가는 이진 탐색은 O(log n)이라고 쓰고, 데이터가 백만 개여도 스무 번 안팎의 비교만으로 원하는 값을 찾을 수 있습니다.
이 감각을 코드로 확인해 보겠습니다. 아래 두 함수는 리스트 안에 중복된 값이 있는지 검사하는 함수입니다.
def has_duplicate_slow(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return True
return False
def has_duplicate_fast(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
두 함수는 결과가 항상 같지만, nums의 길이가 만 개만 되어도 has_duplicate_slow는 확연히 느려지는 반면 has_duplicate_fast는 큰 차이를 느끼기 어려울 정도로 빠릅니다. 반복문을 겹쳐 쓰지 않고 셋 하나로 이미 본 값을 그때그때 기록해 두었기 때문입니다.
4. 자료구조는 어떤 질문에 답하기 위해 고르는가
자료구조를 고를 때 가장 먼저 던져야 할 질문은 이 데이터에 대해 어떤 연산을 가장 자주 할 것인가입니다. 순서대로 하나씩 꺼내 볼 것인지, 특정 값이 있는지 자주 확인할 것인지, 앞뒤로 계속 추가하고 뺄 것인지에 따라 알맞은 자료구조가 전혀 다릅니다.
순서를 기억하고 인덱스로 접근할 일이 많다면 리스트가 자연스러운 선택입니다. 있는지 없는지 자주 확인해야 한다면 셋이나 딕셔너리가 훨씬 유리합니다. 파이썬 리스트의 맨 앞에서 값을 계속 빼는 코드는 겉보기와 다르게 매번 남은 원소를 한 칸씩 당겨야 해서 O(n)이 걸리는데, 이런 용도로는 collections 모듈의 deque를 쓰면 양쪽 끝에서 넣고 빼는 연산을 O(1)로 처리할 수 있습니다. 스택은 마지막에 들어온 것이 가장 먼저 나간다는 규칙 하나로 함수 호출이 되돌아가는 순서를 기억하거나, 괄호가 제대로 짝지어졌는지 검사하거나, 실행 취소 기능을 구현하는 문제를 간단히 풀어냅니다.
5. 초보자가 가장 많이 걸리는 함정
신입 개발자들이 정말 자주 저지르는 실수는 반복문 안에서 리스트에 in 연산자를 쓰는 습관입니다. targets 리스트를 돌면서 매번 t in numbers처럼 리스트 전체를 훑으면, 바깥 반복문이 한 번뿐이라도 사실상 O(n^2)에 가깝게 동작합니다. targets와 numbers가 각각 이만 개라면 최악의 경우 사억 번에 가까운 비교가 일어날 수 있습니다.
해결 방법은 간단합니다. numbers를 미리 셋으로 한 번만 바꿔 두면 in 연산이 O(1)로 바뀌어서 전체 코드가 O(n) 수준으로 끝납니다. 데이터가 수백 개일 때는 체감하기 어렵지만, 수만 개나 수십만 개로 늘어나는 순간 이 한 줄의 차이가 코드가 통과하느냐 시간 초과로 떨어지느냐를 가르는 경우가 정말 많습니다.
6. 자료구조별 비용을 감으로 기억해 두기
지금 당장 모든 자료구조의 세부 구현을 외울 필요는 없습니다. 다만 앞으로 배우게 될 자료구조들이 대략 어떤 비용을 갖는지 감으로만 잡아 두면 이후 내용을 따라가기가 훨씬 수월합니다. 리스트는 인덱스로 값을 꺼내는 것은 아주 빠르지만 특정 값이 있는지 찾는 것은 데이터 수만큼 시간이 걸립니다. 딕셔너리와 셋은 넣고 찾고 지우는 작업 대부분이 평균적으로 아주 빠르게 끝나는 대신 순서를 유지하거나 정렬된 상태를 보장해 주지는 않습니다.
이 감각을 몸에 익히는 가장 좋은 방법은 코드를 직접 돌려 보고 시간을 재보는 것입니다. 코딩테스트를 준비하는 입장에서는 이 감각이 특히 중요합니다. 입력 크기가 십만이나 백만 단위라면 반복문을 겹쳐 쓰는 풀이는 시작부터 의심해 봐야 하고, 반대로 입력 크기가 스물 이하로 아주 작다면 오히려 모든 경우를 다 따져 보는 단순한 풀이가 가장 안전한 정답일 때도 많습니다. 문제를 마주할 때마다 지금 자주 하려는 연산이 무엇인지부터 떠올리는 습관을 들이면, 코드를 짜기 전에 이미 절반은 설계가 끝난 셈입니다.