자료구조

자료구조 : 데이터의 효율적인 접근 및 조작을 가능케 하는 저장 및 관리 방식

자료구조의 목적은 데이터를 효율적으로 사용하기 위함(속도, 메모리)

컴퓨터의 데이터 저장 방식

1. 스토리지
2. 메모리

스토리지

데이터가 영구적으로 저장되는 공간

• 사용자가 직접 지우지 않으면 사라지지 않음
• 데이터 저장과 불러오기에 시간이 오래 걸림
• 정확히 언제 사용할 지 모르는 데이터 저장

메모리

데이터가 임시적으로 저장되는 공간

예를 들어 문서를 작성할 때, 메모리에 임시 저장된다. 저장 버튼을 눌렀을 때, 스토리지에 저장된다.

• 프로그램 혹은 PC를 종료할 경우, 데이터가 사라짐
• 데이터 저장과 불러오기에 빠름
• 일반적으로 스토리지에 비해 메모리 공간이 작음
• 당장 사용할 데이터 저장

자료구조는 메모리에 데이터를 잘 저장하고, 불러오는 것과 관련이 있음

RAM

Random Access Memory : 임의 접근 메모리

메모리는 다음과 같은 특징을 갖는다.

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

위와 같은 모습이다.

여기서 RAM은 저장되어 있는 데이터에 접근하는데에 언제나 일정한 시간이 걸리는 메모리다. 이를 시간복잡도인 Big-O로 측정한 $O(1)$ 으로 표기한다. 순서에 따르는 순차접근이 아닌 임의접근을 하기 때문이다.

메모리의 기본 단위는 바이트(Byte)이다. 그리고 메모리 한 칸에 1바이트의 데이터가 담긴다.

레퍼런스

x = 10

파이썬에서 위와 같이 변수 x에 10라는 값을 할당하면, x는 10이라는 값이 저장된 메모리 주소를 갖는다. 레퍼런스는 데이터에 접근할 수 있게 해주는 값을 의미하며, 위의 예시에서는 레퍼런스가 메모리 주소였다.
하지만 레퍼런스는 보통 주소보다는 더 포괄적인 표현이다.

파이썬에서는 id함수를 통해서 데이터의 메모리 주소를 정수로 표현한 값을 알 수 있다.

x = 10
print(id(x))

> 4504577440

같은 값인 경우, 메모리 주소는 동일하다.

y = 20-10
print(id(y))

> 4504577440

배열(Array/List)

파이썬은 C언어를 기반으로 만들어진 언어이며, 파이썬의 리스트는 C언어의 배열을 이용해서 만들어졌다.
비슷하지만 배열과 리스트는 차이점이 있다.

가장 큰 차이점은 파이썬의 리스트가 데이터를 제한 없이 append 할 수 있고, 타입의 제한이 없다. 반면, C의 배열은 크기가 고정되어 있고, 데이터의 삭제가 불가능하다. 또한 모두 같은 타입의 데이터만 담을 수 있다.

# C 배열
int numArray[4];

위와 같이 C 배열은 데이터 타입과 크기를 지정한다. 이를 통해 메모리에서 연속적인 16바이트의 공간을 예약한다.(정수 1개당 4바이트) 그리고 각 인덱스에 값이 할당되는 순서대로 메모리에 저장된다.

반면, 파이썬은 연속적인 메모리를 예약하는 것이 아니며 각각의 값이 저장되지 않는다. 대신, 레퍼런스가 저장된다. 어떤 값인지를 가리키는 레퍼런스만 저장하기 때문에, 리스트 안에 반드시 동일한 타입만 담지 않아도 된다.

배열의 접근 및 탐색

배열은 인덱스만 알고 있다면 어떤 데이터를 접근하든 $O(1)$ 의 시간이 걸린다.

반면, 특정 조건에 맞는 값을 탐색하는 데에는 접근보다 비효율적이다. 처음부터 모든 배열 값을 확인해야하기 때문이다. 이와 같은 탐색법을 선형탐색 이라고 한다. 탐색의 시간복잡도는 $O(n)$ 이다.

• 접근의 시간복잡도 : $O(1)$
• 탐색의 시간복잡도 : $O(n)$

정적 배열과 동적 배열

정적 배열 : 크기가 고정된 배열 (C의 배열)
동적 배열 : 크기가 변하는 배열 (파이썬의 리스트)

정적 배열에서는 값을 추가할 수 없다. 추가를 원할 경우에는 해당 값을 포함한 길이의 배열을 다시 정의해야 한다. 왜냐하면, 정의된 배열 밖의 메모리 공간의 사용 가능 여부를 보장할 수 없기 때문이다.

반면, 동적 배열은 값을 추가할 수 있다. 만약 배열에 꽉 찼다면, 추가될 전체 길이보다 더 많은 메모리 공간을 확보하여 기존 값을 복사하고 뒤에 새로운 추가 값을 저장한다. 동적 배열은 내부적으로 정적 배열로 만들어진 자료구조이며, 상황에 맞게 크기를 조절하도록 구현되어 있다.

동적 배열의 추가 연산

값을 추가해주기만 하면 된다. 시간복잡도는 $O(1)$ 이다.

기존 배열의 값을 복사하여 새 배열에 붙여 넣는 과정을 반복한다. n개의 값을 이와 같이 반복한다고 하였을 때, $O(n)$ 의 시간복잡도를 가진다. 마지막 새로운 값을 추가하는 과정은 $O(1)$ 이 소요되며, 총 $O(n+1)$ 이다. 상수를 무시해도 되므로 결과적으로 $O(n)$이 소요된다고 볼 수 있다.

분할 상환 분석

시간복잡도는 최악의 경우를 이야기 한다. 따라서 동적 배열의 추가 연산에 대한 시간복잡도는 $O(n)$ 이라고 할 수 있다. 그러나, 실질적으로 최악의 경우가 발생하는 경우는 드물다. 따라서 어찌보면 비합리적으로 보일 수도 있다. 이러한 상황을 고려하여 시간복잡도를 계산하는 방식이 분할 상환 분석이다.

분할 상환 분석은 쉽게 얘기하면, 할부와 같다. 시간복잡도를 평균을 내어 계산하는 방식이다.

동적 배열의 추가 연산에서 새로운 배열에 데이터를 옮기는 시간은 아래의 표와 같다.

동적 배열은 배열의 크기가 가득찰 때마다, 기존 배열의 크기보다 큰 배열을 다시 할당하여 기존 값을 옮겨넣는다. 만약 배열의 크기가 2배씩 증가한다고 가정했을 때, 위와 같이 2,3,5,9 번째 추가 때 배열의 크기를 늘려야 한다. 이러한 과정을 일반화하였을 때, 분할 상환 분석을 통한 동적 배열의 추가 연산은 $O(1)$ 소요된다고 볼 수 있다.

동적 배열의 삽입 연산

배열 끝에 데이터를 넣는 것을 추가라고 하며, 연산은 아무 위치에나 데이터를 넣는 것을 말한다. 추가와 마찬가지로 배열의 공간이 남을 때와 그렇지 않을 때로 구분한다.

추가 연산과의 큰 차이점은 삽입하고자 하는 인덱스 공간을 만들기 위해 다른 데이터들을 이동시켜야 한다. 최악의 경우 인덱스 0에 데이터를 삽입하는 경우이다. 이 때, n개의 데이터를 인덱스 한 칸 뒤로 이동시키는 데에 $O(n)$이 소요된다. 그리고 인덱스 0에 새 값을 저장하는 것은 $O(1)$ 이며, 결과적으로 $O(n+1)$, 상수를 무시하면 $O(n)$이 소요된다.

기존 배열이 가득찼을 경우에는 삽입 연산과 마찬가지로 더 큰 크기의 새 배열을 만들어서 기존 값을 옮겨넣어야 한다.
먼저, 새로운 배열로 옮기는 데에 걸리는 시간이 $O(n)$이 소요된다. 그 후에 위와 같이 새로운 데이터를 위한 인덱스의 공간을 만드는 것도 $O(n)$이 소요되며, 값을 추가하는 데는 $O(1)$ 이 소요된다. 결과적으로 $O(2n+1)$ 이며, 이는 위의 경우와 마찬가지로 $O(n)$으로 볼 수 있다.

동적 배열 삭제 연산과 배열 크기 줄이기

삭제 연산은 해당 값을 지우고 빈 인덱스를 채워넣는 과정이다. 이 때, 맨 앞 데이터를 지우는 최악의 경우에는 n-1 개의 요소들을 한 칸씩 앞으로 옮겨줘야 하므로 $O(n)$이 소요된다. 반면, 가장 뒤의 데이터를 지울 경우에는 $O(1)$만으로도 가능하다.

동적 배열은 크기를 늘리는 것 뿐만 아니라 줄이기도 한다. 이를 통해 불필요한 메모리 낭비를 방지하기 위해 효율적으로 공간을 사용한다. 크기를 줄이는 시점은 배열의 사용 비율이 특정 값 이하로 떨어질 때이다. 만약 배열의 데이터를 삭제한 시점이 배열 크기가 줄이드는 시점과 동일할 경우에는 맨 끝 데이터를 삭제하더라도, 새로운 배열에 다른 값들을 옮기는 과정을 인하여 $O(n)$의 시간복잡도를 가질 수 있다.

그러나 분할 상환 분석을 적용하면, 동적 배열의 크기가 줄어드는 경우는 상대적으로 드문 경우이므로, $O(1)$이 걸린다고 볼 수 있다.

파이썬은 내부적으로 리스트에서 값을 지울 때, 실질적으로 데이터를 지우는 것이 아니라 해당 인덱스에 개발자가 접근할 수 없도록 인덱스 범위를 조절한다. 예를 들어 2, 3, 5, 7 에서 인덱스 1을 삭제하는 경우에는 2, 5, 7, 7 로 내부적으로 저장되지만 인덱스의 범위는 0~2로 제한할 수 없도록 한다. 개발자는 더 이상 해당 값에 접근할 수 없으므로 실질적으로는 삭제된 것으로 볼 수 있다.

배열과 동적 배열의 비교

배열은 크기가 고정되어 있으므로 낭비하는 공간이 없지만 동적 배열은 상황에 따라서 낭비하는 공간이 있을 수 있다.
동적 배열이 낭비하는 공간이 가장 큰 시점은 새로운 배열을 만들었을 때이다. 2배의 공간을 갖는다고 했을 때, 아래와 같은 낭비 공간을 갖는다.

즉, 최악의 경우 $O(n)$의 공간이 낭비된다고 볼 수 있다.

---

Q & A

1. 저장방식 중에서 스토리지와 메모리는 각각 무엇인가?
2. RAM이 항상 일정한 속도로 데이터에 접근할 수 있는 이유는?
3. C의 배열과 파이썬의 리스트의 차이점은 무엇인가?
4. 배열의 접근과 탐색연산에 대한 시간복잡도는 어떻게 되고, 그 이유는?
5. 정적배열과 동적배열은 각각 무엇이며, 파이썬의 리스트는 어떤 자료 구조로 구현되어 있는가?
6. 동적 배열의 추가 연산에 대한 시간복잡도는 어떻게 되는가?
7. 동적 배열의 삽입 연산에 대한 시간복잡도는 어떻게 되는가?
8. 동적 배열의 삭제 연산에 대한 시간복잡도는 어떻게 되는가?
9. 분할 상환 분석이란 무엇인가?
10. 배열 int_array의 주소가 10000이고, 정수 자료형의 크기가 4 바이트이면, int_array[300]의 주소를 계산하라.
11. 다음 중 동적 배열을 사용하는 게 가장 부적절한 경우는 무엇인가?
    1) 순위 정보를 담아 놓고, 저장해 놓은 데이터에 접근해야 될 때.
    2) 게임 프로그램에서 캐릭터가 죽을 때마다 리스트에 추가해야 될 때.
    3) 온라인 상담소에서 접수가 들어오는 순서대로 저장하고, 가장 앞에 있는 문의부터 처리하고 지워야 할 때.