배열과 리스트

🎯 학습 목표

이 강을 마치면 배열이 메모리에서 어떻게 놓이는지, 그래서 왜 인덱스 접근은 O(1)인데 중간 삽입·삭제는 O(n)인지 설명할 수 있습니다. 그리고 파이썬 리스트가 배열과 어떻게 다른지, 코딩 테스트에서 리스트 때문에 시간 초과가 나는 전형적인 패턴과 그 대안을 익히게 됩니다.

자료구조 강의를 배열부터 시작하는 이유가 있습니다. 거의 모든 자료구조가 배열 위에 올라가 있기 때문입니다. 뒤에 나올 스택·큐·힙도 내부는 배열입니다.

💡 배열은 왜 인덱스 접근이 빠른가

배열(array)은 같은 크기의 칸을 메모리에 연속으로 붙여 놓은 자료구조입니다. 이 "연속"이라는 성질 하나가 모든 특성을 결정합니다.

배열의 메모리 배치

  인덱스     0      1      2      3      4
          ┌──────┬──────┬──────┬──────┬──────┐
  값      │  10  │  20  │  30  │  40  │  50  │
          └──────┴──────┴──────┴──────┴──────┘
  주소     1000   1008   1016   1024   1032
           ↑      ↑
        시작 주소  칸 하나가 8바이트라고 가정

  ▲ 3번 인덱스의 주소는?
    1000 + 8 × 3 = 1024

    → 계산 한 번으로 바로 찾아간다. 앞을 훑지 않는다.
    → 그래서 arr[3] 은 O(1)이다.
    → 배열 크기가 100만이어도 계산은 똑같이 한 번이다.

핵심은 "시작 주소 + 칸 크기 × 인덱스"라는 곱셈 한 번으로 위치가 정해진다는 점입니다. 몇 번째 칸이든 같은 비용이 듭니다. 이것을 임의 접근(random access)이라고 부릅니다.

그런데 이 장점이 곧 단점이 됩니다. 연속으로 붙어 있어야 하므로, 중간에 끼워 넣으려면 뒤를 전부 밀어야 합니다.

중간 삽입은 왜 O(n)인가

  [10, 20, 30, 40, 50] 의 인덱스 1에 15를 넣으려면

  단계 1) 뒤쪽을 한 칸씩 민다
     10 │    │ 20 │ 30 │ 40 │ 50
              ←──── 4개를 옮겨야 한다

  단계 2) 빈 자리에 넣는다
     10 │ 15 │ 20 │ 30 │ 40 │ 50

  ▲ 맨 앞에 넣으면 n개 전부를 민다  → O(n)
    맨 뒤에 넣으면 밀 것이 없다     → O(1)

  삭제도 똑같다. 중간을 빼면 뒤를 당겨 와야 한다.

  ▲ 결론
    배열은 '읽기'에 강하고 '중간 수정'에 약하다.

여기서 맨 뒤 추가·삭제만 O(1)이라는 사실을 기억해 두세요. 5강 스택에서 이 성질을 그대로 활용합니다.

📖 파이썬 리스트는 정확히 무엇인가

파이썬에는 array라는 이름의 자료형이 따로 있지만, 실무와 코딩 테스트에서 쓰는 것은 리스트(list)입니다. 리스트는 동적 배열(dynamic array)입니다. 배열의 성질을 그대로 가지면서 두 가지가 다릅니다.

항목	고전적인 배열	파이썬 리스트
크기	고정	자동으로 늘어남
담는 값	같은 자료형만	아무 자료형이나 섞어도 됨
인덱스 접근	O(1)	O(1)
맨 뒤 추가	-	상각 O(1)
중간 삽입·삭제	O(n)	O(n)

"자동으로 늘어난다"는 것은 공간이 부족해지면 더 큰 공간을 새로 잡아 통째로 옮긴다는 뜻입니다. 2강에서 본 상각 O(1)이 여기서 나옵니다. 옮기는 순간만 O(n)이고, 그런 일은 드물게 일어납니다.

리스트의 주요 연산을 복잡도와 함께 정리하면 다음과 같습니다. Python Wiki의 TimeComplexity 문서 기준입니다.

연산	복잡도	이유
lst[i]	O(1)	주소 계산 한 번
lst.append(x)	상각 O(1)	맨 뒤라 밀 것이 없음
lst.pop()	O(1)	맨 뒤 제거
lst.insert(0, x)	O(n)	전부 뒤로 밀어야 함
lst.pop(0)	O(n)	전부 앞으로 당겨야 함
x in lst	O(n)	앞에서부터 비교
lst.sort()	O(n log n)	정렬 알고리즘
len(lst)	O(1)	길이를 따로 저장해 둠

이 표에서 빨간불은 세 개입니다. insert(0, x), pop(0), in. 이 셋이 반복문 안에 들어가는 순간 전체가 O(n²)이 됩니다.

💻 실전 예제 — 앞쪽 삽입이 만드는 함정

숫자를 역순으로 모으는 간단한 작업을 세 가지 방법으로 비교해 보겠습니다.

import time
from collections import deque

n = 100_000

# 방법 A : 맨 앞에 계속 삽입  → 매번 O(n) → 전체 O(n^2)
start = time.perf_counter()
a = []
for i in range(n):
    a.insert(0, i)             # 넣을 때마다 기존 원소를 전부 민다
time_a = time.perf_counter() - start

# 방법 B : 맨 뒤에 넣고 마지막에 뒤집기 → O(n) + O(n) = O(n)
start = time.perf_counter()
b = []
for i in range(n):
    b.append(i)                # 맨 뒤는 밀 것이 없다
b.reverse()                    # 한 번만 뒤집는다
time_b = time.perf_counter() - start

# 방법 C : deque 사용 → 양쪽 끝 모두 O(1)
start = time.perf_counter()
c = deque()
for i in range(n):
    c.appendleft(i)            # 앞쪽 추가도 O(1)
time_c = time.perf_counter() - start

print(a == b == list(c))       # True : 결과는 셋 다 같다
print(f"insert(0): {time_a:.3f}s")
print(f"append+reverse: {time_b:.3f}s")
print(f"deque: {time_c:.3f}s")

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

• a.insert(0, i) — 인덱스 0에 넣습니다. 기존 원소를 전부 한 칸씩 뒤로 밀어야 하므로 O(n)입니다. 이것을 n번 반복하니 전체가 O(n²), 즉 100억 번 수준의 이동이 발생합니다.
• b.append(i) — 맨 뒤에 붙이므로 밀 것이 없습니다. n번 해도 O(n)입니다.
• b.reverse() — 리스트를 뒤집습니다. 이것도 O(n)이지만 한 번만 합니다. 그래서 전체가 O(n)입니다.
• from collections import deque — 덱(deque)은 파이썬 표준 라이브러리의 자료구조로, 양쪽 끝에서의 추가·삭제가 모두 O(1)입니다.
• c.appendleft(i) — 덱의 앞쪽에 넣습니다. 리스트의 insert(0, x)와 결과는 같지만 비용이 다릅니다.
• a == b == list(c) — 세 결과가 모두 같은지 확인합니다. True가 나옵니다. 답은 같고 시간만 다릅니다.

실행해 보면 방법 A만 눈에 띄게 느립니다. 정확한 초는 환경마다 다르지만 A가 B·C보다 수백 배 느리다는 결과는 동일합니다. n을 100,000에서 200,000으로 두 배 늘리면 A는 네 배가 되고, B·C는 두 배가 됩니다. 이것이 O(n²)와 O(n)의 차이입니다.

정리하면 앞쪽에서 넣고 빼는 일이 잦다면 리스트 대신 덱을 씁니다. 덱은 6강 큐에서 본격적으로 다룹니다.

⚠️ 자주 하는 실수

첫째, pop(0)으로 큐를 흉내 냅니다. 앞에서 하나씩 꺼내는 처리는 매우 흔한데, lst.pop(0)은 O(n)입니다. n개를 전부 꺼내면 O(n²)이 됩니다. 덱의 popleft()를 쓰면 O(1)로 끝납니다.

둘째, 2차원 리스트를 곱셈으로 만듭니다. [[0] * 3] * 3처럼 만들면 같은 리스트 객체가 세 번 참조되어, 한 줄을 바꾸면 세 줄이 다 바뀝니다. [[0] * 3 for _ in range(3)]처럼 리스트 컴프리헨션으로 만들어야 각 행이 독립적입니다. 이것은 격자 문제에서 매우 자주 나오는 버그입니다.

셋째, 반복 중에 리스트를 수정합니다. for x in lst로 순회하면서 lst.remove(x)를 하면 인덱스가 밀려 일부 원소를 건너뜁니다. 조건에 맞는 것만 남긴 새 리스트를 만드는 방식이 안전합니다.

넷째, 슬라이싱 비용을 잊습니다. lst[1:]은 새 리스트를 복사해서 만듭니다. O(n)이고 메모리도 그만큼 씁니다. 반복문 안에서 슬라이싱하면 O(n²)이 됩니다. 인덱스로 범위를 지정하는 방식으로 바꾸면 복사를 피할 수 있습니다.

다섯째, 리스트에서 최댓값을 반복해서 찾습니다. max(lst)는 O(n)입니다. 반복문 안에서 매번 호출하면 O(n²)입니다. 최댓값을 자주 꺼내야 한다면 21강의 힙이 알맞은 도구입니다.

📝 핵심 요약 + 다음 강 예고

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

#	기억할 것
1	배열은 연속된 칸. 주소 계산으로 바로 찾아간다
2	그래서 인덱스 접근 O(1), 중간 삽입·삭제 O(n)
3	맨 뒤 추가·삭제만 O(1)
4	파이썬 리스트는 동적 배열 — 자동으로 늘어난다
5	빨간불 세 개: insert(0), pop(0), in
6	앞쪽 작업이 잦으면 deque
7	2차원 리스트는 컴프리헨션으로 만든다

지금 해 볼 것은 [[0] * 3] * 3과 [[0] * 3 for _ in range(3)]을 각각 만들어 [0][0]에 1을 넣어 보는 것입니다. 결과가 다른 것을 직접 확인하면 다시는 헷갈리지 않습니다.

다음 4강 「문자열 다루기」에서는 코딩 테스트 단골 주제인 문자열을 봅니다. 파이썬 문자열이 수정 불가능하다는 성질이 왜 중요한지, 그리고 join·슬라이싱·split 같은 기본 도구를 복잡도와 함께 정리하겠습니다.

📚 참고 자료

• TimeComplexity — Python Wiki
• Data Structures — Python 공식 문서
• collections.deque — Python 공식 문서