6. 자료구조

 

부스트코스에서 진행한 '모두를 위한 컴퓨터 과학(CS50 2019)'을 수강한 뒤 작성한 내용입니다.

몰랐던 내용을 위주로 정리했기 때문에 빠진 부분이 많을 수 있습니다.

 

1. malloc과 포인터 복습

포인터로 메모리 상의 실제 주소를 확인할 수 있다.

*, malloc, free 같은 함수로 메모리 관리하는 방법이 존재한다.

*은 역참조 연산자(그 주소로 가라는 말)

할당하지 않은 메모리를 사용하면 안 좋은 일이 벌어질 수 있다.

 

2. 배열의 크기 조정하기

배열로 많은 데이터를 한번에 캡슐화 할 수 있다.

배열의 크기를 늘리려면 배열이 위치한 메모리를 다른 곳으로 이동시키거나 복사한다. 주변에 다른 데이터들로 꽉 차 있기 때문이다.

옮기거나 복사해서 이전에 사용한 메모리는 버리거나 free를 실행한다. O(n), 배열의 크기 n만큼 시간이 소요된다.

malloc은 메모리 동적 할당 함수이다.

포인터 이름 옆에 대괄호를 쓰면 컴퓨터는 자동으로 그 메모리 덩어리의 첫번째 바이트로 이동한다. 모두 malloc이 반환했던 범위 안에 있다. 

int 덩어리

int 덩어리

int 덩어리

메모리 덩어리. int arr[3]

메모리가 부족할 때 좋은 방법은 메모리를 할당 할 때마다 리스트가 null이 반환되었는지 확인해보는 것이다.

realloc : malloc의 메모리 할당, 직접 값들을 옮기거나 free를 모두 할 필요없이 한번에 합칠 수 있다. 이미 할당받은 기존 메모리 덩어리를 새롭게 가져오고 새롭게 설정된 크기로 바꾸는 작업을 한다.

배열은 본질적이고 메모리의 덩어리이다.

배열은 자동으로 free를 해준다. 컴파일러를 통해서 자동으로 진행된다.

 

3. 연결 리스트 : 도입

자료구조는 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해준다.

struct : 구조체, 자신만의 구조를 만들 수 있는 키워드. 비트맵, 비트맵 헤더 등에서 사용한다.

* : 메모리 덩어리로 접근할 수 있는 역참조 연산자.

연결 리스트 : 값들의 리스트를 저장하는 방법.

배열의 장점 : 쉬운 인덱싱, 랜덤접근으로 일정한 시간에 접근할 수 있어 빠르다.

바이너리 검색에 적용 가능하다.

연결 리스트는 값이 모두 떨어져 있기 때문에 대괄호로 인덱싱하여 접근할 수 없다.

문자 \0을 뜻하는 NUL과 NULL(포인터)은 다르다. 둘 다 0이긴 하다.

어떤 값이 실제로 메모리의 어디에 있는지는 중요하지 않다.

연결리스트는 메모리 덩어리 여러 개를 포함한 데이터구조이다.

node란 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미(컴퓨터 공학에서), 그래프의 노드와 비슷한 역할을 한다.

node 안에서 node를 쓸 수는 없다. typedef struct node라고 선언한다.

struct node *next;

 

4. 연결 리스트 : 코딩

연결 리스트에 값이 없으면 리스트가 없다는 것을 알려주는 변수가 있어야 하는데, 값이 없을 때 이를 표현하는 가장 간단한 방법은 0을 저장해서 'null'이라는 새로운 별명을 가지도록 하는 것이다.

(*n).number=2; == n->number=2; 두 코드는 같은 의미이다.

노드가 null이 아닌지 확인되기 전까지는 노드를 건드리거나 화살표 기호를 사용해서는 안된다.

얼마나 리스트가 크든 계속해서 임시 포인터를 움직여서 null을 찾을 때까지 따라간다.

값들이 어디에 있는지 기억하고 있는 변수가 없다면 메모리 누수가 발생하고, 컴퓨터에 요청할 수 있지만 다시 되돌려 받을 수 없다.

 

5. 연결 리스트 : 시연

컴퓨터는 한번에 하나의 메모리만 볼 수 있다. 노드의 한 칸만 보인다.

값을 정렬하기 위해서 각각의 값을 찾으려면 최대한으로 모든 값을 확인해야 한다.

연결리스트로 리스트에 동적으로 추가할 수 있다. 추가적인 값들을 malloc 하면 된다.

장점 : 배열처럼 숫자를 추가하기 위해서 크기를 조절하고 기존의 값을 모두 옮기지 않아도 된다.

단점 : 임의 접근을 할 수 없다. 처음부터 끝까지 가기 위해서 포인터를 따라가야 한다. 중간값으로 바로 갈 수 없다.

임의 접근을 사용하면 이진 탐색을 잘 할 수 있다. 연결 리스트는 이진 검색이 되지 않는다.

 

6. 연결 리스트 : 트리

트리는 두 개의 포인터를 가진 노드(이진 탐색 트리)

'탐색'트리는 순서를 맞추기 위해 신경을 썼다는 의미이다.

트리의 높이는 로그를 따른다.

재귀에 가장 적합한 방법이다.

트리에서 재귀적으로 정의되었다라는 의미는 어떤 노드에서라도 왼쪽이 더 작고 오른쪽이 더 크다는 것이다.

트리를 탐색하려면 트리의 루트릐 주소를 받는다.

log n : 이진 탐색 트리의 탐색 속도

이진 텀색 트리에 추가할 때 : 계속해서 작거나 큰 숫자를 넣으면 트리가 아주 얇고 길어진다.

이진 검색 트리의 균형을 유지할 수 있는 알고리즘이 있다. 어떤 값을 넣으면 요소들을 움직이게 되는 것이다.

그래서 이진 탐색이 가능한 배열과 같은 실행 시간을 가진다(log n)

연결 리스트는 크기를 줄이거나 늘릴 수 있지만 이진 탐색이 불가능하다. 공간을 더 써서 노드에 포인터가 두개씩 들어가게 하면 탐색하는 시간을 log로 단축시킨다.

 

7. 해시 테이블

배열과 연결 리스트를 조합한 것이다.

해시 테이블에서는 단어나 이름같은 입력값이 들어온다면 그 단어에 포함된 문자를 보고 어디에 그 이름을 넣을지 결정하는 방식이 흔하게 사용된다.

세로는 배열, 가로는 연결 리스트(예시)

충돌 : 어떤 값을 넣으려고 하는데 이미 무언가 들어있는 경우. 해시 테이블은 이것을 연결 리스트로 해결한다.

여기서 인덱싱을 하는데 사용하는 배열은 해시함수이다.

최악의 경우 O(n)의 시간이 추가하거나 탐색할 때 필요하게 된다. 대부분의 이름, 단어가 같은 문자로 시작될 때 첫 한글자가 아닌 첫 두글자를 본다. 공간은 더 많이 필요하지만 충돌할 확률은 낮아진다.

하지만 이렇게 글자를 늘려가다가 어느 순간부터는 그냥 연결하는 것이 낫다. 시간은 좀 더 걸린다. 시간과 공간 사이에 균형이 필요하다.

해시 테이블은 O(n)이 될 수 있지만 이론적으로는 느려질 수 있다.

 

8. 트라이

검색(retrieval)의 줄임말이다.

어떤 자원을 절약하기 위해 다른 자원을 소비하는 패턴이기 때문에 많은 메모리가 든다.

자료 구조 안에 있는 이름이나 단어를 찾는데 일정한 실행 시간을 가진다.

각각의 노드가 배열로 이루어진 트리다.

만약 트라이에 이름을 저장하고 싶은 경우 그 이름의 모든 글자들을 봐야한다.

해당 노드에 자식 노드가 없다면 그 아래에 다른 트리, 혹은 가지가 없으면 새로운 노드를 할당한다. 새로운 노드는 새로운 배열이다.

C에서는 boolean 연산식으로 여기에 이름 하나가 끝난다는 것을 표기할 수 있다.

이름의 각 글자에 대해서 하나의 노드(배열)이 저장된다.

Hagrid, Harry, Hermionie는 최소 하나의 노드를 나누어 가진다. 

고정된 값은 수학적, 컴퓨터 과학적으로 상수라고 한다. O(1) 상수 시간.

이 자료구조를 탐색, 삽입할 때 k값이 상수인 O(k)라는 것을 달성한다.

상수는 점근적으로 O(1)과 같다.

다른 자료구조는 이름들의 갯수에 따라 실행시간이 길어졌지만 트라이는 그렇지 않다.

빠를 대신 메모리를 많이 사용한다. 이름을 많이 삽입할수록 몇 노드들은 나누어 사용한다.

 

9. 스택, 큐, 딕셔너리

큐 : FIFO, 선입선출.

enqueue : 줄에 서서 들어가는 것 / dequeue : 줄을 바져나오는 것

스택 : LIFO 후입선출.

push : 넣는다. / pop : 뺀다.

딕셔너리 : 해시 테이블이라고도 생각할 수 있는 개념이다. 키/값, 단어/값, 단어/페이지 번호 등 쌍으로 이루어진 자료구조이다.