자료구조란?
- 자료구조
데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리 방식
단순히 0에서 1,000,000까지 있는 list와 set에서 원하는 수 하나를 찾는 데에 걸리는 시간이 set이 더 짧다. 그러나, 항상 set이 빠른 건 아니다. 상황별로 어떤 자료구조가 빠른지가 다르다.
따라서 각 상황에 맞는 효율적인 자료구조가 존재하며, 어떤 상황에 어떤 자료구조를 써야 하는지를 공부해보자.
자료구조의 목적
자료들을 어떻게 구조화할지 고민해서 데이터를 효율적으로 사용하는 것이 자료구조의 목적이다.
따라서 컴퓨터에 데이터가 어떻게 저장되는지 알아보자.
스토리지 vs 메모리
컴퓨터는 데이터를 크게 두 곳에 저장한다.
1. 스토리지(Storage)
데이터가 영구적으로 저장되는 곳. 사진, 노래, 영화, 워드 등이 여기에 보관된다. 많이 저장할 수 있는 대신, 데이터를 저장하는 시간이 오래 걸리고, 데이터를 받아오는 것도 오래 걸린다. 따라서 정확히 언제 사용할지 모르겠는 파일들을 스토리지에 보관한다.
2. 메모리(Memory)
메모리는 스토리지와 달리, 데이터를 임시로 저장하는 곳이다. 따라서 데이터를 저장하고 받아오는 데 빠르다.
워드에 글을 쓰고 있는 상황을 생각해보자. 아직 저장하지 않은 경우, 메모리에 임시적으로 저장된다. 이때 컴퓨터가 꺼지면 쓰던 글이 사라지는데 메모리에서는 임시로 이를 저장하고 있기 때문이다. 이걸 저장하면 문서가 메모리에서 스토리지로 복사되고, 스토리지에 영구적으로 저장된다.
보통 컴퓨터 사양 얘기할 때 RAM이 몇 GB냐 물어보는데, 여기에서 램이 이 메모리다. 내 4년된 맥북은 스토리지가 250GB고, 메모리가 8GB다....
스토리지와 메모리의 필요성
왜 데이터를 저장하는 데에 이 두 가지가 필요할까?
영화가 보고 싶은데, 스토리지에 영화가 저장되어 있다고 가정하자. 그럼 영화를 재생하면 한 장면, 한 장면이 실시간으로 스토리지에서 꺼내오면서 시간이 굉장히 오래 걸릴 것이다.
그래서 영화파일을 키면 스토리지에 있던 영화를 메모리로 복사한다. 메모리는 받아오는 게 빠르기 때문에 끊김없이 영화를 볼 수 있는 것이다. 영화를 끄면, 메모리에 있던 영화는 지워지고 스토리지에만 남게 된다.
자료구조를 공부할 땐, 스토리지보다 메모리에서 데이터를 잘 사용하는 것에 집중한다.
RAM(Random Access Memory, 임의 접근 메모리)
메모리는 비유하자면 하나의 긴 띠라고 할 수 있다. 일정하게 칸이 나뉘어져 있고, 각 칸에는 데이터를 담을 수 있다. 그리고 데이터를 찾을 수 있도록 각 칸에는 주소가 있다.
메모리 한 칸이 저장할 수 있는 기본적인 용량의 단위를 byte(바이트)하고 한다.
컴퓨터는 메모리에서 값들을 어떻게 받아올까?
RAM은 한국말로 임의 접근 메모리라고 한다.
여기서 임의 접근은 저장 위치를 알면 접근할 때 항상 일정한 시간이 걸린다.
램은 원하는 값이 어떤 주소에 있든 상관없이 일정한 시간으로 찾을 수 있다. 따라서 메모리에 저장한 데이터 접근 시간 복잡도는 O(1)이다.
비디오 테이프처럼 내가 원하는 위치를 찾기 위해서 한 단계씩 거치는 걸 순차 접근이라고 한다. 이와 다르게 임의 접근은 주소와 상관없이 항상 빠르게 갈 수 있어 훨씬 효율적이다.
레퍼런스
언어마다 조금씩 다르지만, 파이썬에서 x = 90 이 의미하는 건, 'x가 90이다' 가 아니라 'x는 90를 가리킨다' 고 말할 수 있다. x는 90이라는 값 자체를 가지고 있는 게 아니라, 90이 담겨있는 메모리 주소를 갖고 있다.
이렇게 데이터에 접근하게 해주는 값을 레퍼런스(reference)라고 한다.
여기서 주소는 메모리의 진짜 실질적인 주소 이고, 레퍼런스는 데이터에 접근할 수 있게 해주는 좀 더 포괄적인 표현이라고 할 수 있다.
파이썬에서 데이터가 저장되어 있는 주소를 알아내는 방법
파이썬의 id 함수를 이용하면 된다.
list1 = [1, 2]
print(id(list1)) # 140237662138184list1 = [1, 2]
list3 = [1, 2, 3]
# Aliasing을 통해 List1rhk list2를 같게 함
list2 = list1
print(id(list1)) # 140657629409160
print(id(list2)) # 140657629409160
## print(id(list3)) 140657629409096