[CS50] 6.자료구조, Data Structures
메모리의 구조
지난 단원이었던 ‘메모리’에서 컴퓨터는 저장하려는 데이터의 타입에 따라 물리적 기억공간인 메모리에 데이터를 저장할 공간을 할당하고, 각 공간에는 주소가 지정되어 있어서 데이터를 불러올 때 포인터라는 개념을 사용하여 주소를 찾아가서 데이터 값을 가져온다고 배웠다.
그렇다면 만약 이미 저장되어 있는 배열에 값을 추가하고 싶을 경우, 메모리에서 이 배열을 어떻게 저장해야 할까? 아래 이미지에서 배열 [1, 2, 3] 주변에는 이미 다른 데이터들이 저장되어 있다.
이런 경우 옆에 있는 “EMMA\0” 문자열들을 모두 한칸씩 오른쪽으로 이동시키고 4를 추가하거나, 새로운 공간으로 배열의 값들을 모두 옮기는 방법을 선택해야 한다.
이 경우 배열에 값을 하나 추가시키기 위해서 모든 값들을 일일히 다른 공간으로 이동시키는 O(n) 만큼의 작업을 해야만하는 것이다.
자료구조의 정의
위와 같이 컴퓨터의 메모리는 물리적인 특성과 한계를 가지고 있는데, 이 때 자료구조라는 개념을 사용하게 된다.
자료구조는 C, C++, Java, Python 등에서 볼 수 있는 일종의 프로그래밍 구조로 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 하고, 메모리를 더욱 효율적으로 관리하기 위해 정의하는 구조체다.
자료구조 또는 데이터 구조는 일종의 메모리 레이아웃 또는 지도라고도 볼 수 있다.
연결 리스트
위에서 배열은 각 인덱스의 값이 메모리상에서 연이어 저장되어 있고, 그런 특성 때문에 4라는 값을 추가하기 위해서 배열을 통째로 이동시킬 수 밖에 없었다. 그러면 배열을 통째로 옮기지 않고도 4라는 값만 새로 비어있는 공간에 저장시키고 값을 연속으로 불러오게 할 방법은 없는 것일까?
이 때 사용할 수 있는 자료구조가 바로 연결 리스트다.
위 사진처럼 각 값을 메모리상의 여러군데에 나눠 놓더라도 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있게된다. 위의 상태라면 정의상 배열도 아니고 값들이 서로 연결되어 있지도 않지만, 아래처럼 각 값과 다음 값의 주소(포인터)를 함께 저장시키면 연결 리스트를 만들 수 있다.
각 값은 다음에 올 값의 메모리 주소를 함께 저장하고 있는데, 3은 다음 값이 없기 때문에 NULL (\0, 0으로 채워진 값)을 다음 값의 주소로 저장하고 리스트의 끝을 알린다.
C 로는 다음 코드로 간단하게 정의할 수 있다.
typedef struct node
{
int number;
struct node *next;
}
node;
값과 포인터가 하나로 합쳐진 구조체를 node 라고 하는데, number는 각 node가 가지는 값이고 *next는 다음 node를 가리키는 포인터다.
연결리스트의 장단점
배열에 비해서 연결리스트는 이렇게 새로운 값을 추가할 때마다 다시 메모리를 할당하지 않아도 된다는 장점이 있다. 하지만 배열에 비해 단점도 존재하는데, 순서대로 값이 저장되어있는 정적 구조의 배열과는 달리 유동적 구조인 연결 리스트는 중간에 있는 값을 찾기 위한 임의 접근이 불가능하다.
위 이미지 처럼 연결 리스트 안의 어떤 값을 찾거나 제일 끝에 있는 값에 접근하려면 앞에서부터 포인터를 따라 모든 메모리를 확인해봐야만 한다. 그래서 정렬되어 있는 배열에 이진 검색을 이용해서 값을 찾을 때 O(log n)의 실행 시간이 걸리는데 반해, 연결 리스트는 각 node를 모두 확인하기 때문에 O(n)의 실행시간이 걸린다.
이처럼 모든 데이터 구조는 각각 장단점이 존재하고, 프로그래밍을 할 때 목적에 맞는 가장 효율적인 데이터 구조를 고민해서 사용하는 것이 중요하다.
트리
트리는 연결리스트를 기반으로 해서 연결리스트의 단점을 보완한 새로운 데이터 구조다.
연결 리스트의 각 노드가 1차원적으로 구성되어 있었다면, 트리에서는 노드들이 아래처럼 2차원적으로 연결되어 있다. 가장 높은 층에 트리가 시작되는 노드를 루트라고 하고, 한 노드의 다음에 연결되어 있는 노드들을 자식 노드라고 한다.
위는 연결리스트를 기반으로 이진 검색을 하기 위해 구현한 이진 검색 트리다. 이렇게 이진 검색 트리를 활용하면 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)이 된다.
해시 테이블
해시 테이블은 연결 리스트들의 배열로 이루어진 자료구조다.
각 값들은 ‘해시 함수‘라는 맞춤형 알고리즘을 통해 적절한 연결리스트로 이어지게 된다.
예를들어 아래 이미지의 경우 이름의 가장 첫 글자 순으로 연결 리스트를 정의하는 해시 함수를 사용해서 만들어진 해시 테이블을 보여준다.
만약 이상적인 해시 함수를 사용할 경우 배열의 각 인덱스에 연결리스트 대신 하나의 값만 담기게 되고 (위의 Albus 처럼) 그 때 각 값의 검색 시간은 O(1)이 된다.
하지만 그렇지 못한 최악의 상황에는 단 하나의 인덱스에 모든 값들이 담겨서 일반 연결리스트 자료구조와 마찬가지로 O(n)이 될 수도 있다.
그리고 또 주의해야할 점은 데이터 값이 많아질수록 이상적인 해시테이블을 구성하기 위해 필요한 메모리가 많아지기 때문에, 공간과 시간 사이의 장단점을 잘 조율해서 사용하는 것이 중요하다.
트라이 (trie)
검색(retrieval)의 줄임말로, 각 노드가 배열로 이루어진 트리 형태의 자료구조다.
앞서 이름 별로 정리를 했던 해시 테이블을 트라이로 만들경우 각 노드는 다음처럼 a부터 z까지 알파벳으로 이루어진 배열이 되고, 배열의 각 요소(알파벳)는 다음 노드(a-z 배열)를 가리킨다.
이름의 알파벳 순서에따라 노드가 연결되고, Harry 라는 이름을 찾고 싶은 경우 “Harry” 문자열 순서에 따라 H → a → r → r → y 순으로 노드들이 연결되어 있는지를 확인하게 된다.
위의 트라이에서 값을 검색하는데 걸리는 시간은 곧 문자열의 길이가 되고, 이름의 길이가 n이라고 하면 실행 시간은 O(n)이 된다. 다만 대부분 이름은 그리 크지 않은 상수값이기 때문에 O(1)에 가깝다고 볼 수 있다.
해시 테이블과 비교했을 때, 트라이는 데이터가 아무리 많아도 해시 함수의 영향을 받아 자료가 치우치거나 특정 값만 탐색 시간이 길어지는 일 없이 일관되게 빠른 실행 시간을 유지할 수 있다는 장점이 있지만, 모든 노드가 배열로 이루어지기 때문에 해시 테이블보다 더 많은 메모리가 필요하다는 단점이 있다.
큐, 스택, 딕셔너리
큐, 스택, 딕셔너리는 앞서 많이 다룬 주제이기 때문에 가볍게 정리만하고 넘어갑니다.
큐 - 선입선출(FIFO), 값이 아래로 쌓이는 구조
스택 - 후입선출(LIFO), 값이 위로 쌓이는 구조
딕셔너리 - ‘키’와 ‘값’으로 이루어져 있으며, 일반적인 의미에서 해시 테이블과 동일한 개념이라고도 볼 수 있다.
이것으로 ‘모두를 위한 컴퓨터 과학 (CS50 2019)’를 기반으로 한 기초 컴퓨터 공학 이론 공부를 마칩니다.
따로 강의를 들어보고 싶으실 경우 https://www.boostcourse.org/ 에서 무료로 수강이 가능하며, 제 노트에 삽입된 모든 캡처본과 이미지들은 해당 부스트코스 과정에서 가져온 것입니다.
이 뒤로 강의내용이 더 이어지는 것으로 알고 있는데 부스트코스에서는 여기까지만 한글 교육과정이 구성되어 있습니다. 영어가 되시는 분들은 https://cs50.harvard.edu/x/2021/weeks/0/ 로 가시면 2021년 최신버전의 수업이 업로드 되어있으며 자료구조 이후의 Python, SQL, HTML, CSS, JavaScript, Flask 그리고 컴퓨터공학 윤리까지 다룬 전체 교육 내용을 확인하실 수 있습니다.
댓글남기기