리스트·배열·문자열·딕셔너리의 역할

학생 다섯 명의 점수를 저장한다고 해 봅시다. 출석 번호 순서대로 리스트에 담아 두면 "세 번째 학생의 점수"는 바로 꺼낼 수 있지만, "민수의 점수"를 알려면 이름을 처음부터 하나씩 비교해야 합니다. 반대로 이름을 키로 삼는 딕셔너리에 담으면 이름으로는 바로 찾을 수 있지만 "세 번째 학생"이라는 질문에는 답하기 어려워집니다. 이처럼 같은 값이라도 어떤 구조에 담느냐에 따라 빠르게 할 수 있는 작업이 달라지고, 알고리즘의 비용도 그에 따라 달라집니다. 이 글에서는 Python으로 알고리즘을 짤 때 가장 자주 쓰는 리스트, 문자열, 딕셔너리가 각각 어떤 작업을 빠르게 하고 어떤 작업에서 느려지는지를 메모리 안의 모양에서부터 살펴봅니다.

배열은 번호로 칸의 위치를 계산한다

배열(array)은 크기가 같은 칸을 메모리에 빈틈없이 이어 붙인 구조입니다. 칸 하나의 크기가 s바이트이고 첫 칸이 주소 a에서 시작한다면, i번째 칸의 주소는 a + i × s라는 계산 한 번으로 나옵니다. 그래서 배열은 0번째 칸이든 100만 번째 칸이든 같은 시간에 읽을 수 있고, 이 작업의 비용은 O(1)입니다. 인덱스가 0부터 시작하는 것도 이 식과 관련이 있습니다. 첫 칸의 주소가 a + 0 × s, 곧 시작 주소 그대로가 되기 때문입니다.

Python의 리스트(list)는 이 배열 방식 위에 만들어져 있습니다. 다만 원소의 값을 칸에 직접 넣지 않고, 값이 들어 있는 객체를 가리키는 참조(reference)를 칸에 넣습니다. 참조는 가리키는 값이 정수든 문자열이든 크기가 같으므로, 여러 종류의 값을 섞어 담아도 i번째 칸의 위치를 같은 식으로 계산할 수 있습니다. 함수·리스트·복사와 작은 검사에서 두 이름이 같은 리스트를 가리키는 별칭이 생긴 것도 변수와 리스트의 칸이 모두 참조를 담기 때문이었습니다.

numbers = [10, 20, 30, 40, 50]
print(numbers[0], numbers[2], numbers[4])
print(numbers[-1], numbers[-2])
print(len(numbers))

10 30 50
50 40
5

음수 인덱스는 끝에서부터 셉니다. numbers[-1]은 마지막 원소이고 numbers[-2]는 그 앞 원소입니다. Python은 음수 인덱스 -i를 len(numbers) - i번째 칸으로 바꾸어 읽으므로 이 작업도 O(1)입니다. 길이가 5인 리스트에서 쓸 수 있는 인덱스는 0부터 4까지와 -1부터 -5까지이고, 그 밖의 인덱스로 읽으면 IndexError: list index out of range가 납니다.

끝에 붙이기는 빠르고 앞에 끼우기는 느리다

리스트는 길이가 늘었다 줄었다 하지만, 배열은 처음 잡은 칸 수가 정해져 있습니다. Python은 이 차이를 메우려고 실제 원소 수보다 칸을 넉넉하게 잡아 둡니다. append로 끝에 원소를 붙일 때 남는 칸이 있으면 참조 하나를 써 넣기만 하면 되므로 O(1)입니다. 남는 칸이 없으면 더 큰 공간을 새로 잡고 기존 참조를 모두 옮겨야 해서, 그 한 번은 원소 수에 비례하는 O(n)이 듭니다.

옮기는 일이 얼마나 자주 일어나는지는 직접 확인할 수 있습니다. 아래 코드 첫 줄의 import sys는 표준 라이브러리의 sys 모듈(module)을 불러와, 그 안의 함수를 sys.이름처럼 모듈 이름을 붙여 쓸 수 있게 합니다. sys.getsizeof는 객체가 차지하는 메모리 크기를 바이트로 돌려주는데, 리스트는 칸을 새로 잡을 때만 이 값이 바뀝니다. 아래 코드는 빈 리스트에 원소를 하나씩 붙이면서 크기가 바뀐 순간의 길이를 모읍니다.

import sys

values = []
last = sys.getsizeof(values)
grew_at = []
for n in range(1, 70):
    values.append(n)
    size = sys.getsizeof(values)
    if size != last:
        grew_at.append(n)
        last = size
print(grew_at)

[1, 5, 9, 17, 25, 33, 41, 53, 65]

69번 붙이는 동안 공간을 새로 잡은 것은 아홉 번뿐이고, 그 사이의 간격은 4, 4, 8, 8, 8, 8, 12, 12로 점점 넓어집니다. Python 3.14와 3.15의 CPython에서 실행한 결과이며, 늘리는 비율은 구현마다 다를 수 있습니다. 중요한 것은 늘릴 때마다 지금 크기에 비례해 여유를 더 잡는다는 점입니다. 그러면 드물게 일어나는 큰 이동 비용을 그 사이의 많은 append가 나누어 지는 셈이 되어, append 한 번에 드는 평균 비용이 상수로 묶입니다. 이렇게 연산 여러 번에 걸친 총비용을 횟수로 나누어 따지는 방법을 분할상환 분석(amortized analysis)이라 하고, append의 비용을 분할상환 O(1)이라고 말합니다.

맨 앞에 끼우는 insert(0, x)는 사정이 다릅니다. 0번 칸을 비우려면 원래 있던 원소를 모두 한 칸씩 뒤로 밀어야 하기 때문입니다. 맨 앞을 꺼내는 pop(0)도 마찬가지로, 빈 0번 칸을 메우려고 나머지를 한 칸씩 앞으로 당깁니다. 아래 함수는 insert(0, x)가 안에서 하는 일을 반복문으로 풀어 쓰고, 몇 번 옮겼는지 셉니다.

def insert_front(cells, value):
    cells.append(None)
    moves = 0
    for i in range(len(cells) - 1, 0, -1):
        cells[i] = cells[i - 1]
        moves += 1
    cells[0] = value
    return moves


cells = [20, 30, 40]
print(insert_front(cells, 10), cells)
print(insert_front(cells, 0), cells)

3 [10, 20, 30, 40]
4 [0, 10, 20, 30, 40]

먼저 끝에 빈 칸을 하나 만들고, 뒤에서부터 앞 칸의 값을 한 칸씩 뒤로 옮긴 다음 비워진 0번 칸에 새 값을 넣습니다. 원소가 n개일 때 앞에 하나를 끼우려면 n번 옮겨야 하므로 비용은 O(n)입니다. 중간 위치 k에 끼우거나 지울 때도 k 뒤의 원소를 모두 옮기므로, 뒤쪽 원소의 개수에 비례하는 비용이 듭니다. 실제 리스트의 insert는 이 이동을 C로 작성한 반복으로 처리해서 위의 Python 반복문보다 훨씬 빠르지만, 옮겨야 하는 원소의 개수는 같습니다.

이 차이는 앞에서 꺼내는 작업을 반복하는 알고리즘에서 크게 드러납니다. 먼저 들어온 것을 먼저 꺼내는 대기열을 리스트와 pop(0)으로 흉내 내면, 원소 n개를 모두 꺼내는 동안 (n - 1) + (n - 2) + … + 1 + 0 = n(n - 1)/2번을 옮기게 되어 전체 비용이 O(n²)이 됩니다. 큐와 너비 우선 탐색 BFS에서는 양쪽 끝 모두에서 O(1)로 넣고 꺼낼 수 있는 collections.deque를 써서 이 문제를 피합니다.

슬라이스는 새 리스트를 만든다

슬라이스(slice) numbers[1:3]은 인덱스 1부터 3 앞까지, 곧 1번과 2번 원소를 담은 새 리스트를 만듭니다. 변수·조건·반복으로 상태 읽기의 range처럼 시작은 포함하고 끝은 포함하지 않는 반열린 구간입니다. 새 리스트를 만들려면 참조를 하나씩 복사해야 하므로, 원소 k개를 자르는 비용은 O(k)입니다. numbers[:]나 list(numbers)처럼 전체를 자르면 리스트 전체를 복사하는 O(n)이 듭니다.

새로 만든 리스트이므로, 그 뒤에 원본을 바꿔도 잘라 둔 쪽은 바뀌지 않습니다. 이름만 하나 더 붙인 별칭은 그렇지 않습니다.

numbers = [10, 20, 30]
part = numbers[1:3]
whole_copy = list(numbers)
alias = numbers
alias.append(40)
print(numbers)
print(part)
print(whole_copy)

[10, 20, 30, 40]
[20, 30]
[10, 20, 30]

alias.append(40)은 alias가 가리키는 리스트, 곧 numbers와 같은 리스트에 40을 붙였으므로 numbers를 출력하면 40이 보입니다. part와 whole_copy는 그 전에 따로 만든 리스트라서 영향을 받지 않습니다. 다만 이 복사는 칸에 든 참조만 복사하는 얕은 복사(shallow copy)라서, 원소가 다시 리스트라면 안쪽 리스트는 원본과 함께 씁니다. 이 차이는 1장의 얕은 복사 설명에서 다루었습니다.

문자열은 바꿀 수 없는 문자의 나열이다

문자열(str)도 문자들을 순서대로 늘어놓은 것이라서, 인덱스와 슬라이스가 리스트와 같은 방식으로 동작합니다. 차이는 한 번 만든 문자열의 내용을 바꿀 수 없다는 점입니다. 이런 성질을 불변(immutable)이라고 합니다. 특정 위치의 문자를 바꾸려고 하면 오류가 납니다.

text = "가나다"
print(text[0], text[1:])
text[0] = "하"

가 나다
Traceback (most recent call last):
  File "C:\algo\lesson.py", line 3, in <module>
    text[0] = "하"
    ~~~~^^^
TypeError: 'str' object does not support item assignment

바꾼 문자열이 필요하면 새 문자열을 만들어야 합니다. "하" + text[1:]은 원본을 그대로 두고 "하나다"라는 새 문자열을 만듭니다. 이 성질은 문자열을 조금씩 이어 붙이는 반복문에서 비용 문제로 이어집니다. result += piece는 겉보기에는 끝에 덧붙이는 것 같지만, 원칙적으로는 지금까지의 내용을 모두 복사한 새 문자열을 매번 만듭니다. 길이가 1인 조각 n개를 이렇게 이으면 복사하는 양이 1 + 2 + … + n에 비례해 O(n²)이 될 수 있습니다.

그래서 조각을 많이 이어야 할 때는 조각을 리스트에 모았다가 마지막에 join으로 한 번에 합칩니다. join은 먼저 조각들의 길이를 모두 더해 필요한 크기의 문자열을 한 번에 만들고, 그 안에 조각을 차례로 복사하므로 전체 길이에 비례하는 비용으로 끝납니다.

parts = []
for n in range(1, 6):
    parts.append(str(n * n))
print(", ".join(parts))

1, 4, 9, 16, 25

", ".join(parts)는 parts의 조각 사이에 ", "를 끼워 넣어 합친 문자열을 돌려줍니다. CPython에는 +=의 복사를 줄이는 최적화가 있지만 동작하는 조건이 까다롭고 다른 Python 구현에는 없습니다. 그래서 Python의 코딩 스타일 지침인 PEP 8도 성능이 중요한 곳에서는 join을 쓰라고 권합니다.

더 깊이: 인덱스 한 칸이 화면의 한 글자는 아니다

Python 문자열의 인덱스는 유니코드 코드 포인트(code point) 하나를 한 칸으로 셉니다. 코드 포인트는 유니코드가 문자마다 붙인 번호입니다. "가"는 보통 코드 포인트 하나(U+AC00)로 쓰지만, 초성 ㄱ(U+1100)과 중성 ㅏ(U+1161) 두 개를 이어서 같은 모양을 나타낼 수도 있습니다. 앞의 방식을 NFC, 뒤의 방식을 NFD라는 정규화(normalization) 형식이라고 부릅니다.

import unicodedata

composed = "가"
decomposed = unicodedata.normalize("NFD", composed)
print(len(composed), len(decomposed))
print([hex(ord(c)) for c in decomposed])
print(composed == decomposed)
print(unicodedata.normalize("NFC", decomposed) == composed)

1 2
['0x1100', '0x1161']
False
True

화면에는 둘 다 "가"로 보이지만 길이는 1과 2이고, == 비교도 거짓입니다. 운영체제나 프로그램에 따라 한글을 분해된 형태로 저장하기도 하므로, 밖에서 받은 문자열을 비교하거나 길이를 셀 때는 unicodedata.normalize로 형식을 맞춘 뒤에 다루는 것이 안전합니다. 이모지처럼 여러 코드 포인트가 모여 한 글자로 보이는 경우도 있어서, "글자 수"를 셀 때는 무엇을 한 글자로 볼지부터 정해야 합니다.

딕셔너리는 키로 값의 위치를 찾는다

리스트에서 "민수의 점수"를 찾으려면 이름을 하나씩 비교해야 해서 O(n)이 듭니다. 딕셔너리(dict)는 이름 같은 키(key)와 값(value)을 짝지어 저장하고, 키를 주면 그 값을 평균 O(1)에 찾습니다. 키에서 저장 위치를 바로 계산하기 때문입니다.

scores = {"민수": 90, "지수": 85}
scores["하늘"] = 77
print(scores["민수"])
print("지수" in scores, "보라" in scores)
print(scores.get("보라", 0))
print(list(scores))
print(scores["보라"])

90
True False
0
['민수', '지수', '하늘']
Traceback (most recent call last):
  File "C:\algo\lesson.py", line 7, in <module>
    print(scores["보라"])
          ~~~~~~^^^^^^^^
KeyError: '보라'

scores["하늘"] = 77처럼 없는 키에 값을 대입하면 새 짝이 추가되고, 있는 키에 대입하면 값이 바뀝니다. 없는 키를 대괄호로 읽으면 마지막 줄처럼 KeyError가 납니다. 키가 없을 수도 있다면 in으로 먼저 확인하거나, get(키, 기본값)으로 키가 없을 때 쓸 값을 정해 둡니다. 딕셔너리의 in은 키가 있는지를 확인하며, 값이 있는지는 90 in scores.values()처럼 따로 확인해야 하고 이때는 값을 하나씩 비교하는 O(n)이 듭니다. list(scores)의 출력에서 보듯 딕셔너리는 키를 넣은 순서도 기억합니다. Python 3.7부터 언어 규칙으로 정해진 성질이라 어떤 Python 구현에서나 같습니다.

딕셔너리가 키에서 위치를 계산할 때는 해시 함수(hash function)를 씁니다. 해시 함수는 키를 정수 하나로 바꾸는 함수이고, 기본 아이디어는 그 정수를 칸 수로 나눈 나머지를 저장 위치로 삼는 것입니다. Python의 hash 함수가 이 정수를 돌려주며, 0 이상의 작은 정수의 해시값은 그 정수 자신입니다. 칸이 8개라면 키 42는 42 % 8 = 2번 칸에 들어갑니다.

print(hash(42), 42 % 8)
print([key % 8 for key in [3, 11, 19, 5]])

42 2
[3, 3, 3, 5]

두 번째 줄처럼 서로 다른 키가 같은 칸을 가리킬 수도 있습니다. 이것을 충돌(collision)이라 하며, Python은 충돌이 나면 정해진 규칙에 따라 다른 빈 칸을 찾아가는 열린 주소 방식(open addressing)으로 처리합니다. 충돌이 드물면 몇 칸 만에 자리를 찾으므로 평균 O(1)이지만, 많은 키가 한곳에 몰리면 한 번 찾는 데 O(n)까지 걸릴 수 있습니다. 그래서 딕셔너리의 O(1)은 평균에 대한 말이고, 모든 입력에서 성립하는 최악의 경우는 아닙니다. 참고로 문자열의 해시값은 프로그램을 실행할 때마다 달라지도록 섞여 있습니다. 일부러 충돌하는 키를 대량으로 보내 프로그램을 느리게 만드는 공격을 어렵게 하려는 것입니다.

키는 해시값을 계산할 수 있어야 하므로, 리스트를 키로 쓰면 오류가 납니다.

cell = {[0, 1]: "벽"}

Traceback (most recent call last):
  File "C:\algo\lesson.py", line 1, in <module>
    cell = {[0, 1]: "벽"}
           ^^^^^^^^^^^^^^
TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

리스트는 내용을 바꿀 수 있어서, 키로 저장한 뒤 내용이 바뀌면 해시값도 달라져 원래 칸에서 다시 찾을 수 없게 됩니다. 그래서 Python은 리스트의 해시값 계산을 아예 막아 두었습니다. 예전 버전의 Python에서는 괄호 안의 unhashable type: 'list' 부분만 오류 메시지로 나옵니다. 좌표처럼 여러 값을 묶은 키가 필요하면 바꿀 수 없는 튜플(tuple)을 써서 {(0, 1): "벽"}처럼 만듭니다. 해시와 충돌은 단순 문자열 탐색·롤링 해시·충돌에서 다시 만납니다.

자주 하는 작업으로 구조를 고른다

지금까지 본 비용을 표로 모으면 다음과 같습니다. 문자열은 위치로 읽는 비용이 리스트와 같지만, 바꾸는 작업은 모두 새 문자열을 만듭니다.

어느 구조가 더 좋다고 말할 수는 없습니다. 위치나 순서로 다루는 일이 많으면 리스트가, 이름으로 찾는 일이 많으면 딕셔너리가 알맞습니다. 두 작업이 모두 잦다면 리스트와 딕셔너리를 함께 두고 둘을 같이 갱신하기도 합니다. CPython의 연산별 비용은 Python 공식 문서의 내장 타입 연산의 시간 복잡도에 정리되어 있습니다.

정리

• 배열은 칸의 위치를 계산 한 번으로 찾으므로 인덱스로 읽기가 O(1)입니다. Python 리스트는 원소를 가리키는 참조를 배열에 담습니다.
• append는 여유 칸을 미리 잡아 두는 덕분에 분할상환 O(1)이지만, 앞이나 중간에 끼우거나 지우면 뒤쪽 원소를 모두 옮겨야 해서 O(n)입니다.
• 슬라이스와 list(...)는 새 리스트를 만드는 얕은 복사이고, 별칭은 같은 리스트를 가리키는 이름이 하나 더 생길 뿐입니다.
• 문자열은 불변이라서 바꾸는 작업마다 새 문자열이 생깁니다. 조각을 많이 이어 붙일 때는 리스트에 모아 join으로 합칩니다.
• 딕셔너리는 해시값으로 키의 위치를 계산해 평균 O(1)에 찾습니다. 키는 해시값을 계산할 수 있어야 하므로 리스트 대신 튜플을 씁니다.

연습 문제

1. 쓸 수 있는 인덱스

letters = ["a", "b", "c", "d"]에서 오류 없이 쓸 수 있는 인덱스를 음수까지 모두 쓰고, letters[-4]가 무엇인지 답하세요.

2. 슬라이스를 별칭으로 바꾸면

본문의 슬라이스 예제에서 part = numbers[1:3]을 part = numbers로 바꾸면 세 줄의 출력은 어떻게 될까요?

numbers = [10, 20, 30]
part = numbers
whole_copy = list(numbers)
alias = numbers
alias.append(40)
print(numbers)
print(part)
print(whole_copy)
print(part is numbers, whole_copy is numbers)

[10, 20, 30, 40]
[10, 20, 30, 40]
[10, 20, 30]
True False

3. 리스트로 만든 대기열의 이동 횟수

손님 6명이 줄을 선 리스트에서 pop(0)으로 한 명씩 모두 꺼냅니다. 원소를 옮기는 횟수는 모두 몇 번일까요? 손님이 n명이면 어떻게 될까요?

def pop_front_moves(cells):
    moves = 0
    for i in range(1, len(cells)):
        cells[i - 1] = cells[i]
        moves += 1
    cells.pop()
    return moves


line = ["가", "나", "다", "라", "마", "바"]
total = 0
while line:
    total += pop_front_moves(line)
print(total)

15

다음 글 순차 탐색과 자기 조직화에서는 정렬되지 않은 리스트에서 값을 찾는 가장 단순한 방법과, 자주 찾는 값을 앞으로 옮겨 다음 탐색을 빠르게 하려는 전략을 봅니다. 이 글의 리스트와 딕셔너리는 뒤에서 힙, 스택, 큐, 그래프의 인접 목록을 만드는 재료로 다시 쓰입니다.