안녕하세요 집 DS입니다. 지도를 하기로 마음먹었지만 그래도 컴퓨터에 대한 지식은 여전히 필요합니다. 그중 데이터 구조이해로부터 나오는 알고리즘 구현은 특히나 중요한 부분입니다. 모든 부분을 설명할 순 없지만 제가 얘기하고 싶고 이해한 부분을 공유하고자 합니다.
자료구조(Data Structure)란
흔히들 자료구조를 푼다. 자료구조를 구현한다라는 말을 많이 쓰곤합니다. 프로그래밍을 처음 접했을 때나 지금이나 다소 이해가 안 될 때가 있습니다. 그럼 수업 자료를 기준으로 자료구조란 무엇인지 얘기해 보도록 하겠습니다.
A data structure is a way to store data, with algorithms that support operations on the data
위 내용을 해석해보면 자료구조란 데이터를 저장하는 방식이며, 해당 데이터를 위해 연산을 지원하는 알고리즘을 포함하는 것이라고 하고 있습니다. 가장 간결한 설명이라고 볼 수 있습니다. 여기서 지원하는 기능 및 우리가 원하는 명세(Specification)를 Interface라고 표현합니다. Java를 해보면 Interface라는 말이 나오는 것을 볼 수 있습니다. 즉, 이것은 우리가 해당 자료구조로부터 기대하는 기능(specification)입니다. 기대하는 기능을 직접 구현한 것이 자료구조입니다.
자료구조 = 데이터 + 기능(알고리즘)
정리해보면 자료구조란 위와 같이 이해할 수 있습니다. 이러한 자료구조는 다양한 종류가 있습니다. 해당 챕터에서는 sequence, set interface(구현하고 싶은 것)을 다루며 저는 이 중 sequence interface를 array로 구현한 것(array sequence data structure)을 이야기해보겠습니다.
Sequence Interface 란
항상 하나하나 단어를 정확히 정의하는 일이 중요합니다. 그렇기 때문에 글을 쓸 때 많은 이해가 필요하지만 그래서 성장하기도 하고 재밌기도 합니다. 아무튼 딴소리 그만. Sequence는 프로그래밍 언어를 접하면 가장 처음 접하는 형태일 것입니다. python에서 list나 c#의 array 등이 대표적인 예입니다. 앞에서 Interface는 원하는 기능명세라고 했습니다. 수업의 자료도 보면 원하는 기능명세를 면저 한 후, 각 data structure로 어떻게 구현하고 차이가 있는지 설명하고 있습니다. 수업 자료의 그림을 한 번만 이해하면 나머지 뒤는 쉽습니다. 저는 이제야 이걸 어느 정도 이해했네요
위 그림에서 보면, container, static, dynamic 크게 세 가지를 볼 수 있습니다. container에 해당하는 친구들은 데이터 구조를 담는 그릇을 연상하면 됩니다. 그릇에 무엇을 담을 것인지(build(X)) 담긴 물건의 개수는 몇 개인지(len())를 표현하고 있습니다. 잘 보시면 build에 X와 나머지에 쓰인 x의 대소문자 구분이 있는 것을 볼 수 있습니다. 이는 대문자는 보통 array(또는 list)를 뜻하고 소문자는 하나의 요소를 뜻하기 때문입니다.
Static은 Container의 크기가 변하지 않는 interface들을 뜻합니다. 가령 inter_seq()는 그릇 안에 어떤 요소들이 있는지 훑는 기능을 합니다. 단순히 훑고 지나가는 것이기 때문에 Container의 크기는 변하지 않습니다. 마찬가지로 get_at(i)는 i 번째 요소를 불러오기 때문에 크기를 변화시키지 않습니다. set_at(i, x)도 마찬가지입니다. i번째 요소를 x로 바꾸는 작업이기 때문에 container의 크기는 변하지 않습니다. 그래서 static 한국말로 "정적인" interface(하고 싶은 것)에 해당합니다.
Dynamic은 그렇다면 Container의 크기를 변화시키는 것 이겠죠? 하나하나 훑어보면 Container의 크기를 바꾸지 않고서는 할 수 없는 일들입니다. 사실 여러분은 동의하지 않을 수도 있습니다. "몇몇 기능들은 Container의 크기를 안 바꿔도 되는 것이 아닌가?"라고 말이죠. 이를 설명하기 위해서는 Word RAM(Random Access Memory)에 대해 어느 정도 이해해야합니다. 왜 어느정도냐. 일단 저도 어느정도 이해하고 있습니다.
Word RAM모델이란?
RAM. 컴공을 전공하지 않은 저로서는 삼성전자 뉴스나 컴퓨터 맞출 때나 듣게 되는 용어였습니다. 디테일은 살짝 흐리게 하고 Word RAM 모델을 간략히 얘기하면 이렇습니다. WordRAM에서는 두 가지만 기억하면 됩니다. 1. 데이터는 메모리 공간상에 저장되며 바로 인접한 곳에 붙어 있을 수도 있다. 2. Word RAM 모델에서 가정하는 기초연산(단위 시간 만에 구현되는 연산)이 몇 가지 있다.
데이터는 메모리 공간상에 저장됩니다. Random Access Memory라는 말에서 알 수 있듯, 데이터를 저장할 때 RAM의 어디에 저장될지는 알 수 없습니다. 더 디테일한 부분은 일단 차치하고 이렇게 함으로써 빈 메모리 장소를 찾을 때 빠르게 찾을 수 있습니다. 그럼 Random으로 하게 되면 A = [1,2,3,4], B = [5,6,7,8]이라는 데이터는 다음과 같은 두 가지 경우로 저장될 수 있습니다.
아래 인접하지 않은 경우에는 행복한 경우입니다. 만약 A에 11이라는 숫자를 넣고 싶다면 제자리에서 Container의 크기를 늘리고 11을 넣으면 됩니다. 그러면 모든 게 해피합니다. 하지만 인접한 경우 이야기는 다소 어려워집니다. 아래 그림을 통해 보면 좀 더 쉽습니다.
어려워 보여도 차근차근 보면 이해할 수 있습니다. 결국 A의 뒤에는 자리가 없습니다. 따라서 적합한 위치를 찾는 과정이 먼저 필요합니다. 적합한 위치를 찾으면 모든 element들을 해당 위치로 복사한 후, 넣으려 했던 11을 넣으면 됩니다. 프로그래밍을 할 때 가장 신경 쓰는 것은 최악의 경우입니다. 좀 더 유식한 말로는 Big O notation이라고 합니다. 쓰는 것은 O(n) 이런 식으로 씁니다. 위 경우, container의 크기가 n이라 할 때 최악의 경우(모든 값을 복사하는 경우) O(n)이 걸리게 됩니다.
그럼 O(n)을 제대로 정의하기 위해서는 어떤 연산들이 단위시간 안에 이루어지며 어떤 연산들이 단위시간의 조합으로 이루어지는지 알아야 합니다. 어떤 연산이 어떤 시간이 걸리는지 가정하는 것을 Model of Computation이라 하며 이 수업에선 WordRAM 모델을 따르고 있습니다. Word RAM 모델에서는 사측연산(+-*/ 등)과 Memory의 특정 주소를 접근하는 연산은 단위시간에 할 수 있는 것으로 정의하고 있습니다. 수업에서는 Constant Time이라고 표현하고, O(1)이라고 씁니다. 그럼 지금 여기까지 하고 Static Array를 이용한 Sequence를 보겠습니다.(이하 Static Array Sequence)
Static Array Sequence
앞서 설명한 WordRAM을 통해 Array 중 Container, Static 부분은 쉽게 이해할 수 있습니다. 다시 설명하면 build는 Array의 각 item을 훑어야 하기 때문에 O(n)이 걸립니다. static의 get_at(i), set_at(i, x)는 Memory의 주소를 접근하는 경우 O(1)이기 때문에 O(1)입니다. insert도 다뤘습니다. insert를 다뤘으니 insert_어쩌고 하는 친구들은 이해할 수 있습니다.
그렇다면 delete는? 저는 맨 처음에 이걸 이해하지 못했습니다. 하지만 답은 간단합니다. Static Array는 빈 공간을 허용하지 않는다. 그 말은 매번 delete를 할 때마다 Container의 크기가 줄어들며, 줄어들기 위해 다시 RAM의 다른 위치에다가 만든다. 제가 제대로 이해했다면 이게 이유입니다. 뭐가 이렇게 불합리적이냐 할 수 도 있지만 그것 이상은 저도 이해하기 어렵습니다. 그럼 다시 그림으로 표현하면 다음과 같습니다.
위 그림을 보면 간단합니다. 비록 마지막 거를 지운다 하더라도 새로운 메모리 주소를 찾고, 복사해야 하기 때문에 O(n) 시간이 걸립니다. 좀 더 친절해지면 O(n-1)이지만 big O에서는 가장 크게 늘어나는 부분만 신경 씁니다. 따라서 뒤의 -1은 빼고 생각하면 됩니다.
이 정도라면 Sequence Interface를 Array(Static Array)로 Data Structure를 구현하는 방법 및 장단점에 대해 이해가 됐으리라고 생각합니다. 아래 참고자료로 가시면 해당 이론을 코드로 구현한 내용도 있으니 필요시 참고하시면 되겠습니다.
끝.
열심히 하는 것보다 중요한 것은 잘하는 것이다
그러나 잘하기 위해서는 열심히 해야 한다
집 DS
참고자료
'진행중 > Computer Science' 카테고리의 다른 글
| Linear Sorting Algorithm (2) | 2024.04.10 |
|---|---|
| 6.006 Lecture1 - 알고리즘이란 (0) | 2024.01.16 |
| Coursera Programming Language Part B : Intro to racket (1) | 2023.11.27 |