[자료구조 01] 자료구조가 왜 필요한가

프로그램이 하는 일을 가만히 들여다보면 대부분 데이터를 담아 두고, 필요할 때 꺼내거나 찾거나 바꾸는 일입니다. 회원 명단, 장바구니에 담은 상품, 시험 점수판이 모두 그렇습니다. 이때 그 데이터를 어떤 모양으로 담아 둘지 정하는 것이 자료구조(data structure, 자료를 담고 정리하는 방식)입니다. 놀랍게도 같은 값이라도 어디에 담느냐에 따라 찾는 속도가 수천 배까지 벌어집니다. 이 글에서는 파이썬의 리스트와 딕셔너리를 나란히 놓고, 자료구조를 왜 배워야 하는지를 짧은 코드로 직접 쳐 보며 확인하겠습니다. 코드는 모두 파이썬에서 그대로 실행되는 것이니, 눈으로만 읽지 말고 한 줄씩 따라 쳐 보시면 훨씬 오래 남습니다.

01.1 자료구조는 데이터를 담는 그릇입니다

물을 병에 담느냐 넓은 쟁반에 담느냐에 따라 편한 상황이 다릅니다. 데이터도 똑같습니다. 순서대로 죽 늘어놓아야 다루기 편한 데이터가 있고, 이름표를 붙여 그 이름으로 바로 찾는 게 편한 데이터가 있습니다. 어떤 그릇을 고르느냐에 따라 같은 일도 쉬워지기도, 번거로워지기도 합니다. 파이썬에 기본으로 들어 있는 자료구조 중 가장 많이 쓰는 둘이 리스트(list, 목록)와 딕셔너리(dictionary, 사전)입니다. 리스트는 순서가 중요한 데이터에 잘 맞습니다. 시간 순으로 쌓이는 기록이나 차례가 있는 목록이 그렇습니다. 딕셔너리는 순서보다 이름으로 빠르게 찾는 게 중요한 데이터에 잘 어울립니다.

리스트는 값을 순서대로 한 줄로 늘어놓는 그릇입니다. 줄을 세워 놓았다고 생각하면 됩니다.

names_list = ["kim", "lee", "park", "choi"]
print(names_list[1])

lee

대괄호 [ ] 안에 값을 콤마로 나열하고, names_list[1]처럼 순번(인덱스)으로 꺼냅니다. 여기서 순번은 0부터 세기 때문에 [0]이 첫 번째 값, [1]이 두 번째 값입니다. 처음에는 헷갈리지만, 파이썬을 비롯한 많은 언어가 0부터 센다는 점을 기억해 두면 됩니다.

01.2 이름표로 바로 찾는 딕셔너리

딕셔너리는 값마다 이름표를 붙여 두고 그 이름으로 값을 꺼내는 그릇입니다. 이 이름표를 키(key)라고 부릅니다. 전화번호부를 떠올리면 쉽습니다. 이름을 알면 번호를 바로 찾을 수 있듯이, 키를 알면 값을 바로 꺼냅니다.

phone = {"홍길동": "010-1111", "김철수": "010-2222"}
print(phone["홍길동"])

010-1111

중괄호 { } 안에 키: 값 형태로 담습니다. phone["홍길동"]처럼 키를 대면 그 값이 곧바로 나옵니다. 리스트가 몇 번째인지를 알아야 꺼낼 수 있다면, 딕셔너리는 순번을 몰라도 이름만 알면 됩니다. 그런데 이 둘은 겉보기엔 비슷해 보여도, 값을 찾는 속도에서 큰 차이가 납니다. 그 차이를 이제부터 눈으로 확인해 보겠습니다.

01.3 있는지 물어보기, 리스트에도 집합에도

어떤 값이 자료구조 안에 들어 있는지 묻고 싶을 때 in을 씁니다. 회원 명단에 lee가 있는지 확인해 보겠습니다. 여기서는 리스트와 함께 집합(set, 중복 없는 값들의 모음)도 같이 놓아 비교하겠습니다. 집합은 딕셔너리에서 값을 뺀, 키만 모아 둔 그릇이라고 생각하면 편합니다.

names_list = ["kim", "lee", "park", "choi"]
names_set = {"kim", "lee", "park", "choi"}
print("lee" in names_list)
print("lee" in names_set)

True
True

둘 다 True, 있다고 똑같이 답합니다. 결과만 보면 아무 차이가 없습니다. 하지만 컴퓨터가 이 답을 내기까지 속으로 하는 일의 양은 완전히 다릅니다. 데이터가 적을 때는 그 차이가 드러나지 않다가, 개수가 많아지면 확 벌어집니다.

01.4 같은 찾기인데 속도가 수천 배 다릅니다

데이터를 잔뜩 넣어 보면 차이가 드러납니다. 10만 개가 든 리스트와 집합에서, 맨 끝에 있는 값을 여러 번 찾아 걸린 시간을 재 보겠습니다. 맨 끝 값을 고른 이유는, 그 자리가 리스트에게 가장 불리하기 때문입니다.

import timeit
N = 100000
big_list = list(range(N))
big_set = set(range(N))
target = N - 1 # 맨 끝에 있는 값
t1 = timeit.timeit(lambda: target in big_list, number=1000)
t2 = timeit.timeit(lambda: target in big_set, number=1000)
print(round(t1, 4), "초 (리스트)")
print(round(t2, 6), "초 (집합)")

0.8743 초 (리스트)
0.000083 초 (집합)

측정값은 컴퓨터 사정에 따라 달라지지만, 이번 실행에서는 집합이 약 1만 배 빨랐습니다. 왜 이렇게 차이가 날까요. 리스트는 순서대로만 담겨 있어서, 찾는 값이 나올 때까지 앞에서부터 하나씩 비교하는 수밖에 없습니다. 맨 끝 값을 찾느라 10만 번 가까이 비교한 것입니다. 반면 집합은 키를 특별한 계산식에 넣어 자리를 바로 알아내고 한 번에 찾습니다. 이 계산식을 해시(hash, 값을 자리 번호로 바꾸는 계산)라고 하며, 딕셔너리도 같은 원리로 빠릅니다. 이 실험이 말해 주는 것은 분명합니다. 리스트의 값 찾기는 데이터가 늘수록 느려지지만, 딕셔너리와 집합은 데이터가 아무리 많아도 찾는 수고가 거의 그대로라는 사실입니다.

01.5 얼마나 빨라지는지 재는 말, 빅오

방금 본 차이를 개발자들은 빅오 표기법(Big-O notation)이라는 짧은 기호로 나타냅니다. 데이터 개수를 n이라 할 때, 일의 양이 n에 따라 얼마나 늘어나는지를 재는 눈금입니다. 처음에는 낯선 기호지만, 뜻은 아주 단순합니다.

리스트에서 값 찾기처럼 개수에 비례해 늘어나면 O(n)이라고 씁니다. n이 2배면 수고도 2배라는 뜻입니다. 집합이나 딕셔너리에서 값 찾기처럼 개수와 거의 상관없이 일정하면 O(1)이라고 씁니다. 100개가 들었든 100만 개가 들었든 드는 수고가 비슷하다는 뜻입니다.

정확한 초가 아니라 늘어나는 경향을 본다는 점이 중요합니다. 그래서 데이터가 몇 개 안 될 땐 무엇을 써도 비슷하지만, 개수가 커질수록 O(1)과 O(n)의 거리가 무섭게 벌어집니다. 앞의 10만 개 실험에서 본 1만 배 차이가 바로 그 벌어짐입니다. 빅오 하나만 익혀 두어도, 코드를 돌려 보기 전에 이 코드가 데이터가 많아질 때 버틸지 아닐지를 가늠할 수 있습니다.

01.6 자료구조를 배우면 달라지는 것

자료구조를 안다는 것은 이 상황엔 어떤 그릇에 담아야 빠른가를 고를 줄 안다는 뜻입니다. 자주 찾아야 하는 데이터라면 리스트에 쌓아 두고 매번 훑는 대신, 딕셔너리나 집합에 담아 O(1)로 찾게 만드는 식입니다. 이 판단 하나만 몸에 익혀도 굼뜨던 프로그램이 눈에 띄게 빨라지는 경우가 많습니다. 반대로 자료구조를 모르면, 성능 문제를 만났을 때 어디를 고쳐야 할지조차 감이 오지 않습니다. 처음에는 리스트 하나로 모든 걸 해결하려 하기 쉽습니다. 하지만 조금씩 다른 그릇들을 익혀 두면, 상황마다 가장 알맞은 것을 골라 쓸 수 있게 됩니다. 오늘 쳐 본 코드를 직접 실행해, 같은 데이터를 리스트와 집합 두 그릇에 담아 찾는 느낌이 어떻게 다른지 손으로 확인해 보시기 바랍니다.