세상에는 많은 데이터가 있습니다. 많다는 말이 부족할 정도로 방대한 양의 데이터가 존재하죠. 그러한 데이터를 구조적으로 관리하는 것은 프로그래밍 세계에서 아주 중요한 일입니다. 이 구조에 따라 서비스 성능이 결정되기 때문이죠.
이번 시간에는 알고리즘과 더불어 프로그래밍의 이해를 높이는 자료 구조에 대해 함께 배워보겠습니다.
💾 자료 구조
자료 구조는 데이터를 저장하고 관리하기 위해 사용하는 구조입니다. 도서관을 예로 들어봅시다. 춘향전을 찾기 위해서는 어떤 절차가 필요할까요? 우선, 문학 코너에 가야겠죠? 그 다음 고전, 그 중에서도 한문 고전 코너를 살펴볼 겁니다. 책장에는 다양한 기준으로 책이 놓여 있습니다. 출판 연도 혹은 책 이름 등으로 말이죠. 그 기준에 따라 원하는 책을 찾으면 됩니다.
이렇듯 원하는 책을 쉽게 찾을 수 있는 이유는 그 책이 일정한 구조 속에 있기 때문입니다. 여기서 문학, 한문 고전, 책 이름순 등이 구조의 예입니다.
이는 컴퓨터 프로그래밍에서도 적용될 수 있는데요. 컴퓨터에 데이터를 저장할 때도 도서관에 책을 정리하는 것처럼 일정한 구조에 맞춰 저장을 합니다. 컴퓨터 과학에서는 이러한 구조를 자료 구조라고 부릅니다. 자료 구조의 정확한 의미는 데이터의 효율적인 접근 및 조작을 가능하게 하는 저장 및 관리 방식입니다.
프로그래밍에서는 다양한 종류의 데이터를 다루는데요. 어떤 종류의 데이터든 컴퓨터에 저장하고 저장한 내용을 가져오는 것은 동일합니다.
💾 상황에 맞는 자료 구조
효율적인 프로그래밍을 하기 위해서는 다양한 자료 구조를 배우고 특정 상황에 적합한 구조를 고를 수 있는 능력을 기르는 것이 중요합니다.
잘못된 사례를 통해 적합한 자료 구조를 선택하는 것의 중요성을 보여 드리겠습니다. Python에는 리스트(list)와 세트(set)라는 자료형이 있습니다. 여기서 중요한 것은 두 자료형은 서로 다른 구조 혹은 방식을 통해 데이터를 저장한다는 점입니다. 코드를 함께 봅시다.
import time
# 0 ~ 1000000을 리스트에 저장
some_list = [x for x in range(0, 1000001)]
# 0 ~ 1000000을 세트에 저장
some_set = set([x for x in range(0, 1000001)])
# 특정 데이터가 리스트에 있는지 확인할 때 걸리는 시간 파악
time_0 = time.time()
print(100000 in some_list)
time_1 = time.time()
print(f"리스트 소요 시간: {time_1 - time_0}")
# 특정 데이터가 세트에 있는지 확인할 때 걸리는 시간 파악
time_0 = time.time()
print(100000 in some_set)
time_1 = time.time()
print(f"세트 소요 시간: {time_1 - time_0}")0에서 1000000까지의 수가 저장된 리스트와 세트를 각각 선언했습니다. 다음으로 in을 통해 1000000이라는 수가 리스트와 세트 속에 있는지 확인합니다. 이와 더불어, Python의 time 모듈을 통해 두 자료형이 같은 동작을 하는데 소요 되는 시간차를 보려고 합니다.
예시를 통해 위 코드의 내용을 설명하자면 도서관에서 책을 찾을 때, 이름 순으로 찾는 경우와 출판 연도 순으로 찾는 경우 중 어떤 경우가 더 빠른지를 확인하는 과정이라고 보면 됩니다.
코드를 실행해보겠습니다.
True
리스트 소요 시간: 0.01602315902709961
True
세트 소요 시간: 5.245208740234375e-06두 자료형 모두 1000000이라는 수를 가지고 있는 것으로 나왔습니다. 소요 시간을 살펴보면 두 자료형에서 차이가 있는데요. 세트에 저장되는 경우가 리스트에 저장되는 경우보다 약 3000배 정도 빠릅니다(e-06).
물론 0.016초가 전혀 긴 시간은 아닙니다. 그러나 데이터의 양이 늘어나서 시간이 10배, 100배, 1000배로 늘어난다면 어떻게 될까요? 프로그래밍에서 16초의 실행 속도는 굉장히 느린 수치입니다. 빠른 속도가 중요시 되는 현대 사회에서 16초의 실행 속도를 용인해주는 관대한 고객들은 많지 않습니다.
위 사례에서는 세트를 사용하는 것이 리스트를 사용하는 것보다 더 효율적이었습니다. 그러나 항상 세트가 리스트보다 더 좋은 것은 아닙니다. 모든 자료 구조는 저마다 다른 장단점을 가지고 있기 때문에 어떠한 경우에도 항상 좋은 자료 구조는 없습니다.
자료 구조를 공부하다 보면 어떤 자료 구조들이 존재하는지 알 수 있고 각 상황에 적합한 효율적인 자료 구조를 찾을 수 있게 됩니다.
💾 스토리지 vs. 메모리
자료 구조의 목적은 자료를 구조화해서 데이터를 효율적으로 사용하는 데 있습니다. 컴퓨터에 데이터가 어떻게 저장되는지 알면 자료 구조를 이해하는 데 도움이 됩니다.
컴퓨터가 데이터를 저장하는 곳은 크게 두 가지로 나뉩니다. 바로 스토리지(Storage)와 메모리(Memory)입니다.
스토리지는 데이터가 영구적으로 저장되는 곳입니다. 우리가 흔히 사용하는 음악, 사진, 영화 파일 등은 스토리지에 저장됩니다. 스토리지 속 데이터는 사용자가 직접 지우거나 컴퓨터가 외부로부터 심각한 충격을 받지 않는 이상 지워지지 않습니다.
하드 디스크, SSD가 바로 스토리지의 대표적인 예인데요. 이들은 보통 500GB, 1TB 등 많은 저장 공간을 가지고 있습니다. 그런데 스토리지는 정보를 많이 저장할 수 있는 대신 데이터를 저장하고 받아 오는 데 오랜 시간이 걸립니다.
창고의 경우를 떠올리면 쉬운데요. 저장 공간은 넓지만 그 안의 물건들을 옮기는 데에는 많은 시간이 걸립니다. 그래서 대개는 당장 사용할 물건보다는 나중에 사용한 물건들을 저장하는 경우가 많습니다. 스토리지도 마찬가지입니다. 스토리지에는 정확히 언제 사용할 지 모르는 파일을 저장하는 경우가 많죠.
영구적으로 저장하는 공간인 스토리지와 달리 메모리는 데이터를 임시로 저장하는 곳입니다. MS WORD로 과제를 작성한다고 가정해 봅시다. 글을 작성하고 저장하지 않으면 메모리에 임시로 글이 저장됩니다. 이 상태로 프로그램이 종료되면 작성한 글이 모두 사라집니다. 메모리에 임시로 저장되었기 때문이죠.
그러나 저장 버튼을 누르는 순간, 작성된 내용은 스토리지로 복사되고 영구적으로 저장됩니다. 그럼 프로그램이 종료되어도 내용이 사라지지 않고 남게 되죠.
메모리의 용량은 보통 8GB부터 32GB 정도인데요. 이는 스토리지에 비해 적은 수치입니다. 컴퓨터의 스펙을 말할 때, 흔히 언급되는 RAM이 바로 메모리입니다. 메모리는 스토리지보다 용량이 적은 대신에 데이터를 저장하고 불러오는 것이 빠릅니다.
메모리는 서랍 정도로 생각할 수 있는데요. 창고에 비해 크기는 작지만 물건을 빨리 꺼내올 수 있도록 손이 닿는 곳에 보관할 수 있죠. 그래서 메모리는 오래 보관할 데이터보다 지금 당장 사용해야 하는 데이터를 저장할 때 사용합니다.
그런데 저장 공간을 둘로 나누는 이유는 뭘까요? 하나만 사용하면 편할 텐데 말이죠. 컴퓨터에서 음악을 들을 때를 떠올려 봅시다. 우선, 음악 파일은 스토리지에 영구적으로 저장되어 있습니다. 그런데 음악 파일을 실행한다는 건 실제로는 저장 공간에서 음악의 마디마디마다 꺼내오는 것과 같습니다. 만약 이를 스토리지로부터 꺼내온다면 어떻게 될까요?
앞서 스토리지는 데이터를 가져오는 데 오랜 시간이 걸린다고 했습니다. 따라서, 스토리지에서 한 마디씩 음악을 꺼내 오면 음악이 계속 끊기게 됩니다.
이러한 문제를 해결해줄 수 있는 것이 바로 메모리입니다. 음악 파일을 실행하면 스토리지에 있던 파일이 메모리로 복사됩니다. 메모리는 데이터를 받아 오는 속도가 빠르기 때문에 끊김 없이 음악을 실행할 수 있습니다.
이후, 음악이 끝나 파일 실행을 종료하면 메모리에 있던 음악 데이터는 사라지고 다시 스토리지에만 남게 됩니다. 메모리는 용량이 적기 때문에 지금 당장 사용하지 않는 데이터는 바로 삭제됩니다. 이러한 이유 때문에 스토리지와 메모리가 나누어져 있는 것입니다.
자료 구조에서는 메모리를 중점적으로 다룹니다. 데이터를 메모리에서 잘 사용하도록 하는 것이 바로 자료 구조의 목적이니까요.
💾 RAM
메모리는 하나의 긴 띠로 비유할 수 있습니다. 이 띠는 일정한 칸으로 나눠져 있고 각 칸에 데이터를 저장할 수 있습니다. 또한 각 칸에는 자신만의 주소가 있는데요. 이는 데이터를 쉽게 찾기 위해 존재합니다.
예를 하나 들어보겠습니다.
x = 4
y = False위와 같이 변수를 선언하면 메모리의 특정 공간에 값이 저장됩니다. 컴퓨터에서는 어떻게 이 값들을 불러올까요?
앞서 메모리는 RAM이라고도 불린다고 했는데요. RAM은 Random Access Memory의 약어로, 우리말로는 임의 접근 메모리라 합니다.
여기서 임의 접근이란, 저장 위치를 알면 접근할 때 항상 일정한 시간이 걸린다는 것을 의미하는데요. 메모리의 각 칸에는 주소가 있다고 했죠? 임의 접근 방법으로는 그 주소가 32가 됐던 157이 됐던 126524가 됐던, 주소와는 상관없이 원하는 값을 한 번에 찾을 수 있습니다. 어떤 주소에 있든 데이터 접근에 걸리는 시간이 똑같기 때문에 시간 복잡도는 O(1)입니다.
이는 굉장히 효율적인 수치인데요. 잘 와닿지 않는 분들을 위해 다른 사례와 비교해보겠습니다. 아주 예전에 흔히 사용했던 비디오 테이프의 경우를 생각해봅시다. 비디오 테이프를 사용할 때, 원하는 위치로 가기 위해서는 현재 위치에서 테이프를 앞이나 뒤로 감아야 합니다. 만약 스타워즈를 보고 있는데 맨 뒷 장면을 보고 싶다면 그 위치까지 테이프를 돌려야 하죠.
이렇게 한 단계씩 모든 데이터를 거치는 방법을 순차 접근이라고 합니다. 이러한 방법은 더 먼 주소로 갈 수록 많은 시간을 소요하게 됩니다. 그런데 임의 접근을 활용하면 주소와 상관 없이 항상 빠르게 원하는 위치까지 갈 수 있으므로 순차 접근에 비하면 압도적으로 효율적입니다.
앞으로 자료 구조를 학습하며 메모리에 데이터를 저장하고 저장된 데이터를 찾는 등의 말이 자주 등장할 텐데요. 이때, 이 메모리가 바로 RAM이고 시간 복잡도가 O(1)인 임의 접근 방식을 사용한다는 사실을 꼭 기억해주세요.
💾 바이트(Byte)
메모리 한 칸이 저장할 수 있는 가장 기본적인 용량의 단위는 바이트(byte)입니다. 당장에는 바이트가 정확히 어느 정도의 크기인지는 알 필요 없습니다. 아주 단순하게 엄청 작은 단위 정도라고 생각하면 됩니다.
바이트가 아닌 다른 크기의 용량을 담는 저장 장치들도 있습니다. 그러나 대부분의 현대 컴퓨터 시스템들은 메모리 한 칸에 바이트만큼의 데이터를 저장합니다.
우리는 이미 kB(킬로 바이트), MB(메가 바이트), GB(기가 바이트) 등으로 바이트라는 단어를 접해본 적이 있습니다. 이들은 데이터의 용량이 몇 바이트인지를 표현한 겁니다. 정확히 말하자면, kB는 1,000바이트, MB는 1,000,000바이트, GB는 1,000,000,000바이트입니다.
자료 구조를 배우면서 바이트에 대해 알아둘 것은 딱 두 가지입니다. 첫째, 바이트는 컴퓨터 저장 공간 용량을 나타내는 단위라는 것. 둘째, 메모리 한 칸에 담기는 데이터 용량은 1바이트라는 것. 우선은 이 정도만 이해하고 넘어가셔도 무방합니다.
💾 레퍼런스
x = 2525라는 정숫값을 변수 x에 저장했습니다. 이로써 변수 x는 정수 25를 가지고 있다고 할 수 있습니다. 하지만 'x는 25이다'라는 표현은 틀립니다. 언어마다 차이는 있지만 적어도 Python에서는 그렇습니다. 이는 엄밀히 따지면 x가 25라는 값 자체를 가지고 있는 것이 아니라 25라는 값이 담긴 메모리 주소를 가지고 있는 것이기 때문입니다. 그리고 이 메모리 주소를 통해 정숫값 25를 찾아오는 것이죠. 따라서, 'x는 25를 가리킨다'라는 말이 좀 더 정확합니다.
이와 같이 데이터에 접근하게 해주는 값을 레퍼런스(reference)라고 합니다. 이는 추상적인 개념으로, 메모리 주소와는 다른 개념입니다. 이는 레퍼런스가 실질적인 주소라기보다는 데이터에 접근할 수 있도록 도와주는 값 혹은 활동을 포괄적으로 담은 표현이기 때문입니다. 그러니까 주소는 레퍼런스 자체라기보다는 레퍼런스의 한 종류인 셈이죠.
그러나 자료 구조를 학습할 때는 이 두 가지 표현을 동일하게 봐도 무방합니다. 그러니 앞으로는 주소보다는 레퍼런스라는 표현을 사용하겠습니다.
레퍼런스에 대해 배울 때, 사람들이 항상 물어보는 질문이 있습니다. 다음 코드를 함께 봅시다.
x = 25
print(x+5)위 코드를 보면 변수 x에 25를 넣고 x와 5를 더한 값을 출력합니다. 앞서 x는 25라는 정수를 가리키고 있다고 했는데요. 따라서, x에는 25가 아닌 레퍼런스가 담긴 셈입니다. 그럼 다음 줄에서 그 레퍼런스와 5를 더하는 걸까요?
x에 레퍼런스가 담겨 있는 건 맞지만 값을 사용할 때는 Python이 알아서 값을 불러옵니다. 다시 말해, Python이 메모리에 있는 25를 불러와서 25 더하기 5를 하는 것이죠. 이렇듯 Python이 보이지 않는 곳에서 위와 같은 작업을 하기 때문에 마치 변수 x가 정수 25 자체를 담고 있는 것처럼 느껴지는 겁니다.
💾 데이터 주소
❗ Python id 함수
id 함수를 사용하면 저장한 데이터의 메모리 주소를 정수로 표현한 값으로 알아낼 수 있습니다. 여러 타입의 데이터를 저장하고 id 함수를 써서 메모리 주소를 출력해보겠습니다.
some_list = [3, 6]
some_int = 4
some_float = 2.0
some_tuple = (3, 6)
print(id(some_list))
print(id(some_int))
print(id(some_float))
print(id(some_tuple))1827949071488
1827943508368
1827944138224
1827949052416각각 다른 주소에 저장되어 있는 것을 확인할 수 있습니다. 이 값은 컴퓨터에 따라서도 다르므로 다른 값이 나왔다고 해서 당황할 필요는 없습니다.
❗ 같은 주소에 저장되어 있는 데이터
당연한 말이지만 같은 주소에 저장되어 있는 데이터는 동일한 데이터입니다.
list_1 = [3, 6]
list_2 = [2, 4]
list_3 = list_1
print(id(list_1))
print(id(list_2))
print(id(list_3))2487634971776
2487634968704
2487634971776list_3에 list_1을 지정했더니 메모리 주소도 같은 값이 나왔습니다. 이는 하나의 리스트를 list_1, list_3이라는 서로 다른 변수가 가리키도록 했기 때문입니다. 이렇게 여러 변수가 같은 메모리를 가리키는 것을 Aliasing이라고 합니다.
반면, list_2는 두 변수와 다른 리스트를 가지고 있기 때문에 메모리 주소도 다르게 나옵니다.
이번 시간에는 자료 구조의 개념과 컴퓨터가 데이터를 저장하는 방법과 함께 스토리지와 메모리, 바이트, RAM, 레퍼런스, 데이터 주소에 대해 배웠습니다. 컴퓨터의 저장 구조를 생각하려니 조금은 복잡하셨죠? 하지만 이 내용이 숙지되어야 앞으로 배울 자료 구조를 좀 더 쉽게 이해할 수 있습니다.
다음 시간에는 본격적으로 자료 구조의 한 종류인 배열에 대해 함께 알아보도록 하겠습니다.
* 이 자료는 CODEIT의 '자료 구조' 강의를 기반으로 작성되었습니다.