콘텐츠 대표 이미지 - 왜 일부 데이터 구조는 특정 작업에 더 효율적일까? 메모리 배치와 연산 비용으로 읽는 자료구조의 원리

왜 일부 데이터 구조는 특정 작업에 더 효율적일까? 메모리 배치와 연산 비용으로 읽는 자료구조의 원리

같은 데이터 100만 개인데, 어떤 그릇에 담느냐에 따라 "찾기"가 0.001초가 되기도 하고 몇 초가 되기도 해요. 오늘은 그 차이가 도대체 어디서 오는지, 친구한테 수다 떨듯 하나씩 뜯어볼게요. 🧩

"찾기" 한 번에 드는 걸음 수 데이터 100만 개 기준, 대략적인 비교 정렬 안 된 배열 · · · 하나씩 확인: 최악 1,000,000번 균형 이진 탐색 트리 반씩 버리기: 약 20번 (2의 20제곱 ≈ 104만) 해시 테이블 키 바로 점프: 평균 약 1번

같은 "찾기"라도 데이터를 어떻게 배치했느냐에 따라 걸음 수가 수만 배 차이 나요.

1. 시작하기 전에: "효율적"이라는 말의 진짜 뜻

친구야, 이삿짐을 싼다고 생각해 봐. 옷은 옷장 서랍에, 책은 책장에, 양념은 양념통 선반에 두잖아. 왜 전부 커다란 박스 하나에 때려 넣지 않을까? 넣을 땐 편하지만 꺼낼 때 지옥이니까. 반대로 책을 가나다순으로 꽂아 두면 찾기는 쉽지만, 새 책 한 권 끼워 넣을 때 뒤쪽 책들을 다 밀어야 해.

데이터 구조(자료구조)도 정확히 이 이야기예요. 데이터 구조란 데이터를 메모리에 어떤 모양으로 배치하고, 그 배치 위에서 어떤 연산을 허용하는지를 정한 약속이에요. 그리고 핵심 문장 하나만 먼저 박아두고 갈게요.

모든 연산에서 동시에 최고인 데이터 구조는 없다. 어떤 연산을 빠르게 만들면, 그 대가는 반드시 다른 곳에서 치른다.

그러니까 "왜 어떤 구조는 특정 작업에 더 효율적인가?"의 답은 결국 그 구조가 특정 작업에 유리하도록 정보를 미리 정리해 두었기 때문이에요. 정렬된 배열은 "순서"라는 정보를 미리 만들어 뒀고, 해시 테이블은 "키 → 위치" 계산 규칙을 만들어 뒀고, 힙은 "제일 작은 놈은 맨 위"라는 규칙만 지켜요. 이 미리 해 둔 정리 작업이 어떤 질문에는 지름길이 되고, 어떤 질문에는 아무 도움이 안 되거나 오히려 방해가 되는 거죠.

효율을 재는 자: 빅오(Big-O) 표기법

효율을 비교하려면 공통된 자가 필요해요. 컴퓨터 과학에서는 주로 점근적 시간 복잡도, 흔히 빅오 표기법을 써요. 데이터 개수 n이 엄청 커질 때 연산 횟수가 어떤 모양으로 늘어나는지를 보는 거예요. 상수나 작은 항은 무시하고 "증가의 기세"만 봐요.

표기이름n = 1,000,000일 때 대략대표 예
O(1)상수 시간1배열 인덱스 접근, 해시 조회(평균)
O(log n)로그 시간약 20이진 탐색, 균형 트리 탐색, 힙 삽입
O(n)선형 시간1,000,000정렬 안 된 배열 탐색, 연결 리스트 순회
O(n log n)선형 로그약 20,000,000효율적인 비교 기반 정렬
O(n²)제곱 시간1,000,000,000,000이중 반복으로 모든 쌍 비교

표를 보면 O(log n)과 O(n)의 차이가 어마어마하죠? 100만 개에서 20 대 100만이에요. 데이터가 10억 개로 늘어도 log₂ 값은 고작 30 정도예요. 그래서 "로그 시간"은 개발자들 사이에서 거의 "사실상 공짜에 가까운" 느낌으로 통해요.

최악·평균·분할상환, 세 가지 관점 같은 구조라도 어떤 경우를 보느냐에 따라 복잡도가 달라져요. 최악의 경우는 가장 운 나쁜 입력, 평균의 경우는 입력이 무작위라고 가정했을 때의 기대값, 분할상환(amortized)은 연산 여러 번을 묶어 평균 낸 비용이에요. 해시 테이블이 "평균 O(1), 최악 O(n)"이라고 소개되는 게 바로 이 차이 때문이에요.

시간만 있는 게 아니다: 공간과 상수

빅오는 강력한 도구지만 만능은 아니에요. 효율에는 적어도 세 가지 축이 더 있어요.

💾 공간 복잡도속도를 얻으려고 메모리를 더 쓰는 경우가 많아요. 해시 테이블은 빈 칸을 일부러 남겨두고, 트리는 노드마다 포인터를 들고 다녀요.
⚙️ 상수 계수O(1)이라도 해시 함수 계산이 무거우면, 작은 배열을 그냥 훑는 O(n)보다 느릴 수 있어요.
🧠 하드웨어 친화성CPU 캐시, 메모리 접근 패턴, 디스크 블록 크기 같은 물리적 조건이 실제 속도를 크게 좌우해요.

이 세 가지가 이번 이야기의 숨은 주인공이에요. 이론상 복잡도가 같아도 실제로는 몇 배씩 차이 나는 이유가 대부분 여기 있거든요.

2. 모든 차이의 뿌리: 메모리에 어떻게 놓여 있는가

컴퓨터 메모리는 결국 번호(주소)가 붙은 아주 긴 칸들의 줄이에요. 데이터 구조가 하는 일은 이 일렬 공간 위에 "논리적인 모양"을 얹는 거예요. 그 방법은 크게 두 가지예요.

🧱 연속 배치데이터를 빈틈없이 나란히 붙여 놓아요. 대표 선수는 배열. 위치를 계산으로 바로 알아낼 수 있어요.
🔗 연결 배치데이터 조각을 아무 데나 두고 "다음은 저기야"라는 주소(포인터)로 이어요. 대표 선수는 연결 리스트와 대부분의 트리.
배열 vs 연결 리스트의 메모리 모습 배열: 나란히 붙어 있음 A B C D E F i번째 주소 = 시작 주소 + i × 칸 크기 → 바로 계산 연결 리스트: 흩어져서 주소로 연결 A B C D

배열은 계산으로 바로 점프, 연결 리스트는 화살표를 하나씩 따라가야 해요.

배열이 "i번째 찾기"에 무적인 이유

배열의 원소가 모두 같은 크기로 나란히 있으면, i번째 원소의 주소는 시작 주소 + i × 원소 크기로 딱 한 번의 계산이면 나와요. 그래서 인덱스 접근이 O(1)이에요. 100번째든 900만 번째든 걸리는 시간이 같아요.

그런데 배열 중간에 새 원소를 끼워 넣으려면? 그 뒤의 원소를 전부 한 칸씩 밀어야 해요. 앞쪽에 넣으면 거의 전부를 옮기니까 O(n)이에요. 영화관에서 가운데 자리에 친구 한 명 끼워 앉히려고 그 줄 사람을 다 한 칸씩 옮기게 하는 거랑 똑같아요. 😅

연결 리스트가 "중간 삽입"에 강한(것처럼 보이는) 이유

연결 리스트는 각 노드가 "내 값 + 다음 노드 주소"를 들고 있어요. 삽입할 위치의 노드를 이미 알고 있다면, 포인터 두 개만 바꾸면 끝이라 O(1)이에요. 아무것도 밀 필요가 없죠.

하지만 함정이 있어요. "i번째 노드"로 가려면 처음부터 화살표를 i번 따라가야 해서 O(n)이에요. 그래서 "500번째 자리에 넣기"는 결국 찾는 데 O(n)이 들어요. 연결 리스트의 O(1) 삽입은 위치를 이미 손에 쥐고 있을 때만 진짜예요. LRU 캐시처럼 해시 테이블이 노드의 위치를 바로 알려주는 구조와 조합하면 이 장점이 제대로 살아나요.

연산배열(동적 배열)단일 연결 리스트
i번째 원소 읽기O(1)O(n)
맨 뒤에 추가분할상환 O(1)꼬리 포인터가 있으면 O(1)
맨 앞에 추가O(n)O(1)
알고 있는 위치 뒤에 삽입O(n)O(1)
값으로 탐색(정렬 안 됨)O(n)O(n)
원소당 추가 메모리거의 없음(여유 용량 제외)포인터 1개 이상

빅오가 말해주지 않는 비밀: CPU 캐시

자, 여기서 재밌는 반전이 하나 있어요. 배열 전체 순회와 연결 리스트 전체 순회는 둘 다 O(n)이에요. 이론상 동급이죠. 그런데 실제로 재보면 배열이 압도적으로 빠른 경우가 아주 흔해요. 왜일까요?

현대 CPU는 메인 메모리(DRAM)에서 데이터를 가져오는 게 연산에 비해 엄청 느려요. 그래서 CPU 안에 작고 빠른 캐시 메모리를 두고, 메모리를 읽을 때 딱 필요한 바이트만이 아니라 주변까지 한 덩어리(캐시 라인, 현대 x86 프로세서에서는 일반적으로 64바이트)를 통째로 가져와요. 게다가 하드웨어 프리페처는 "얘가 순서대로 읽고 있네?" 하고 다음 덩어리를 미리 당겨 놓기도 해요.

배열은 데이터가 붙어 있으니 한 번 가져온 캐시 라인 안에 다음 원소들이 이미 들어 있어요. 이걸 공간 지역성(spatial locality)이라고 해요. 반면 연결 리스트 노드는 메모리 여기저기 흩어질 수 있어서 화살표를 따라갈 때마다 캐시 미스가 날 수 있고, 다음 주소를 알아야 다음 읽기를 시작할 수 있어서 프리페치도 잘 안 먹혀요.

흔한 오해: "삽입이 많으면 무조건 연결 리스트" 교과서 표만 보면 삽입·삭제가 잦으면 연결 리스트가 답처럼 보여요. 하지만 삽입 위치를 찾으려고 순회해야 하는 상황이라면, 캐시 친화적인 배열에서 원소를 밀어내는 쪽이 실제로 더 빠른 경우가 많아요. C++ 표준 라이브러리 커뮤니티에서 "특별한 이유가 없으면 vector를 기본으로 써라"라는 조언이 널리 퍼진 것도 이런 이유예요. 결국 정답은 측정(프로파일링)이에요.

동적 배열과 분할상환 O(1)

배열은 크기가 고정이라는 약점이 있죠. 그래서 Python의 list, Java의 ArrayList, C++의 std::vector 같은 동적 배열은 꽉 차면 더 큰 공간을 새로 잡고 전부 복사해요. 복사는 O(n)인데 어떻게 "맨 뒤 추가는 O(1)"이라고 할 수 있을까요?

비밀은 크기를 일정 배율로 키우는 것이에요. 예를 들어 꽉 찰 때마다 2배로 늘린다고 해볼게요. 원소 n개를 넣는 동안 일어난 복사 총량은 1 + 2 + 4 + … + n/2 + … 로, 2n을 넘지 않아요. 총비용이 O(n)이니 한 번당 평균은 O(1)이에요. 이게 바로 분할상환 분석이에요. 성장 배율은 구현마다 달라서, Java ArrayList는 약 1.5배, GCC의 std::vector는 2배를 쓰는 식이에요.

실전 팁: 크기를 알면 미리 잡아두기 넣을 원소 수를 대충이라도 안다면 C++의 reserve(), Java의 new ArrayList<>(capacity)처럼 용량을 미리 확보하세요. 중간 재할당과 복사가 사라져서 체감 속도가 꽤 달라져요.
# 파이썬에서 동적 배열의 용량이 계단식으로 늘어나는 모습 관찰
import sys
lst = []
prev = sys.getsizeof(lst)
for i in range(32):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev:
        print(f"원소 {len(lst)}개: {size} 바이트")
        prev = size

이 코드를 돌려 보면 원소 하나 넣을 때마다 메모리가 늘어나는 게 아니라, 띄엄띄엄 계단처럼 늘어나는 걸 볼 수 있어요. 여유 공간을 미리 확보해 두는 거죠. 정확한 바이트 값은 파이썬 버전과 플랫폼에 따라 달라요.

3. 해시 테이블: "이름만 대면 바로 꺼내 줄게"

배열은 "i번째"에는 무적이지만, 우리가 실생활에서 묻는 질문은 보통 "홍길동의 전화번호는?"처럼 키(key)로 찾는 거예요. 이름은 숫자 인덱스가 아니잖아요. 해시 테이블은 이 간극을 메우는 천재적인 아이디어예요.

작동 원리: 키를 숫자로 바꿔서 배열에 꽂기

해시 함수 계산: 키("홍길동")를 정수로 바꿔요. 같은 키는 항상 같은 값이 나와야 해요.
버킷 위치 결정: 그 정수를 배열 크기로 나눈 나머지 등으로 칸 번호(버킷)를 정해요.
배열 직접 접근: 배열의 장점인 O(1) 인덱스 접근으로 바로 그 칸에 가요.
키 비교 확인: 그 칸에 있는 게 진짜 찾는 키인지 확인해요(충돌 대비).

보이죠? 해시 테이블은 사실 "키를 인덱스로 바꿔주는 함수 + 배열"이에요. 배열의 O(1) 접근이라는 무기를 키 기반 탐색에 빌려 쓰는 거예요. 그래서 평균 O(1)이라는 놀라운 조회 속도가 나와요.

피할 수 없는 손님: 충돌

키는 무한히 다양한데 칸 수는 유한하니, 서로 다른 키가 같은 칸에 배정되는 충돌(collision)은 반드시 생겨요(비둘기집 원리). 해결법은 크게 두 계열이에요.

⛓️ 체이닝(분리 연결)각 칸에 작은 리스트를 달아서 같은 칸에 온 애들을 줄줄이 매달아요. Java의 HashMap이 이 방식이에요. Java 8부터는 한 칸에 너무 많이 몰리면(기본 임계값 8개, 테이블이 충분히 클 때) 그 칸을 레드-블랙 트리로 바꿔 최악을 O(log n)으로 완화해요.
🚪 개방 주소법칸이 차 있으면 정해진 규칙으로 다른 빈칸을 찾아가요(선형 탐사, 이차 탐사 등). 데이터가 배열 안에 다 들어 있어서 캐시 친화적이에요. CPython의 dict가 개방 주소 계열 방식을 써요.

적재율(load factor): 빈칸의 미학

해시 테이블이 빠르려면 칸이 너무 꽉 차면 안 돼요. 저장된 원소 수 ÷ 칸 수를 적재율이라고 하는데, 이 값이 커지면 충돌이 늘어 속도가 떨어져요. 그래서 적재율이 임계값을 넘으면 테이블을 키우고 모든 원소를 새 칸에 다시 배치(리해싱)해요. Java HashMap의 기본 적재율 임계값은 0.75예요.

즉, 해시 테이블의 빠른 속도는 일부러 비워 둔 메모리를 대가로 얻은 거예요. 시간과 공간을 맞바꾸는 전형적인 사례죠.

해시 테이블이 못하는 것

이렇게 빠른데 왜 모든 걸 해시 테이블로 안 할까요? 해시 함수는 데이터를 일부러 골고루 흩뿌리도록 설계돼요. 그래서 원래 순서 정보가 완전히 사라져요.

질문해시 테이블이유
"홍길동" 있어?👍 평균 O(1)키 → 위치 직행
가장 작은 키는?👎 O(n)순서 정보 없음, 전부 봐야 함
점수 80~90점 사이 전부👎 O(n)범위가 칸 전체에 흩어짐
정렬된 순서로 출력👎 정렬 필요 O(n log n)저장 순서가 키 순서가 아님
최악의 시나리오: 해시 충돌 공격 해시 함수가 예측 가능하면, 공격자가 일부러 같은 칸에 몰리는 키를 잔뜩 보내 서버를 느리게 만들 수 있어요(해시 플러딩, HashDoS). 2011년 무렵 여러 웹 플랫폼에서 이 문제가 크게 알려졌고, 이후 Python 등은 실행마다 무작위 시드를 섞는 해시(예: SipHash 계열)를 도입했어요. "평균 O(1)"이 공격 앞에서는 O(n)으로 무너질 수 있다는 좋은 교훈이에요.

4. 트리: 순서를 지키면서도 빠르게

"빠른 탐색"과 "순서 유지"를 동시에 원한다면? 정렬된 배열은 이진 탐색으로 O(log n) 탐색이 되지만 삽입이 O(n)이에요. 해시는 삽입·탐색이 빠르지만 순서가 없어요. 이 둘 사이의 행복한 중간 지점이 바로 이진 탐색 트리(BST)예요.

이진 탐색 트리의 규칙

각 노드에 대해 "왼쪽 서브트리는 전부 나보다 작고, 오른쪽은 전부 나보다 크다"는 규칙 하나만 지켜요. 그러면 찾을 때 루트에서 시작해 "작으면 왼쪽, 크면 오른쪽"으로 내려가면서 매번 남은 후보의 절반가량을 버릴 수 있어요. 삽입도 같은 길을 따라 내려가 빈자리에 붙이면 끝이라, 원소를 밀어낼 필요가 없어요.

균형 잡힌 트리 한쪽으로 기운 트리 40 20 60 10 30 50 70 70 찾기: 3단계 높이 ≈ log n 10 20 30 40 50 60 정렬된 순서로 넣으면 사실상 연결 리스트, 높이 n

같은 BST라도 모양이 무너지면 O(log n)이 O(n)으로 추락해요.

트리의 효율은 "높이"가 결정한다

BST 연산의 비용은 사실 루트에서 잎까지의 거리, 즉 트리의 높이에 비례해요. 노드가 n개일 때 꽉 찬 모양이면 높이가 약 log₂ n이지만, 위 그림 오른쪽처럼 1, 2, 3, 4… 순서대로 넣으면 한쪽으로만 줄줄이 늘어져서 높이가 n이 돼요. 이러면 트리라는 이름만 달고 실제로는 연결 리스트예요. 😵

자가 균형 트리: 알아서 자세 교정

그래서 등장한 게 삽입·삭제할 때마다 스스로 모양을 다듬는 자가 균형 이진 탐색 트리예요. 핵심 도구는 회전(rotation)이라는 연산인데, BST의 크기 순서 규칙은 그대로 지키면서 부모-자식 관계를 살짝 비틀어 한쪽으로 쏠린 무게를 옮겨요.

AVL 트리1962년 Adelson-Velsky와 Landis가 발표한 최초의 자가 균형 BST. 모든 노드에서 왼쪽·오른쪽 높이 차가 1 이하가 되도록 엄격히 관리해요. 균형이 빡빡해서 탐색이 아주 빨라요.
레드-블랙 트리노드에 빨강·검정 색을 칠하고 몇 가지 규칙으로 "가장 긴 경로가 가장 짧은 경로의 2배를 넘지 않게" 해요. 균형은 느슨하지만 삽입·삭제 시 재조정이 적은 편이라 범용 라이브러리에서 많이 써요. C++ std::map과 Java TreeMap이 대표적이에요.

두 트리 모두 탐색·삽입·삭제를 최악의 경우에도 O(log n)으로 보장해요. 해시 테이블처럼 평균 O(1)은 아니지만, 대신 정렬된 순서 유지, 최솟값·최댓값, 범위 검색, "이 값 바로 다음 값" 같은 질문에 강해요. 해시가 "그 사람 있어?"에 강한 접수처라면, 균형 트리는 "가나다순 명부"예요.

디스크로 가면 판이 바뀐다: B-트리

데이터가 메모리가 아니라 디스크(HDD나 SSD)에 있다면 이야기가 또 달라져요. 저장 장치는 바이트 단위가 아니라 블록(페이지) 단위로 읽고 쓰는데, 저장 장치 접근 한 번이 메모리 접근보다 훨씬 비싸요. 이때 중요한 건 비교 횟수가 아니라 디스크를 몇 번 읽느냐예요.

이진 트리는 노드 하나에 키가 1개뿐이라 높이가 log₂ n이에요. 반면 B-트리는 한 노드에 키를 수백 개씩 담아 페이지 하나를 꽉 채워요. 한 노드에서 갈라지는 가지가 수백 개면 높이가 log₍수백₎ n으로 확 줄어요. 예를 들어 가지가 100개씩이라면 높이 3만으로도 약 100만 개(100³)를 다룰 수 있어요. 디스크 몇 번만 읽으면 원하는 데이터에 도달하는 거죠.

데이터베이스 인덱스에서 널리 쓰이는 B+ 트리는 실제 데이터 포인터를 잎 노드에만 두고 잎들을 옆으로 연결해 놓아서, 범위 검색("2024년 1월~3월 주문")을 할 때 잎을 쭉 따라가며 순차적으로 읽을 수 있어요. MySQL의 InnoDB 저장 엔진 인덱스가 B+ 트리 구조를 쓰는 대표적인 예예요.

여기까지 핵심 배열은 위치 계산으로, 해시는 키를 위치로 바꾸는 계산으로, 트리는 절반씩 버리는 비교로 빠르다. 그리고 B-트리는 "저장 장치는 블록 단위로 읽는다"는 하드웨어 사실에 맞춰 트리 모양을 바꾼 결과다. 효율은 결국 연산의 성격 + 하드웨어의 성격에 구조를 맞춘 정도다.

5. 힙과 우선순위 큐: "제일 급한 것만 알면 돼"

응급실을 생각해 봐요. 환자 전체를 중증도 순으로 완벽하게 정렬해 둘 필요는 없어요. 지금 가장 위급한 한 명만 정확히 알면 돼요. 이런 질문에 특화된 게 힙(heap)이에요.

"완벽한 정렬" 대신 "느슨한 규칙"

최소 힙의 규칙은 딱 하나예요. 부모는 자식보다 작거나 같다. 형제끼리의 순서는 신경 안 써요. 이렇게 규칙을 느슨하게 잡으니 유지 비용이 확 줄어요.

연산이진 힙정렬된 배열균형 BST
최솟값 보기O(1)O(1)O(log n) (최소 포인터 유지 시 O(1))
최솟값 꺼내기O(log n)O(1)~O(n)*O(log n)
삽입O(log n)O(n)O(log n)
n개로 처음 만들기O(n)O(n log n)O(n log n)
임의 값 탐색O(n)O(log n)O(log n)

* 정렬 방향에 따라 맨 끝에서 꺼내면 O(1), 맨 앞에서 꺼내면 원소를 밀어야 해서 O(n)

균형 BST로도 우선순위 큐를 만들 수 있지만, 힙은 배열 하나로 구현된다는 큰 장점이 있어요. 완전 이진 트리 모양을 유지하기 때문에, 인덱스 i 노드의 자식은 2i+1, 2i+2, 부모는 (i−1)/2로 계산만 하면 돼요(0부터 셀 때). 포인터가 필요 없으니 메모리도 아끼고 캐시도 좋아해요. 또 n개 원소로 힙을 한 번에 만드는 건 아래에서부터 정리하면 O(n)이면 돼요. 정렬(O(n log n))보다 싸죠.

import heapq
tasks = []
heapq.heappush(tasks, (3, "메일 답장"))
heapq.heappush(tasks, (1, "서버 장애 대응"))
heapq.heappush(tasks, (2, "회의 준비"))
print(heapq.heappop(tasks))  # (1, '서버 장애 대응') — 가장 급한 일부터

힙이 빛나는 곳은 많아요. 다익스트라 최단 경로 알고리즘에서 "아직 확정 안 된 정점 중 가장 가까운 것"을 고를 때, 운영체제나 이벤트 시뮬레이션에서 "다음에 실행할 작업"을 고를 때, 대용량 데이터에서 "상위 k개"만 뽑을 때(크기 k짜리 힙을 유지하면 O(n log k)) 등이에요. 다익스트라는 이진 힙을 쓰면 O((V+E) log V)로 동작해요.

주의: 힙은 정렬된 상태가 아니에요 힙 배열을 그냥 출력해 보면 순서가 뒤죽박죽처럼 보여요. 정상이에요! 보장되는 건 "맨 앞이 최소"뿐이에요. 전체를 정렬된 순서로 얻으려면 하나씩 꺼내야 해요(이게 힙 정렬이에요).

6. 스택·큐·덱: 할 줄 아는 게 적어서 빠르다

"기능이 적을수록 빠르다"는 걸 가장 잘 보여주는 친구들이에요. 이들은 어디서 넣고 어디서 빼는지를 딱 정해 놓았어요.

📚 스택 (LIFO)마지막에 넣은 게 먼저 나와요. 접시 쌓기처럼요. 함수 호출 기록, 실행 취소(Ctrl+Z), 괄호 짝 검사, 깊이 우선 탐색(DFS)에 써요. 끝에서만 넣고 빼니 동적 배열 끝 연산으로 O(1).
🚶 큐 (FIFO)먼저 온 게 먼저 나가요. 줄 서기처럼요. 작업 대기열, 프린터 스풀, 너비 우선 탐색(BFS)에 써요. 원형 배열(링 버퍼)이나 연결 리스트로 앞뒤 O(1).
↔️ 덱 (Deque)양쪽 끝에서 다 넣고 뺄 수 있어요. 슬라이딩 윈도우 최댓값 같은 알고리즘에 딱이에요. Python의 collections.deque가 대표적이에요.

여기서 유명한 실수 하나! 파이썬 list로 큐를 만들어서 pop(0)을 하는 경우예요. list는 동적 배열이라 맨 앞을 빼면 나머지를 전부 앞으로 당겨야 해서 O(n)이에요. 데이터가 많아지면 BFS가 이유 없이 느려져요. collections.deque의 popleft()는 O(1)이에요. 같은 "큐"라는 개념이라도 밑바탕 구조가 성능을 결정하는 완벽한 예시죠.

from collections import deque
q = deque([1, 2, 3])
q.append(4)      # 뒤에 추가: O(1)
q.popleft()      # 앞에서 꺼내기: O(1)  ← list.pop(0)은 O(n)

7. 그래프 표현: 같은 지도, 다른 장부

SNS 친구 관계, 지하철 노선도, 웹 페이지 링크는 모두 그래프(정점과 간선)예요. 그런데 같은 그래프라도 메모리에 적는 방식에 따라 잘하는 일이 달라요.

같은 그래프, 두 가지 장부 A B C D 정점 4개, 간선 4개 인접 행렬 ABCD ABCD 0110 1001 1001 0110 인접 리스트 A: B, C B: A, D C: A, D D: B, C 행렬: 칸 V×V개, "A-B 연결?" O(1) 리스트: 공간 V+E, 이웃 순회가 빠름

빼곡한 그래프엔 행렬, 듬성듬성한 그래프엔 리스트가 유리해요.

질문/조건인접 행렬인접 리스트
메모리O(V²)O(V + E)
u와 v가 연결됐나?O(1)O(u의 이웃 수)
u의 모든 이웃 순회O(V)O(u의 이웃 수)
BFS/DFS 전체O(V²)O(V + E)
어울리는 그래프간선이 빽빽한(조밀) 그래프간선이 듬성한(희소) 그래프

현실의 큰 그래프는 대부분 희소해요. SNS 사용자가 수억 명이라도 한 사람의 친구는 수백~수천 명 수준이죠. 만약 사용자 1억 명을 인접 행렬로 만들면 칸이 1억 × 1억 = 10¹⁶개가 필요해서, 칸 하나를 1비트로 줄여도 1,000테라바이트가 넘어요. 그래서 대규모 그래프는 인접 리스트나 이를 압축한 CSR(Compressed Sparse Row) 같은 희소 표현을 써요. 정보 지능공학 쪽에서 많이 다루는 그래프 신경망(GNN)이나 추천 시스템도 이런 희소 표현 위에서 돌아가요.

8. 질문 하나에 올인한 특수 구조들

이제부터는 "딱 한 가지 질문을 기가 막히게 잘하는" 특수 요원들이에요. 이 친구들을 보면 효율은 질문에 맞춘 설계에서 나온다는 원리가 더 선명해져요.

🔤 트라이(Trie): 접두사 전문가

검색창에 "자료"까지 치면 "자료구조", "자료형"이 쭉 뜨잖아요? 이런 접두사 검색에 특화된 게 트라이예요. 문자열을 글자 단위로 쪼개서 나무의 경로로 저장해요. 공통 접두사는 경로를 공유하니까, 길이 m인 접두사를 찾는 데 저장된 단어 개수와 상관없이 O(m)이에요.

해시 테이블은 "자료구조"라는 완전한 단어가 있는지는 빨리 알지만, "자료로 시작하는 단어 전부"는 전체를 훑어야 해요. 트라이는 "자료" 노드까지만 내려가면 그 아래가 전부 답이에요. 대가는 메모리예요. 노드마다 자식 링크를 들고 있어야 해서, 공간을 줄이려고 경로를 압축한 래딕스 트리 같은 변형을 쓰기도 해요. IP 라우팅 테이블의 최장 접두사 일치 검색에도 트라이 계열 구조가 쓰여요.

🌸 블룸 필터: "확실히 없음"만 장담하는 구조

블룸 필터는 1970년 Burton Bloom이 제안한 확률적 구조예요. 비트 배열 하나와 해시 함수 여러 개로 "이 원소가 집합에 있나?"를 답해요. 신기한 성질이 있어요.

❌ "없다"는 답100% 정확해요. 거짓 음성(있는데 없다고 하는 실수)이 없어요.
❓ "있을 수도"라는 답가끔 틀려요. 거짓 양성(없는데 있다고 하는 실수)이 일정 확률로 생겨요.

정확도를 조금 포기하는 대신 원소를 통째로 저장하지 않으니 메모리를 엄청나게 아껴요. 일반적으로 원소당 약 10비트 정도면 거짓 양성률을 대략 1% 수준으로 맞출 수 있다고 알려져 있어요. 그래서 "디스크까지 가서 확인하기 전에, 확실히 없는 건 미리 걸러내기" 용도로 딱이에요. LSM 트리 기반 저장소인 RocksDB, Cassandra, HBase 등이 블룸 필터를 이렇게 활용해요. 효율이란 꼭 정답률 100%가 아니어도 된다는, 꽤 철학적인 교훈을 주는 구조예요.

👥 유니온-파인드: "같은 그룹이야?"의 달인

"A와 B가 같은 무리에 속하나?", "이 두 무리를 합쳐라" 이 두 연산만 엄청 많이 반복된다면? 서로소 집합(Disjoint Set), 일명 유니온-파인드가 답이에요. 각 그룹을 대표 원소를 뿌리로 하는 나무로 표현하고, 두 가지 최적화를 더해요.

랭크(또는 크기) 기준 합치기: 작은 나무를 큰 나무 밑에 붙여서 높이가 쓸데없이 커지지 않게 해요.
경로 압축: 대표를 찾으러 올라가는 김에 지나간 노드들을 대표에 바로 붙여버려요. 다음엔 한 방에 찾아요.

두 기법을 함께 쓰면 연산당 분할상환 비용이 역 아커만 함수 α(n)에 비례하는데, 이 함수는 우주에 있는 원자 수만큼의 n을 넣어도 4~5를 넘지 않을 만큼 느리게 자라서, 실용적으로는 거의 상수 시간이에요. 크루스칼 최소 신장 트리 알고리즘, 이미지의 연결 영역 찾기 등에 써요.

🪜 스킵 리스트: 연결 리스트에 급행 노선 깔기

연결 리스트의 약점은 "중간까지 걸어가야 한다"였죠. 스킵 리스트는 여기에 급행열차 노선을 겹겹이 깔아요. 맨 아래 층은 모든 역에 서고, 위층으로 갈수록 무작위로 뽑힌 일부 역만 서요. 위층에서 크게 건너뛰다가 아래층으로 내려가며 정밀하게 찾으니 평균 O(log n)이에요. 균형 트리 같은 복잡한 회전 없이 동전 던지기 확률로 균형을 얻는 셈이죠. Redis의 정렬 집합(Sorted Set)이 내부적으로 스킵 리스트를 사용하는 것으로 잘 알려져 있어요.

정리: 특수 구조들의 공통점 트라이는 접두사, 블룸 필터는 "확실한 부재", 유니온-파인드는 그룹 소속, 스킵 리스트는 단순한 정렬 유지. 모두 질문을 좁히는 대신 그 질문만큼은 극단적으로 빠르게 만든 구조예요. 범용성과 특화 성능은 대체로 맞바꾸는 관계예요.

9. 효율의 원리, 네 가지 법칙으로 정리하기

여기까지 많은 구조를 봤는데, 사실 이들이 빠른 이유는 몇 가지 공통 원리로 묶을 수 있어요.

① 미리 정리해 둔 정보정렬, 힙 규칙, 해시 위치처럼 데이터에 구조를 부여해 두면, 질문할 때 볼 필요가 없는 부분을 건너뛸 수 있어요. 대신 삽입·삭제 때마다 그 구조를 유지하는 비용을 내요.
② 계산으로 바로 가기배열 인덱스, 해시 함수처럼 "어디 있는지"를 계산 한 번으로 알면 탐색 자체가 사라져요.
③ 매번 절반 이상 버리기이진 탐색, 트리, 스킵 리스트처럼 비교 한 번마다 후보를 크게 줄이면 로그 시간이 돼요.
④ 하드웨어와 박자 맞추기연속 메모리(캐시 라인), 블록 단위 읽기(B-트리)처럼 기계가 잘하는 방식에 맞추면 같은 복잡도에서도 몇 배가 빨라져요.

공짜 점심은 없다: 대표적인 트레이드오프

얻는 것내주는 것예시
빠른 조회느린 삽입(정렬 유지)정렬된 배열
평균 O(1) 조회순서 정보, 여분 메모리해시 테이블
순서 + O(log n) 보장포인터 메모리, 구현 복잡도레드-블랙 트리
최솟값에 대한 빠른 접근임의 탐색 능력힙
극적인 메모리 절약정확도(거짓 양성)블룸 필터
빠른 접두사 검색큰 메모리 사용트라이

이 표는 사실 하나의 이론적 사실과도 연결돼요. 비교만으로 정렬하는 알고리즘은 최악의 경우 Ω(n log n)번보다 적게 비교할 수 없다는 것이 증명되어 있어요. 그래서 만약 어떤 구조가 "삽입 O(1)"과 "최솟값 꺼내기 O(1)"을 동시에 비교만으로 보장한다면, 그걸로 O(n)에 정렬이 가능해지니 모순이에요. 어딘가에 비용을 내야만 한다는 걸 수학이 보증해 주는 셈이죠. (피보나치 힙 같은 구조가 삽입을 분할상환 O(1)로 만들 수 있는 것도, 최솟값 삭제에 O(log n)을 지불하기 때문이에요.)

10. 실전에서 데이터 구조 고르는 법

이론은 충분! 이제 친구가 "나 이거 뭐 써야 돼?" 하고 물으면 이렇게 답해 주면 돼요. 핵심은 "가장 자주 하는 질문이 뭔지"부터 생각하는 거예요.

주로 하는 작업추천 구조한 줄 이유
순서대로 쌓고, 번호로 읽기동적 배열O(1) 접근 + 캐시 최고
키로 값 찾기, 중복 제거해시 맵 / 해시 셋평균 O(1)
정렬 상태 유지 + 범위 검색균형 BST(TreeMap 등)최악 O(log n), 순서 유지
가장 우선순위 높은 것 반복 처리힙(우선순위 큐)꺼내기 O(log n), 배열 기반
되돌리기, 재귀 흉내스택끝에서만 O(1)
도착 순서대로 처리큐 / 덱양끝 O(1)
자동완성, 접두사 검색트라이단어 수와 무관한 O(m)
대용량에서 "없는 것" 빠르게 거르기블룸 필터아주 작은 메모리
디스크 기반 대량 인덱스B+ 트리디스크 접근 횟수 최소화
그룹 합치기·소속 판단유니온-파인드사실상 상수 시간
질문 목록 만들기: 내 프로그램이 데이터에 던지는 질문(조회, 삽입, 삭제, 범위, 최솟값…)을 적어요.
빈도 매기기: 어떤 질문이 초당 수만 번이고 어떤 게 하루 한 번인지 따져요. 자주 하는 연산을 빠르게 해야 해요.
데이터 규모 확인: 원소가 수십 개면 그냥 배열이 이길 때가 많아요. 복잡도 차이는 n이 커져야 의미가 생겨요.
보장 수준 결정: 평균만 빨라도 되는지, 최악도 막아야 하는지(실시간 시스템, 외부 입력) 결정해요.
측정하기: 마지막은 언제나 벤치마크와 프로파일링이에요. 캐시와 상수 계수는 표에 안 나와요.
조합의 힘을 기억하세요 실전 고수들은 구조 하나만 쓰지 않아요. LRU 캐시는 해시 맵 + 이중 연결 리스트로 "키 조회 O(1) + 최근 사용 순서 갱신 O(1)"을 동시에 얻어요. Python 3.7부터 dict가 삽입 순서를 보장하는 것도 해시 인덱스와 별도의 조밀한 엔트리 배열을 함께 쓰는 설계 덕분이에요. 각 구조의 장점만 빌려오는 거죠.

11. 정보 지능공학에서 만나는 데이터 구조

AI와 데이터 시대가 오면서 "어떤 질문을 빨리 답해야 하는가"가 또 바뀌었어요. 그리고 그에 맞춰 새로운 데이터 구조가 무대 중앙에 섰어요.

벡터 검색: "가장 비슷한 것"을 찾는 질문

문장이나 이미지를 임베딩 벡터(수백~수천 차원의 숫자 묶음)로 바꾸면, "이 질문과 의미가 가장 비슷한 문서는?"이 "가장 가까운 벡터는?"이라는 질문이 돼요. 정확히 답하려면 모든 벡터와 거리를 재야 해서 O(n)이에요.

저차원에서는 공간을 나누는 KD-트리 같은 구조가 효율적이지만, 차원이 높아지면 이른바 차원의 저주 때문에 가지치기가 잘 안 돼서 전수 조사와 큰 차이가 없어져요. 그래서 고차원 벡터 검색에서는 정확도를 살짝 양보하는 근사 최근접 이웃(ANN) 구조가 주로 쓰여요. 대표적인 것이 그래프를 여러 층으로 쌓은 HNSW(Hierarchical Navigable Small World)인데, 위층에서 크게 이동하고 아래층에서 세밀하게 찾는 모습이 앞서 본 스킵 리스트와 닮았어요. 원리가 세대를 넘어 재활용되는 게 참 재밌죠.

희소 행렬과 텐서

추천 시스템의 "사용자 × 상품" 행렬은 대부분 칸이 비어 있어요. 이걸 그대로 2차원 배열로 저장하면 메모리 낭비가 극심하죠. 그래서 0이 아닌 값과 그 위치만 저장하는 CSR, COO 같은 희소 행렬 형식을 써요. 그래프에서 인접 리스트를 쓰던 것과 똑같은 논리예요. 반대로 신경망의 가중치처럼 값이 빽빽한 데이터는 연속 메모리 배열(텐서)에 담아 GPU가 한꺼번에 처리하게 해요. 결국 AI 시대에도 "조밀하면 연속 배열, 희소하면 위치 기록"이라는 원리는 그대로예요.

정보 지능공학 관점의 핵심 새로운 기술이 나와도 데이터 구조 선택 원리는 같아요. ① 어떤 질문을 자주 하나 ② 데이터는 어떤 모양(조밀/희소, 저차원/고차원)인가 ③ 어떤 하드웨어(CPU 캐시, GPU, 디스크) 위에서 도나 ④ 정확도를 얼마나 양보할 수 있나. 이 네 가지가 구조를 결정해요.

12. 마무리: 데이터 구조는 "질문에 대한 준비"다

처음 질문으로 돌아가 볼게요. 왜 일부 데이터 구조는 특정 작업에 더 효율적일까요? 이제 한 문장으로 답할 수 있어요.

데이터 구조는 앞으로 받을 질문을 예상하고 미리 정리해 둔 결과물이고, 그 정리 방식이 질문과 잘 맞을수록 빠르며, 맞지 않는 질문에는 오히려 느려진다.

배열은 "몇 번째?"를 예상했고, 해시 테이블은 "이 키 있어?"를, 균형 트리는 "순서대로/범위로"를, 힙은 "제일 급한 건?"을, 트라이는 "이걸로 시작하는 건?"을, 블룸 필터는 "확실히 없는 건?"을 예상했어요. 그리고 각자 그 준비를 위해 메모리든, 다른 연산의 속도든, 정확도든 무언가를 지불했어요.

좋은 개발자와 데이터 엔지니어의 실력은 결국 "이 문제에서 진짜 자주 하는 질문이 뭔가"를 꿰뚫어 보는 눈에서 갈려요. 이런 감각은 이론 공부와 함께 실제 코드를 짜고 측정해 보는 경험에서 길러지는데, 재능넷 같은 재능 공유 플랫폼에서 알고리즘 코칭이나 코드 리뷰를 주고받으며 다른 사람의 시선으로 내 선택을 점검해 보는 것도 좋은 방법이에요.

다음에 코드를 짤 때, 습관처럼 리스트를 꺼내기 전에 딱 3초만 스스로 물어봐요. "나는 이 데이터에 무슨 질문을 제일 많이 하지?" 그 3초가 프로그램을 수십, 수백 배 빠르게 만들 수도 있어요. 🚀

#시간복잡도#캐시지역성#해시테이블#균형트리#B트리#힙#트레이드오프
댓글 작성

이 글에 대한 여러분의 생각을 들려주세요

댓글 0
댓글을 불러오는 중입니다.

아직 댓글이 없습니다.