CS50x 2023 - Lecture 5 - Data Structures

• enqueue: queue에 추가시키는것
• dequeue: queue에서 빼는것
  
  
• FIFO(First in first out): 먼저 들어간값이 먼저 나옴
• LIFO(Last in first out): 마지막으로 들어간값이 먼저 나옴. (기존것들은 계속 쌓인다는 문제가 있음)

Resizing Arrays

아래 코드는 array를 resize하는 예시이다.

6번째 줄에서 list라는 이름의 array에 integer 3개가 들어가는 memory를 malloc펑션을 이용하여 allocation해주고 있다.

그 아래 7~10번째에서는 memory allocation error의 방지를 위한 안전장치를 설정해두었다. (return 1하여 프로그램을 종료함)

12~14번째 줄에서 list란 이름의 각 자리에 정수 1, 2, 3을 넣어주고 있다.

18번째 줄에서는 resize를 위한 tmp란 이름의 array를 만들어주고 있는데, list와 달리 정수가 하나 더 들어갈 memory를 주고 있다.

여기서 쓰이는 realloc은 malloc과 달리 두개의 arguments를 받는다. 하나는 변경의 기준이 되는 메모리의 크기이고, 두번째는 바꾸고 싶은 사이즈 값이다.

19~23번째 줄에서는 7~10번째 줄과 같은 memorry allocation error방지를 위한 안전장치가 보인다.

 

 

24번째 줄에서 list = tmp를 하여 list가 tmp의 memory를 point하도록 하였고, 26번째 줄에는 비어있었던 4번째 자리에 숫자 4를 채워준다.

이를 28~31번째줄처럼 출력하면 정수 1, 2, 3, 4가 나온다. resize 된것이다.

(근데 28번째 줄에 i < 3이 아니고 i < 4로 해야 1, 2, 3, 4 가 나옴. 강의에서는 저 숫자를 늘려서 출력해보지 않지만, 여튼 resize했으니 저 숫자도 하나 늘려서 확인해줘야 한다.)

중간과 끝에 free함수를 이용하여 list의 memory를 free(더이상 사용하지 않겠다고 선언) 한 점에도 유의하자.

 

 

NUL 과 NULL의 차이

• NUL: 'nul character'라고도 불리며, 컴퓨터에서 문자열의 끝을 나타내는데 사용되는 문자. ASCII 코드에서 숫자 0에 해당하며, 문자열의 끝을 표현하는 데 사용된다.
• NULL: 보통 프로그래밍에서 사용되며, '아무것도 없음'을 나타낸다. C, C++, Java, JavaScript 등의 많은 프로그래밍 언어에서 주로 포인터나 참조 타입의 변수가 메모리의 어떤 영역도 가리키지 않는다는 것을 의미한다.

 

Linked list

Linked list란 데이터 요소들을 순서대로 저장하는 자료 구조인데, 각 요소는 아래 그림처럼 데이터 값과 다음 요소를 가리키는 포인터로 구성되어 있다. (아래 그림에서 빈칸이 포인터가 들어가는 부분이다. 포인터는 화살표가 가리키는 memoryd의 주소를 값으로 가지고 있다)

첫 번째 요소를 가리키는 특별한 포인터인 헤드(Head)가 있고, 각 요소는 다음 요소를 가리키는 링크를 통해 순서대로 연결된다. Linked list에는 Singly Linked List, Doubly Linked List, Circular Linked List 등 여러 종류가 있다. Single Linked List는 각 노드가 다음 노드를 가리키는 링크만을 갖고 있고, Doubly Linked List는 각 노드가 이전 노드와 다음 노드를 모두 가리키는 링크를 갖고 있다.

Linked list는 데이터의 삽입과 삭제가 배열과 달리 비교적 유연하게 처리될 수 있다는 장점이 있으나(memory address를 자유롭게 사용할 수 있음. 꼭 안붙어있어도 되니까), 특정 위치에 직접 접근하는 데에는 시간이 더 걸릴 수 있다는 점, pointer arithmetic이 불가능하다는점(주소 + 1이 반드시 배열의 다음 값이 아니라서), data당 다음 데이터의 포인터값을 갖고 있으므로 데이터를 이중으로 사용한다는 등의 단점이 있다. Trade off인것이다.

 

 

강의에서는 위의 아이디어에서 Singly linked list를 코드로 구현해보고 있다.

프로그램에 1, 2, 3과 같은 인수 3개를 입력하여 이 인수들을 노드화해서 연결시키는 것이다.

 

먼저, 4~9번째 줄과 같이 typedef를 활용하여 node라는 struct를 정의한다.

하나의 노드가 자체적인 정수를 갖고, 그 다음 노드를 가리키는 포인터도 갖도록 정의하고 있다.

 

그리고 11번째 줄에서부터는 앞서 정의한 node를 활용한 main 함수를 만들어주고 있다.

11번째 줄의 int main(int argc, char *argv[])는 프로그램이 실행될 때 커맨드 라인으로부터 인자(argument)를 전달받는 데 사용되는 표준적인 표현이다.

• int argc: 'argc'는 'argument count'의 줄임말로, 프로그램에 전달되는 명령행 인자(argument)의 개수이다.
• char *argv[] 또는 char **argv: 'argv'는 'argument vector'의 줄임말로, 명령행 인자들을 저장하는 문자열 배열이다. 각 요소는 프로그램에 전달된 각각의 인자를 가리키는 포인터이다.
  가령, 프로그램을 실행시키면서 1, 2, 3을 인자로 나란히 넣으면 argc는  4이고, argv 배열에는 프로그램이름, 1, 2, 3 총 4개 인자가 순서대로 들어간다. 인덱스 0의 포인터는 프로그램 이름을 가리키며, 인덱스 1부터는 각각의 명령행 인자를 가리키게 되는 것이다.
  그렇기 때문에 아래 예시의 15번째 줄에서도 for loop을 int = 1에서부터 돌린다. 0은 프로그램 이름이기 때문.

17번째 줄에서부터 보면 argv가 char *이기 때문에 atoi() (ASCII to integer) 함수를 써서 배열의 i번째 숫자를 number에 저장해주고 있다.

19번째 줄에서는 node에 memory를 배분해주고 있으며, 20~23번째 줄에서는 memory allocation fail을 방지하는 안전장치가 마련되있다.

24번째 줄에서는 해당 node의 number에 입력된 number 값을 넣어주고 있고,

25번째 줄에서는 해당 node의 next에 NULL을 넣어줌으로써 해당 next라는 포인터가 가리키는 주소의 값에 들어있을 garbage value를 비워낸다.

27번째 줄은 해당 node가 현재 리스트의 최초 값을 가리키는 next field를 갖도록 하는것이며, 이과정이 prepend이다. 이 과정이 바로 2번째 룹에서는 1번째 노드를 가리키는 2번째 노드를 만드는것이고, 3번째 룹에서는 2번째 노드를 가리키는 3번째 노드를 만드는것이다.

그런 뒤에 28번째 줄에서 현재의 list를 업데이트 하는것이다.

 

31번째 줄에서부터는 for loop의 밖에서 *ptr 이라는 temporary pointer를 만들어서, 리스트의 prepend된 노드들을 입력된 값을 역으로 추적하여 각 노드에 있던 값을 출력하도록 하고 있다.

그래서 ./list.c 1, 2, 3을 입력하면 3, 2, 1이 역순으로 한줄씩 출력된다.

32번째 줄에 ptr != NULL 조건이 붙는 이유는, 젤 첨에 입력되었던 node는 어딘가를 가리키는 point 주소값이 없고 garbage value를 지우기만 했기 때문에 NULL이기 때문이다. 젤 첨에 입력된 node까지 출력되면 while loop을 멈추려는 것이다.

 

코드의 끝에서는 다시 loop을 활용하여 노드에 활용했던 memory들을 순차적으로 free 해주고 있다.

 

 

Binary serarch tree (BST)

 

전화번호부 예시로 보여줬던 binary search의 신속함과 방금 배운 linked list의 역동성이란 장점을 합한 Binary search tree라는 것이 있다.

 

가령, 1부터 7까지의 배열을 아래와 반, 반의 반, 반의반씩 쪼개어 아래와 같은 tree형태로 만드는 것이다.

이때 4가 루트 노드이고, 4의 왼쪽에는 반드시 4보다 작은 수만 있으며, 오른쪽에는 4보다 큰수만 있을수 있다.

그 밑의 노드들도 왼쪽, 오른쪽이 마찬가지로 구성되어 있다.

 

이를 코드로 나타내면 아래와 같다.

 

다만 루트가 너무 작거나 너무 큰 수 등 너무 한쪽에만 가지가 치우쳐져있으면 linked list랑 다를게 없는 상황이 되어버리고,

그런 경우 루트를 바꿔줘야 하는 번거로움이 있을 수 있다.

 

 

Dictionary

Dictionary는 키(key)와 값(value)을 쌍으로 저장하는 자료 구조로, 각 키는 고유한 값을 가지며 그 키와 연관된 값에 접근하고 저장하는데 사용된다. 딕셔너리는 해시 테이블(Hash table)로 구현될 수 있다.

 

 

Hash table

Hash table은 키(key)와 값(value)을 연결하여 데이터를 저장하는 자료구조 중 하나로, 일반적으로 배열(Array)로 구현된다. Hash Function을 사용하여 키(key)를 해시(Hash)값으로 변환하고, 이 해시 값을 인덱스로 사용하여 배열에 데이터를 저장하거나 검색한다.

해시 테이블의 가장 큰 장점은 평균적으로 O(1)의 시간복잡도를 가지는 빠른 데이터 접근인데, 즉 해시 함수에 의해 계산된 위치로 바로 접근하여 데이터를 저장하거나 검색할 수 있다는 것이다. 하지만 서로 다른 키가 동일한 해시 값을 가지는 충돌(Collision)이 발생할 수 있고, 이를 해결하기 위해 더 고유한 해시키를 생성하는등의 다양한 방법들이 존재한다.

 

 

Trie

Trie(트라이)는 트리(Tree) 자료 구조의 변형 중 하나로, 단어나 문자열을 저장하고 검색하는 데 사용되는 자료 구조이다.

위 그림처럼 트라이는 각 문자를 노드(Node)로 갖는 트리 구조로 이루어져 있으며, 각 노드가 문자 하나를 나타내고 루트 노드(root node)부터 시작하여 각 문자에 해당하는 자식 노드들을 연결하여 검색 과정에서 문자열을 찾거나 찾지 못할 때까지 이동한다.

문자열 검색 시 시간 복잡도는 O(m)이며, 여기서 m은 검색하려는 문자열의 길이이다. 이처럼 트라이는 각 문자를 노드로 표현하여 문자열 검색에 있어서 빠르고 효율적이지만, 저장 공간 측면에서는 메모리를 많이 사용하는 단점이 있다.