[코드잇] 기본 자료 구조들 (1) (2021.2.26)

본 내용은 해당 강의 토대로 작성

자료 구조란?

01. 자료 구조란?

• 자료 구조: 데이터를 저장, 관리하기 위해 사용하는 구조
• 데이터의 효율적인 접근 및 조작을 가능하게 하주는 저장 및 관리 방식

02. 상황에 맞는 자료 구조

• 각 자료구조마다 장점, 단점이 있다.
• 모든 경우에 제일 좋은 자료구조는 없다.
• 각 상황에 알맞은 자료구조를 선택해서 사용한다.

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

01. 스토리지 vs. 메모리

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

스토리지 (Storage)

• 데이터가 영구적으로 저장되는 곳
• 사진, 음악, 영상, 워드문서 등
• 데이터를 저장, 불러오는 것이 느리다.
• 정확히 언제 사용할지 모르는 파일 저장

메모리 (Memory)

• 데이터가 임시로 저장되는 곳
• 컴퓨터가 종료되면 사라진다.
  • ex. 저장 전의 문서 내용
• 스토리지 용량보다 상대적으로 작다
• 데이터를 저장, 불러오는 것이 빠르다.

두 가지 방식이 필요한 이유

• 많은 용량을 가진 스토리지에 담긴 컨텐츠를 사용할 때 빠른 속도의 메모리에 불러와서 사용하기 위해

02. RAM: Random Access Memory

• 메모리는 긴 띠와 같다.
  • 일정한 칸으로 나눠져 있다.
  • 각 칸에 데이터를 저장할 수 있다.
  • 각 칸은 자신만의 주소가 있다.
• RAM: 임의 접근 메모리
  • 임의 접근: 저장 위치를 알면 접근할 때 항상 일정한 시간이 걸림(cf. 순차 접근: 저장된 위치까지 가는데 한 단계씩 거쳐야 됨)
  • 임의 접근이 순차 접근보다 효율적
  • 메모리에 저장한 데이터 접근 시간 복잡도: O(1)
• 자료구조는 메모리에 데이터를 저장하고 저장된 데이터를 찾는다.

03. 메모리의 기본 단위: 바이트

• 컴퓨터 저장 공간 용량을 나타내는 단위
• 메모리 한 칸에 담기는 데이터 용량은 1 바이트(byte)이다.

04. 레퍼런스 (reference)

x = 95

python "95가 저장된 메모리 주소"

• 데이터에 접근하게 해주는 값
• "주소"보다 조금 더 포괄적인 표현
• 자료구조에서, '주소 == 레퍼런스'라고 생각해도 된다.
• 실제로 변수를 사용할 때는 저장된 값을 알아서 받아온다.

05. 데이터의 주소

파이썬 id 함수

• 저장한 데이터의 메모리 주소를 정수로 표현한 값을 알아낼 수 있다.

id(data)

Aliasing

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

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

• list1, list2는 같은 메모리를 가르킨다.

배열

01. 배열이란

• 기본적인 자료 구조

C배열 vs. python 리스트

• python 리스트는 C배열을 기반으로 만들어졌다.

C 배열	Python 리스트
선언시 크기 고정	append 메소드를 사용해서 요소 추가
수정 가능, 삭제 불가	수정 및 삭제 가능
같은 타입의 데이터만 가능	다른 타입의 데이터도 가능
데이터가 메모리에 연속적으로 저장	데이터를 가르키는 레퍼런스 저장
	데이터의 크기 상관없이 다룰 수 있음

02. 배열 인덱스를 이용한 데이터 저장/접근법

저장법

C 배열 선언

int numArray[4];

정수형 값 4개를 저장하는 배열

• C에서 정수 하나는 4바이트 -> 총 16바이트
• 메모리에서 사용하고 있지 않는 연속적인 16칸 예약
• 배열의 길이는 4므로 인덱스는 0~3까지 있다.
• 배열의 요소들이 메모리에 순서대로, 연속적으로 저장(메모리 네 칸 씩)
• 저장된 데이터를 불러오기: 부를 인덱스를 사용
• 배열 저장 시간 복잡도: O(1)

접근법

시작주소 + 데이터크기 x i(인덱스) = 인덱스 i 주소

• 해당 배열이 시작하는 지점만 알면, 인덱스의 주소를 계산할 수 있다.
• 임의 접근: 주소를 알면, 효율적으로 접근이 가능하다.
• 즉, 배열의 주소는 간단한 계산으로 구할 수 있으므로 O(1) 으로 접근이 가능하다.
• 배열 인덱스 접근: O(1)

03. 배열 탐색

• 특정 조건을 만족하는 값을 찾는 것
• 선형 탐색: 순서대로 데이터를 하나씩 찾는 탐색법
• **시간 복잡도:O(n) **
  • n: 배열에 저장한 데이터의 개수

04. 정적 배열 (Static Array)

• 크기 고정 (요소 수 제한)
  • ex. C의 배열
• 일반적인 배열
• 이미 만들어진 배열이 꽉 차면 더 이상 값을 추가할 수 없다.
  • 크기가 확장된 새로운 배열을 선언 후 사용해야 한다.
  • 기존 꽉 찬 배열의 다음 자리가 사용가능한지 알수 없기 때문이다.
• 필요 이상으로 여유롭게 배열 정의한 경우
  • 메모리 공간의 낭비
  • 공간 부족으로 문제 발생 가능

05. 동적 배열 (Dynamic Array)

• 상황에 따라 크기 변함 (요소 계속 추가 가능)
  • ex. python의 리스트
• 정적 배열로 만들어진 자료 구조
• 정적 배열의 크기를 상황에 맞게 조절
• 꽉 찬 배열에 값을 추가하는 경우
  • 더 많은 값을 저장하기 위해 기존 배열의 더 큰 배열을 만든다.
  • 기존 데이터를 복사 후 새로운 데이터를 다음 공간에 저장

파이썬 리스트(동적 배열)

• 파이썬 리스트 또한 C 배열을 이용해서 동적 배열을 구현한 것이다.
• 동적 배열로 인해, 배열의 나머지 공간이 있어도 값을 저장한 공간에 대해서만 접근할 수 있다.
  • 채워지지 않은 공간을 접근 시, 오류가 발생

06. 동적 배열 추가 연산 시간 복잡도

• 추가 연산 (append operation) : 배열의 가장 끝에 새 값을 넣는 것
• 시간복잡도: O(n)
  • 최고의 경우: O(1)
  • 최악의 경우: O(n)

경우 1: 정적 배열에 남는 공간이 있을 때

• 비어있는 공간에서 가장 앞쪽에 있는 칸에 데이터 저장
• O(1) 시간복잡도를 가진다.

경우 2: 정적 배열이 꽉 찼을 때

• 현재 사용중인 공간보다 더 큰 공간을 확보
• 기존 배열의 값 복사
  • 기존 배열 접근 후 복사 -> 새 배열 접근 후 붙여넣기
  • O(n) 시간 복잡도
  • n : 기존 데이터 개수
• 그 후, 새로운 값 넣기

07. 분할 상환 분석 개념

분할 상환 분석(Amortized Analysis)

• 최악의 경우로 시간 복잡도를 애기하는 것이 비합리적인 경우에 사용
• 같은 동작을 n번 했을 때 드는 시간이 X일 때
  • 동작을 한 번 하는 데 걸린 시간: X/n
• 시간 복잡도를 평균으로 구한다.

동적 배열의 추가(append) 연산은 최악의 경우 O(n)이 걸리지만, 분할 상환 분석을 하면 O(1)이 걸린다.

08. 동적 배열 삽입 연산

• 삽입 연산 (insert operation)

경우 1: 정적 배열에 남는 공간 있을 때

• 요소를 넣으려는 인덱스 기준으로 뒤의 요소들은 뒤에 밀려난다.
  • 가장 뒤에 있는 요소부터 뒤로 밀려난다.
• 해당 인덱스는 빈 상태가 된다.
• 빈 인덱스에 요소를 넣는다.

시간 복잡도

• 인덱스 0에 넣을 때(최악의 경우) : O(n)

경우 2: 정적 배열이 찼을 때

• 새로운 요소를 수용하기 위해 큰 새로운 배열을 만든다.
• 기존 데이터를 복사해서 저장
• 넣을 인덱스를 기준으로 뒤에 요소들을 뒤에 밀어낸다.
• 빈 인덱스에 요소를 넣는다

시간 복잡도

• 인덱스 0에 넣을 때(최악의 경우): O(n)
  • 새로운 배열에 요소를 복사 : O(n)
  • 자리 만들기: O(n)
  • 인덱스에 요소 저장: O(1)

09. 동적 배열 삭제 연산

삭제 연산 동작

• 삭제할 인덱스 뒤에 있는 데이터를 모두 한 칸식 앞으로 밀어서 저장한다.
• 동적 배열에서 접근할 수 있는 인덱스 범위도 1을 줄여준다.

삭제 연산 시간 복잡도

경우 1: 맨 앞데이터를 지울 때 (최악의 경우)

• 인덱스 1부터 끝까지 모든 요소를 한 칸씩 앞으로 밀어서 저장
• O(n)

경우 2: 맨 뒤 데이터를 지울 때

• 아무 요소도 안 밀고 저장한다.
• 동적 배열의 사용 공간만 줄인다.
• O(1)

10. 동적 배열 크기 줄이기

• 동적 배열은 요소의 개수가 어느정도 줄어들면 내부 배열의 크기도 적절히 줄여서 공간을 좀 더 효율적으로 사용
• 내부 배열의 사용 비율이 특정 값 이하로 떨어질 때
  • 새로운 내부 배열을 정의
  • 기존 요소를 새로운 내부 배열에 옮겨서 저장

시간 복잡도

• 최악의 경우: 더 작은 배열로 모든 요소들을 옮겨 저장할 때
  • O(n)

분할 상환 분석

• 동적 배열에서 마지막 데이터를 삭제할 때는 대부분의 경우 O(1)이므로

최악의 경우 O(n)이 걸리지만, 분할 상환 분석을 적용하면 O(1)이라고 할 수 있다.

11. 배열과 동적 배열 정리/비교

연산 & 시간 복잡도

	배열	동적 배열
접근 (access)	O(1)	O(1)
탐색 (search)	O(n)	O(n)
삽입 (insert)	N/A	O(n), 맨 뒤 O(1)
삭제 (delete)	N/A	O(n), 맨 뒤 O(1)

낭비하는 공간

• 실제 데이터가 저장되는 공간 의외의 공간
• 배열: 크기가 고정되어 있기 때문에 낭비하는 공간이 없다.
• 동적 배열: 공간을 낭비할 수도 안 할 수도 있다.
• 최악의 경우 : 수용 공간을 늘리기 위해 새로운 배열을 만들었을 때
  • 낭비되는 공간이 제일 많음
  • 저장된 요소 수: n
  • 낭비되는 공간: n - 2 -> O(n)

12. 정적 배열에 삽입과 삭제를 못하는 이유

삽입을 못하는 이유

• 배열은 크기가 이미 정해져 있다.
• 크기가 고정되어 잇으므로 처음 정한 수보다 더 많은 데이터를 삽입할 수 없다.

삭제를 못하는 이유

• 비었다는 것을 표시하기 위해서 파이썬에서는 None, 다른 언어들에서는 Null과 같은 값을 사용한다.
• C와 같은 언어에서는 선언시 배열의 자료형도 정의하므로 Null과 같은 다른 데이터형이 들어올 수 없다.
• 그러므로 배열에서는 어떤 인덱스의 요소를 지우기 위해서 임의의 값으로 수정해야한다.

동적 배열에서의 삭제와 차이

• 동적배열에서는 어떤 인덱스가 삭제되었을 때, 그 결과에 맞춰서 접근 할 수 있는 인덱스 범위도 줄인다.

Comment

그동안 아무 생각없이 사용했던 배열의 학문적 접근은 정말정말 신세계다…

분할 상환은 읽으면 이해가 되는 듯해도 뒤돌아보면 머리에서 사라져 있다.

그러므로 내 머리는 메모리인 것 같다.