TIL_31 : 자료 구조

🙄 자료 구조

---

➡ 자료 구조란?

• 데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리 방식
• 우리가 데이터를 저장하고 관리하기 위해 사용하는 구조
• 여러가지 성격의 데이터를 컴퓨터에 저장하고 가지고 올 수 있어야 함

➡ 상황에 맞는 자료 구조

• list 와 set 은 자료 구조 이름이 아닌 자료형 이름
• 두 자료형은 서로 다른 구조, 방식을 이용해서 데이터를 저장

import time

# 0 ~ 1000000을 list 에 저장한다
test_list = [x for x in range(1000001)]

# 0 ~ 1000000을 set 에 저장한다
test_set = set([x for x in range(1000001)])

# 특정 데이터가 list 에 있는지 확인할 때 걸리는 시간 파악
t_0 = time.time()
print(1000000 in test_list)
t_1 = time.time()

print("list 에서 걸린 시간: {}".format(t_1 - t_0))

# 특정 데이터가 set 에 있는지 확인할 때 걸리는 시간 파악
t_0 = time.time()
print(1000000 in test_set)
t_1 = time.time()

print("set 에서 걸린 시간: {}".format(t_1 - t_0))

# True
# list 에서 걸린 시간: 0.011967658996582031
# True
# set 에서 걸린 시간: 5.245208740234375e-06 == 0.0000005245

👉 list 보다 약 3000배 빠른 set
👉 항상 set 이 좋은 자료형은 아님
👉 모든 경우에 제일 좋은 자료 구조는 없음
👉 상황에 따라 알맞은, 효율적인 자료 구조 존재

🙄 컴퓨터가 데이터를 저장하는 방법

---

• 자료구조의 목적 : 자료를 구조화 ➡ 데이터를 효율적으로 사용
• 컴퓨터에 데이터가 어떻게 저장되는지 알아야 함
• 데이터가 저장되는 곳 : 스토리지(Storage), 메모리(Memory)
  
  

➡ 스토리지 vs 메모리

스토리지

• 데이터가 영구적으로 저장되는 곳
• 데이터를 저장하는 데, 받아오는 데 오래 걸림
• 정확히 언제 사용할지 모르겠는 파일 저장

메모리

• 데이터가 임시로 저장되는 곳
• 데이터를 저장하는 데, 받아오는 데 빠름
• 지금 당장 사용해야 할 데이터를 저장

자료 구조는 데이터를 메모리에서 잘 사용하는 것이 목적

➡ RAM (Random Access Memory)

메모리는...

• 일정한 칸으로 나눠져 있다
• 각 칸에 데이터를 저장할 수 있다
• 각 칸은 자신만의 주소가 있다

RAM (Random Access Memory)

• 임의 접근 : 저장 위치를 알면 접근할 때 항상 일정한 시간 소요
• 시간 복잡도 : $O(1)$
• 순차 접근 : 저장된 위치까지 가는데 한 단계씩 거처야 함 (like 선형 탐색)

👉 임의 접근이 순차 접근보다 효율적이다
👉 자료 구조를 공부할 때 데이터에 임의 접근 [$O(1)$] 하고있다는 것 알아야

➡ 레퍼런스 (reference)

• 데이터에 접근할 수 있게 해주는 값
• 주소 보다 조금 더 포괄적인 표현
• 자료 구조를 배울 때는 주소 = 레퍼런스 라고 생각해도 무방

1. x = 95
2. print(x + 5) == print(95 + 5)

1.1 : "X는 95다" 는 틀린 표현
1.2 : X는 95가 아닌 95가 담겨 있는 메모리 주소를 갖고 있음
1.3 : "X는 95를 가리킨다" 는 맞는 표현

2 : 실제로 변수를 사용할 때는 저장된 값을 알아서 받아옴

Aliasing

• 여려 변수가 같은 메모리를 가리키는 것

list1 = [1, 2]
list3 = [1, 2, 3]

list2 = list1

print(id(list1))
print(id(list2))
print(id(list3))

# 2034033767360
# 2034033767360
# 2034034079872