[자료 구조] 데이터를 저장하는 방법

Jo sumin·2022년 3월 31일
0

자료구조

목록 보기
1/1

📚 자료 구조란?

도서관에서 책을 찾을 때 장르별로 나누고 일정 규칙에 맞춰 책에 주소를 붙여 정리하면, 찾으려는 책을 빠르게 찾을 수 있다. 컴퓨터도 마찬가지다. 빨리 데이터를 찾아 넘기려면 데이터를 일정 구조로 정리해야 한다.
자료구조는 데이터의 효율, 조작을 가능하게 하는 저장 및 관리 방식이다. 적합한 자료구조를 찾기 못했을 때 시간차가 많이 발생해 비효율적이다.

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

스토리지 VS 메모리

스토리지는 데이터가 영구적으로 저장되는 곳이고 용량도 크다. ex) 다운받은 사진, 영화, 비디오
-사용자가 직접 지우거나 물리적으로 훼손된 상태가 아니라면 지워지지 않는다.
창고처럼 많이 보관할 수 있지만 이동 속도가 느리다.
언제 사용할 지 모르는 파일들을 저장한다.

메모리는 데이터를 임시로 저장하고 용량이 작다. 만약 영화를 다운 받아 재생한다면, 스토리지에 영화 파일이 저장되고, 재생하는 동안에는 메모리에서 실행된다. 그리고 영화 실행창을 닫는다면 메모리에서 지워진다.

메모리를 RAM이라고도 말한다.

🏆 RAM

Random Access Memory, 임시 접근 메모리

: 메모리의 주소가 일단 주어지면 접근하는데 항상 일정한 시간이 걸린다.
주소가 1에 있든 101010101에 있든 단숨에 찾을 수 있다.
시간복잡도는 O(1)이다.
카세트 테이프처럼 맨 뒤의 부분을 듣고 싶다면 처음부터 시작해 기다리는 수밖에 없는데, 이건 순차 접근이다. 데이터를 찾으려면 더 많은 시간이 소요된다. 저장된 위치까지 가는데 항상 빠른 속도로 갈 수 있어 효율적이다.
📌메모리는 임의 접근으로 동작한다.

메모리에 데이터를 저장한다.
메모리에 저장된 데이터를 찾는다.

메모리_ 바이트

메모리는 한칸에 하나씩 값을 저장할 수 있고 각 칸마다 고유한 주소값이 부여된다.
여기에서 메모리 한 칸의 용량은 1바이트(byte)다.
그래서 1KB = 1000(10^3) byte(천), 1GB = 1000000 byte(10^6)(백만), 1MB = 1000000000(10^9) byte(10억)

🏓 레퍼런스(Reference)

레퍼런스는 주소와 조금 다른 의미다. 주소는 말그대로 메모리의 실제 주소를 말하는 것이고, 레퍼런스는 데이터가 접근하게 도와준다는 개념, 주소보다 더 포괄적인 개념이다.
예를 들어,

x = 95
print(x+5)

여기서 x는 95가 아니라,
95라는 데이터 값의 메모리 주소를 담고 있는 것이 x다.
그렇지만 print(x+5)를 했을 때 100이 나오는 이유는 사실, 95의 주소를 x를 보고 파이썬이 데이터 값 95를 찾아와 5를 더해주는 것이다.(레퍼런스 x와 5가 직접 더하는 게 아님)

레퍼런스와 주소는 보통 같은 의미로 쓰일 때도 있지만 아닐 때도 있다. (offset이 그 예)

📏 데이터 주소를 알고 싶다면 id()

데이터의 주소를 알고 싶다면 id() 를 이용하면 된다.

list1 = [1, 2, 3]
int1 = 0
print(id(list1))
print(id(int1))

# 140237662138184
# 4450309504 
# 결과 값이 다 다르다. 메모리 주소가 다 다르다.

📏 같은 주소에 저장되어 있는 두 데이터 Aliasing

다른 데이터값을 가진 list1과 list2가 있다.
여기서 list2 = list1 은, list1의 주소값을 list2가 가진 주소값과 같게 한다는 의미다.

# 리스트를 정의한다
list1 = [1, 2]
list2 = [1, 2, 3]
    
# Aliasing을 통해 list1과 list2를 같게 한다
list1 = list2
    
# 두 데이터의 메모리를 출력한다
print(id(list1))  # 140657629409160
print(id(list2))  # 140657629409160
print(id(list3))  # 140657629409096

list1과 list2이라는 변수 이름 자체는 다른 메모리에 저장되어 있겠지만, list1과 list2는 같은 주소값을 가리키게 된다. id()로 확인해보면, 주소값이 같다.

🎯 여기서, print(list1)과 print(list2)를 해보면, 동일하게 [1,2,3]이 나온다.
가리키는 주소값이 같고, 데이터 하나의 주소에 하나의 데이터 값이 들어가니 데이터 값도 같아질 수 밖에 없다.
list1 = list2로 list2가 좌항에 있고, 그 위치가 list2의 데이터값을 list1에 할당한다는 의미니까, 데이터값은 [1,2,3]으로 list1이 가리키는 값이 바뀌게 된다.


파이썬에서의 리스트가 C에서의 배열과 비슷한 개념이다. 동적 배열은 그 근본이 정적배열인데, 만약 그 배열 저장공간이 모자라면 그 크기의 2배이던가 정해서 늘려주는 것이다. 하지만 파이썬에서 채워지지 않은 없는 빈공간의 인덱싱을 프린트 했을 경우, 에러가 난다. 동적 배열쓰는 프로그램의 경우 배열의 실제 크기와 무관하게 실제로 저장되어 있는 값까지만 사용할 수 있게 한다.

🌟 추가연산

배열의 추가 연산

내부적으로는 정적배열을 쓴다.남은 공간이 있을 수도 없을 수도 있다.
추가 공간 배열 상태에 따라

  1. 내부적 공간에 남은 공간이 있을 때
    가장 빈 앞공간에 저장한다.
    인덱스를 이용해서 접근하기 때문에 O(1)
    최선의 경우다. 자주 발생

  2. 내부 여유 공간이 없을 때
    뒷 공간에 저장한다.
    현 사용 메모리보다 2배 더 큰 메모리로 예약한다. 기존 배열에서 새 배열로 싹다 복사해야 하는데,
    이게 인덱스 값 하나하나씩 복사 붙여넣기가 되는거라 O(n) 걸린다.
    최악의 경우다. 가끔 발생 _ 비합리적 상황, 보통은 최악의 경우로 시간 복잡도를 얘기하지만 이 경우는 가끔이니까.

🔮 분할 상환 분석

그래서 이 비합리함을 무마하기 위해 분할 상환을 한다.
쇼핑할 때 할부 개념이랑 똑같다. 18개월로 나눠내는 것처럼.

걸리는 총 동작 시간 / 동작횟수 로 1회 평균 동작 시간을 계산한다.
그럼 조금 더 합리적이다.

배열에서 걸리는 시간은 2가지다.
1. 새 인덱스를 넣는 시간
2. 기존 배열 크기가 부족해서 기존 인덱스를 새 배열로 복사 붙이기로 옮기는 시간

1번의 경우 n번 동작하면 n 번 걸린다.
2번의 경우 새 배열을 만들어 다시 입력할 경우와 다시 새 배열을 만들기 까지를 동작을 반복한다고 했을 때,
배열 안 요소 수 m, 가장 최근에 옮겨 저장한 요소수 n
무조건 m<n 이다.
추가연산 n번하고 가장 마지막에 옮긴 요소수 m이라면.
복사해서 걸리는 총 시간이 2m-1이다 m은 n보다 작다

새 데이터를 저장하는데 O(n), 새 데이터를 새 배열에 옮겨담는데에는 2n보다 적은 시간 합하면 총 3n보다 적은시간, 그러니까 총 O(3n)이고, O(n)이다. 그러니까 1회 평균 시간은 n을 나누면 O(1)이 된다.
분활상환 분석은 O(1)이 걸린다

📙 동적 배열 삽입 연산

최선의 경우 마지막 인덱스에 추가하는 거면 O(1)
근데 아무데나 집어넣으면 O(n)

✔ 아무데나 집어넣으면

  • 새 배열 생성하고 옮기는 데 O(n)
  • 맨처음 0번 인덱스(아무인덱스이건)면 그 뒤의 인덱스들 모두 한칸씩 뒤로 밀어내야하니까 O(n)
  • 인덱스한자리에 하나의 값 넣어줌 O(1)

그래서 O(2n+1), 그래서 O(n)이다.

📒 동적 배열 삭제 연산

만약 인덱스 2번에 있는걸 삭제하고 싶다면 그 뒤의 모든 인덱스 값들이 한칸씩 앞으로 댕긴다.
여기서 동적 배열 저장 크기도 하나 줄여준다.(동적 배열 특성)

바로 위 동적 배열 삽입 연산과 같은 원리로 최선의 경우 마지막 인덱스가 삭제되면 O(1), 그 외 아무곳이면 최악의 경우 O(n)이 걸린다.

만약 배열 크기를 너무 낭비하고 있다면 비율 기준을 두어 차지하는 비율 이하일때 아예 새 배열로 크기 지정해 옮겨버린다.

profile
TIL_기술블로그

0개의 댓글