CS50 6주차 강좌 링크📚
이번주차는 CS50의 마지막 강좌이자 자료구조의 정의와 종류에 대한 강의이다.
데이터 구조
데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위하여 새로 정의하는 구조체를 말한다.
연결 리스트
각 인덱스의 값들이 메모리상에 연이어 저장되어있는 배열과는 다르게 값과 함께 다음값의 주소(포인터)를 함께 저장하여 메모리상에 값이 흩어져있더라도 값을 연이어 읽어오는 데이터구조를 말한다.
위와같이 값과함께 다음값의 주소를 저장하여 값들을 순차적으로 불러오고 주소값이 NULL일경우 연결리스트를 종료하게된다.이를 코드로 표현하면
#include <stdio.h>
#include <stdlib.h>
//node 구조체를 정의
typedef struct node
{
int number;
struct node *next;
}
node;
int main(void)
{
// 포인터를 NULL 로 초기화
node *list = NULL;
// 새로운 node를 위해 메모리를 할당
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 1;
// n 다음에 정의된 node가 없으므로 NULL로 초기화
n->next = NULL;
// 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 변환
list = n;
//새로운 메모리를 다시 할당
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 2;
n->next = NULL;
list->next = n;
for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
printf("%i\n", tmp->number);
}
// 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 free
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}java의 경우 LinkedList<>를 선언하여 연결리스트를 생성하고 데이터값들을 추가할 수 있다.
public void LinkedList() {
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1); // 데이터추가
list.add(2);
list.add(1, 5); // 1번 인덱스에 5추가
list.removeFirst(); // 0번 인덱스 삭제
}트리
연결리스트를 기반으로 한 새로운 데이터 구조. 노드들의 연결이 2차원적으로 구성되어있으며 이를 통해 사전에 값들의 정렬이 가능하다.
위의 그림에서 하나의 노드는 두개의 자식노드를 갖고 있으며, 왼쪽 자식노드는 자신의 값보다 작은값이 오른쪽의 자식노드는 자신의 값보다 큰값을 넣는다. 이러한 트리구조는 이진검색을 수행하는데 유리하다.
해시테이블
연결리스트의 배열. 여러 값들을 해시함수라는 맞춤형 함수를 통해 저장한다. 배열의 하나의 인덱스는 연결리스트들을 갖고있으며 해시함수를 통해 어떤 인덱스에 접근할지를 결정한다. 해시테이블의 실행시간을 결정하는것은 해시함수를 얼마나 효율적으로 만드느냐에 따라 달렸기 때문에 상황에 따라 배열의 메모리를 크게가져가더라도 검색시간을 줄여 효율성을 높일 수 있다.
해시(Hash) 값의 충돌
해시는 key를 해시함수를 통해 입력했을때 나온 결과물로, 다른 key값을 넣었을때 같은 해시값이 되는경우를 해시충돌이라한다. 해시테이블에서는 분리연결법과 개방주소법을 통해 충돌을 해결한다.
- 분리연결법(Separate Chaining)
강의의 설명과 마찬가지로 충돌이 발생하였을때 연결리스트의 자료구조를 통해서 기존의 값에 새로운 값을 연결시키는 기법이다.아래의 그림과같이 충돌이발생하여 기존의 John Smith에 Sandra Dee를 연결시켜준다. 현재 Java8의 해시테이블이 이러한 구조를 이루고 있으며 만약 연결되는 데이터가 많아진다면 캐시의 효율이 감소한다는 단점을 가지고있다.
- 개방 주소법(Open Addressing)
비어있는 해시 테이블의 공간을 활용하는 방법. 현재 버킷의 index로부터 고정폭만큼 차례로 이동하여 데이터를 저장하는 Linear Probing , 해시의 충돌이 발생한 순서의 제곱만큼 이동하여 값을 저장하는 Quadratic Probing 등이 있다.
트라이
검색시간을 줄이기위해 많은 메모리를 할당하는 구조. 기본적으로는 트리형태의 데이터 구조이지만 각각의 노드가 배열로 이루어져있다.
위의 그림과 같이 모든 알파벳들이 담긴 배열을 트리구조로 만들었을때 값을 검색하는데 걸리는 시간은 '문자열의 길이'에 의하여 결정된다. 대부분의 문자열의 길이는 길지않기 때문에 O(1)이나 마찬가지이며 실행시간이 적어진만큼 상당한 메모리를 할당해야하는 데이터 구조이다.
스택
값이 위로쌓이는 데이터 구조. 값을 넣고 뺄때 LIFO(후입선출)방식에 따라 가장 나중에 들어온값이 가장 먼저 나가게 된다.
큐
값이 아래로 쌓이는 데이터 구조. 값을 넣고 뺄때 FIFO(선입선출)방식에 따라 가장 먼저 들어온 값이 가장 먼저 나가게 된다.
강의완료!!💯
CS50강의를 마치며...
6주간 CS50강의를 진행하며 컴퓨터공학에 대한 정의와 내가 작성한 코드들이 메모리상에 어떤식으로 저장되는지에 대해서 좀 더 상세하게 알 수 있었다. 다만 아쉬운 점은 코드들이 C언어 위주로 진행되다보니 java와 약간 상이한 개념들이 있었으며 기초편이다보니 내가 생각했던 것보다 개념들에 대해서 깊게 파고든다는 느낌을 받지 못했다. 해당 부분에 관해서는 추가적으로 구글검색을 통해서 알게된 사실들을 인용문 형태로 작성하였지만 다음 강의는 컴퓨터공학에 대한 심화과정이 있는 강의를 선택할것같다.
