[Data] 자료 구조란?(1) : Data Structure 개념 및 종류, 배열, 동적 배열, 접근 연산, 탐색 연산, 연산 시간 복잡도

 

 

💡 자료 구조 : 데이터의 효율적인 접근과 조작을 가능하게 해주는 저장(관리) 방식

쉽게 말해, 데이터를 효율적으로 저장, 활용하는 관리 방식

➡️ 자료들을 어떻게 구조화할지 고민해서 데이터를 효율적으로 사용하는 것이 목적

 

먼저 컴퓨터가 데이터를 어떻게 저장하는지 알아보자.

데이터가 저장되는 곳은 크게 두 가지다.

• 스토리지 Storage : 데이터가 영구적으로 저장되는 곳
  
  • 컴퓨터에 저장해 둔 사진, 노래, 영화 , 워드 문서 등
  • 사용자가 직접 지우거나 컴퓨터에 심각한 외부 충격이 있지 않은 한 지워지지 않는다.
  • 데이터를 저장하는 데, 받아오는 데 오래 걸린다.
  • 창고와 비슷, 많은 물건을 보관할 수 있지만 왔다 갔다 하는 데 시간이 오래 걸림
    ➡️ 정확히 언제 사용할지 모르는(나중에 사용할) 파일을 저장
• 메모리 Memory : 데이터가 임시로 저장되는 곳, 램
  • 메모리 한 칸의 데이터 용량은 1 byte
  • 문서 작업 중엔, 데이터가 메모리에 저장되고 중간에 컴퓨터가 꺼지면 날아간다.
  • 작업 중 저장을 했다면, 스토리지에 영구적으로 저장된다.
  • 데이터를 저장하는 데, 받아오는 데 빠르다.
  • 책상 서랍과 비슷, 적은 물건을 보관할 수 있지만 가까이 있어 빨리 갖고 올 수 있음, 
    ➡️ 지금 당장 사용할 데이터들을 저장

왜 스토리와 메모리, 둘 다가 필요한가?

컴퓨터로 영화를 본다고 가정해 보자.

스토리지에 저장된 영화를 재생하고, 한 장면씩 불러오게 된다.

만약 스토리지에서 장면을 실시간으로 꺼내오면 가져오는 속도가 느리니 영화가 계속 끊길 것이다.

 

이런 스토리지의 단점을 해결해 주는 것이 메모리이다.

영화를 재생하면 스토리지에 있던 영화를 메모리에 복사하고, 메모리에 있는 영화를 재생한다.

이제 끊김 없이 영화를 볼 수 있게 되고, 영화를 끄면 메모리에 있던 영화는 삭제된다.

지금 당장 사용하는 데이터가 아니면 바로바로 지워주는 것!

 

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

 

메모리를 띠처럼 그려 보자.

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

 

메모리를 RAM 이라고도 하는데, RAM 은 무엇일까?

RAM Random Access Memory : 임의 접근 메모리 

• 임의 접근 : 저장 위치를 알면 접근 시 항상 일정한 시간이 걸림,
  1000 에 있는 1007 에 있든 주소와 상관 없이 가져오는 데 다 같은 시간이 걸린다.
• 메모리에 저장한 데이터 접근 시간 복잡도 : O(1)❗️

❗️ 임의 접근이 순차 접근보다 효율적인 이유

비디오 테이프를 생각해 보자. 테이프를 틀고 1시간 20분 장면을 보려고 한다면 빨리 감기 버튼을 눌러 테이프를 돌려야 한다.

이를 순차 접근이라고 한다.

• 순차 접근 : 저장된 위치까지 가는데 한 단계씩 거쳐 감

 

레퍼런스 Reference

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

# Python
x = 5

 

굳이 따지자면 이 코드를 'x 는 5다.' 라고 하는 것은 틀린 표현이다.

x 는 5 라는 값 자체가 아닌 5 가 저장된 메모리 주소를 갖고 있기 때문이다.

➡️ 'x 는 5를 가리킨다.' 라고도 할 수 있다.

 

x = 5
print(x + 3) # => print(5 + 3)

 

그럼 이 코드는 레퍼런스와 3 을 더하는 것일까? 아니다.

x 에 레퍼런스가 담겨 있는 것은 맞지만 실제로 변수를 사용할 땐 파이썬이 저장된 값을 알아서 받아온다.

x 가 3을 갖고 있다 라는 표현은 틀렸지만, 알아서 값을 가져오므로 편하게 생각하자.

 

💡 배열

C 배열 : 메모리에 배열을 쓸 공간을 미리 정해두고(크기 고정, 같은 타입만 가능), 정수를 메모리에 그대로 담는다.

int numArray[4]; // 연속적인 16칸 차지, 정수 하나에 4바이트 정도

numArray[0] = 2;
numArray[1] = 3;
// ...

 

파이썬 리스트 : 정수가 아니라, 정수를 가리키는 레퍼런스를 메모리에 담는다.

num_list = [2, 3, 5, 7]
item_list = [2, '큰 데이터', 5, True]
# 때문에 값의 유형이 달라도 되고, 큰 값이 들어가도 된다. 어차피 주소를 담기 때문에

 

배열 접근 연산 : O(1), 인덱스만 알면 바로 접근 가능

배열 탐색 연산 : O(n), 선형 탐색일 때 전부 확인해야 하므로

 

정적 배열 : 크기 고정, 요소 수 제한, 더 담으려면 새로운 배열을 만들어야 함(이어져있는 다음 공간이 비었는지 모르므로 바로 붙일 수 없음, 그렇다고 여유 있게 만들면 메모리 낭비), 보통 그냥 배열이라고 함.

동적 배열 : 크기 변함, 요소 계속 추가 가능, 다 찬 배열에 더 담으려면 메모리는 더 큰 공간을 찾아서 담음(결국 정적 배열로 만들어짐, 옮기는 것 뿐)

추가 연산 Append Operation : 배열의 가장 끝에 값을 추가하는 것

• 정적 배열(=> 동적 배열)에 남는 공간이 있을 때, : 최고의 경우 O(1)
• 정적 배열이 꽉 찼을 때 : 최악의 경우 O(n), 기존 값을 옮긴 배열에 하나씩 복사해야하므로

분할 상환 분석 Amortized Analysis : 할부, 좀 더 합리적인 시간 복잡도를 구하는 법, O(1)
같은 동작을 N 번 했을 때 드는 시간이 X 일 때 = 동작을 한 번 하는데 걸린 시간 X / N

 

삽입 연산 Insert Operation : 배열의 아무 위치에 값을 추가하는 것

• 정적 배열에 남는 공간이 있을 때 : 최악의 경우([0] 에 삽입할 때, 모든 요소를 한칸 씩 뒤로 밀어야 함) O(n)
• 정적 배열이 꽉 찼을 때 : 최악의 경우 O(n)

삭제할 땐 ? 

• 최악의 경우, 맨 앞 데이터를 지울 때 : O(n)
• 맨 뒤 데이터를 지울 때 : O(1)

연산 시간 복잡도 정리

	배열	동적 배열
접근 access	O(1)	O(1)
탐색 search	O(n)	O(n)
삽입 insert	N / A 정적 배열이기에 자연스럽게 할 수 없음	O(n), 맨 뒤 O(1)
삭제 delete	N / A 정적 배열이기에 자연스럽게 할 수 없음	O(n), 맨 뒤 O(1)

// 자연스럽게 할 수 없는 이유
int numArray[4];
    
numArray[0] = 2;
numArray[1] = 3;
numArray[2] = 5;
numArray[3] = 7;
// numArray = [2, 3, 5, 7]

 

여기서 3을 지운다 할 때 마땅히 지울 방법이 없다.
다른 언어들에선 None, Null 이런 값들이 있지만 numArray 는 정수형 데이터 4개를 저장하도록 정해져 있다.
때문에 3을 지우기 위해선 데이터가 [2, 5, 7] 이 아니라 [2, 5, 7, 7] 이런식으로 만들게 된다.

 

낭비하는 공간

• 배열 : 크기가 고정되어 있기에 낭비하는 공간이 없다.
• 동적 배열 : O(n), 공간을 낭비할 수도, 안 할 수도 있다. 최악의 경우는 새 배열을 만들었을 때