해시 테이블

• 해시 테이블은 ‘연결 리스트의 배열’
• 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해 보자.
• 각 값들은 ‘해시 함수’라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정된다.
• 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다.
• 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 ‘연결 리스트의 배열’, 즉 ‘해시 테이블’

쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우를 생각해 보자.

그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 된다.

• 만약 해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담기게 될 것
• 따라서 검색 시간은 O(1)
• 하지만 최악의 상황에는 단 하나의 바구니에 모든 값들이 담겨서 O(n)이 될 수도 있다.
• 일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 거의 O(1)에 가깝다고 볼 수 있다.

트라이

• 트라이’는 기본적으로 ‘트리’ 형태의 자료 구조
• 특이한 점은 각 노드가 ‘배열’로 이루어져있다는 것입니다.
• 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열
• 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킨다. 

아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보면,

루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다.

• 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은  ‘문자열의 길이’에 의해 한정
• 단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되기 때문
• 일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값(예, 20자 이내)이기 때문에 O(1)이나 마찬가지라고 볼 수 있다.

그 외 자료구조

① 큐

• 큐는 메모리 구조에서 살펴봤듯이 값이 아래로 쌓이는 구조
• 값을 넣고 뺄 때 ‘선입 선출’ 또는 ‘FIFO’라는 방식을 따르게 된다. 가장 먼저 들어온 값이 가장 먼저 나가는 것
• 은행에서 줄을 설 때 가장 먼저 줄을 선 사람이 가장 먼저 업무를 처리하게 되는 것과 동일
• 배열이나 연결 리스트를 통해 구현 가능

② 스택

• 반면 스택은 역시 메모리 구조에서 살펴봤듯이 값이 위로 쌓이는 구조
• 따라서 값을 넣고 뺄 때 ‘후입 선출’ 또는 ‘LIFO’라는 방식을 따르게 된다. 가장 나중에 들어온 값이 가장 먼저 나가는 것
• 뷔페에서 접시를 쌓아 뒀을 때 사람들이 가장 위에 있는(즉, 가장 나중에 쌓인) 접시를 가장 먼저 들고 가는 것과 동일
• 역시 배열이나 연결 리스트를 통해 구현 가능

③ 딕셔너리

• 딕셔너리는 ‘키’와 ‘값’이라는 요소로 이루어져 있다.
• ‘키’에 해당하는 ‘값’을 저장하고 읽어오는 것. 마치 대학교에서 ‘학번’에 따라서 ‘학생’이 결정되는 것과 동일
• 일반적인 의미에서 ‘해시 테이블’과 동일한 개념이라고도 볼 수 있다.
• ‘키’를 어떻게 정의할 것인지가 중요

배열의 크기 조정 - realloc  함수

• 일정한 크기의 배열이 주어졌을 때, 그 크기를 키우려면 어떻게 해야 할까?
• 단순하게 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 일정 크기의 메모리를 더 덧붙이면 되겠지만, 실제로는 다른 데이터가 저장되어 있을 확률이 높다.
• 따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다.
• 따라서 이런 작업은 O(n), 즉 배열의 크기 n만큼의 실행 시간이 소요될 것

연결 리스트: 도입

• 데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체 (일종의 메모리 레이아웃, 또는 지도)
• 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다.
• 하지만 꼭 그럴 필요가 있을까? 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있다. 이를 ‘연결 리스트’라고 한다

• 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다.
• 연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 함께 저장
• 3은 다음 값이 없기 때문에 NULL (\0, 즉 0으로 채워진 값을 의미합니다)을 다음 값의 주소로 저장

연결 리스트는 아래 코드와 같이 간단한 구조체로 정의할 수 있다. 

• node 라는 이름의 구조체는 number 와 *next  두 개의 필드가 함께 정의되어 있다.
• number는 각 node가 가지는 값, *next 는 다음 node를 가리키는 포인터
• 여기서 typedef struct 대신에 typedef struct node 라고 ‘node’를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함

연결 리스트: 코딩

앞서 정의한 구조체를 활용해서 실제로 연결 리스트를 구현해보기

연결 리스트: 시연

• 배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다.
• 하지만 이런 유동적인 구조는 그 대가가 따릅니다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능
• 연결 리스트에 값을 추가하거나 검색하는 경우를 생각해 보면,
• 이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 한다.
• 따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 된다.
• 배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것에 비해서 다소 불리한 것  
• 이처럼 여러 데이터 구조는 각각 장단점이 존재한다.
• 프로그래밍을 할 때 목적에 부합하는 가장 효율적인 데이터 구조를 고민해서 사용하는 것이 중요!

연결 리스트: 트리

• 트리는 연결리스트를 기반으로 한 새로운 데이터 구조
• 연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다
• 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다.
• 가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 한다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 한다.

※ 아래 그림은 트리의 예시. 나무가 거꾸로 뒤집혀 있는 형태를 생각하면 된다.

• 위 그림에 묘사된 트리는 구체적으로 ‘이진 검색 트리’
• 각 노드가 구성되어 있는 구조를 살펴보면 일정한 규칙을 알 수 있다.
• 먼저 하나의 노드는 두 개의 자식 노드를 가진다.
• 또 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값보다 크다.
• 따라서 이런 트리 구조는 이진 검색을 수행하는데 유리

아래 코드에서는 이진 검색 트리의 노드 구조체와 “50”을 재귀적으로 검색하는 이진 검색 함수를 구현하였다. (차근히 읽어보기)

이진 검색 트리를 활용하였을 때 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)

힙 오버플로우/ 스택 오버플로우

• 힙 영역에서는 malloc 에 의해 메모리가 더 할당될수록, 점점 사용하는 메모리의 범위가 아래로 늘어남
• 마찬가지로 스택 영역에서도 함수가 더 많이 호출 될수록 사용하는 메모리의 범위가 점점 위로 늘어남
• 이렇게 점점 늘어나다 보면 제한된 메모리 용량 하에서는 기존의 값을 침범하는 상황도 발생
• 이를 힙 오버플로우 또는 스택 오버플로우라고 한다.

사용자에게 입력 받기

스택은 우리가 여태껏 많이 써왔던 get_int나 get_string 과 같은 함수에서도 사용된다. 만약 이런 함수들을 직접 구현한다면 아래와 같은 코드가 될 것

[get_int 코드]

[get_string 코드]

• 위 코드들에서 scanf라는 함수는 사용자로부터 형식 지정자에 해당되는 값을 입력받아 저장하는 함수
• get_int 코드에서 int x를 정의한 후에 scanf에 s가 아닌 &x로 그 주소를 입력해주는 부분을 유의하기
• scanf 함수의 변수가 실제로 스택 영역 안에 x가 저장된 주소로 찾아가서 사용자가 입력한 값을 저장하도록 하기 위함
• 반면 get_string 코드에서는 scanf에 그대로 s를 입력해줬다.
• 그 이유는 s를 크기가 5인 문자열, 즉 크기가 5인 char 자료형의 배열로 정의하였기 때문
• clang 컴파일러는 문자 배열의 이름을 포인터처럼 다룹니다. 즉 scanf에 s라는 배열의 첫 바이트 주소를 넘겨주는 것

파일 쓰기

사용자로부터 입력을 받아 파일에 저장하는 프로그램도 작성하기

• fopen이라는 함수를 이용하면 파일을 FILE이라는 자료형으로 불러올 수 있다.
• fopen 함수의 첫번째 인자는 파일의 이름, 두번째 인자는 모드로 r은 읽기, w는 쓰기, a는 덧붙이기를 의미
• 사용자에게 name과 number라는 문자열을 입력 받고, 이를 fprintf 함수를 이용하여 printf에서처럼 파일에 직접 내용을 출력할 수 있다.
• 작업이 끝난 후에는 fclose함수로 파일에 대한 작업을 종료해줘야 한다.

파일 읽기

파일의 내용을 읽어서 파일의 형식이 JPEG 이미지인지를 검사하는 프로그램을 작성하기

• 위 코드에서 main 함수를 보면 사용자로부터 입력을 받는 것을 알 수 있다. 여기서는 파일의 이름을 입력으로 받을 예정
• 만약 argc가 2가 아니라면, 파일명이 입력되지 않았거나 파일명 외의 다른 인자가 입력되었기 때문에 1(오류)을 리턴하고 프로그램을 종료
• 만약 argc가 2라면 프로그램이 그대로 진행
• 입력받은 파일명(argv[1])을 ‘읽기(r)’ 모드로 불러옴
• 만약 파일이 제대로 열리지 않으면 fopen 함수는 NULL을 리턴하기 때문에 이를 검사해서 file을 제대로 쓸 수 있는지를 검사하고 아니라면 역시 1(오류)를 리턴하고 프로그램을 종료
• 만약 파일이 잘 열렸다면, 프로그램이 계속 진행
• 그 후 크기가 3인 문자 배열을 만들고, fread 함수를 이용해서 파일에서 첫 3바이트를 읽어옴
• fread 함수의 각 인자는 (배열, 읽을 바이트 수, 읽을 횟수, 읽을 파일)을 의미
• 그리고 마지막으로 읽어들인 각 바이트가 각각 0xFF, 0xD8, 0xFF 인지를 확인
• 이는 JPEG 형식의 파일을 정의할 때 만든 약속으로, JPEG 파일의 시작점에 꼭 포함되어 있어야 함
• 따라서 이를 검사하면 JPEG 파일인지를 확인할 수 있다.

※ 디지털 포렌식에서 쓰이는 매직 넘버들
.jpg는 FFD8 / .gif는 47 49 46 38 [GIF89] / .png는  89 50 4E 47 .PNG
사진파일 확장자 뿐만아니라 .mp3 49 44 33 [ID3] / .avi 52 49 46 46 [RIFF] / .zip 50 4B 03 04 [PK]
등이 있다.

메모리 누수

• malloc 함수를 이용하여 메모리를 할당한 후에는 free라는 함수를 이용하여 메모리를 해제해줘야 한다.
• 그렇지 않은 경우 메모리에 저장한 값은 쓰레기 값으로 남게 되어 메모리 용량의 낭비가 발생하게 되기 때문
• 이러한 현상을 ‘메모리 누수’라고 한다.

※ valgrind라는 프로그램을 사용하면 우리가 작성한 코드에서 메모리와 관련된 문제가 있는지를 쉽게 확인할 수 있다. 

다음과 같은 명령어를 사용하면 filename 파일에 대한 valgrind의 검사 내용을 쉽게 확인할 수 있다.

• f 함수를 살펴보면 먼저 포인터 x에는 int형의 사이즈(4바이트)에 10배에 해당하는 크기의 메모리, 즉 40바이트를 할당한다.
• 그리고 x의 10번째 값으로 0을 할당한다.
• 그리고 main 함수에서 f를 실행하게 되는데,
• 이 코드를 valgrind 로 검사해보면 버퍼 오버플로우와 메모리 누수 두 가지 에러를 확인할 수 있다.
• 먼저 버퍼 오버플로우는 x[10] = 0; 코드로 인해 발생한다.
• 우리는 10개의 int형의 배열을 만들었는데 배열의 인덱스가 0부터 시작한다는 점을 감안하면 인덱스 10은 11번째 인덱스에 접근하겠다는 의미이고, 이는 정의되지 않은 것이기 때문에 버퍼 오버플로우가 발생하는 것
• 따라서 이 오류는 0에서 9 사이의 인덱스를 사용하면 해결할 수 있다.
• 또한 메모리 누수는 x라는 포인터를 통해 할당한 메모리를 해제하기 위해 free(x) 라는 코드를 추가해줌으로써 해결할 수 있다.

메모리 교환, 스택, 힙

① 예제 1 swap 함수

• 함수 swap은 정수 a와 b를 입력받아 그 값을 바꾸는 일을 수행한다. 
• main 함수에서는 x에 1, y에 2를 입력하고 swap 함수를 통해 그 두 값을 바꾸려고 하고 있다.
• 그러나 위 코드를 컴파일하고 출력해보면 의도와는 다르게 swap 함수를 거친 후에도 x와 y의 값이 바뀌지 않은채 그대로 출력된다.
• 사실 swap 함수는 교환 작업을 제대로 수행하고 있는데, 문제는 교환하는 대상이 x, y 그 자체가 아닌 함수 내에서 새롭게 정의된 a, b라는 것
• a와 b는 각각 x와 y의 값을 복제하여 가지게 된다. 서로 다른 메모리 주소에 저장되는 것.

② 데이터 저장 구역

• 그림에서와 같이 메모리 안에는 데이터 저장되는 구역이 나뉘어져 있다.
• 머신 코드 영역에는 우리 프로그램이 실행될 때 그 프로그램이 컴파일된 바이너리가 저장
• 글로벌 영역에는 프로그램 안에서 저장된 전역 변수가 저장
• 힙 영역에는 malloc으로 할당된 메모리의 데이터가 저장
• 스택에는 프로그램 내의 함수와 관련된 것들이 저장

• 이를 바탕으로 다시 생각해보면, 위의 코드에서 a, b, x, y, tmp 모두 스택 영역에 저장되지만
• a와 x, b와 y는 그 안에서도 서로 다른 위치에 저장된 변수!
• 따라서 a와 b를 바꾸는 것은 x와 y를 바꾸는 것에 아무런 영향도 미치지 않는 것
• 따라서 아래 그림 및 코드와 같이 a와 b를 각각 x와 y를 가리키는 포인터로 지정함으로써 이 문제를 쉽게 해결할 수 있다.

문자열

우리는 문자열을 저장하기 위해 CS50 라이브러리에 포함된 string 자료형을 사용했다.

아래와 같이 s에 “EMMA”라는 값을 저장한다고 생각해 보면,

문자열은 결국 문자의 배열이고, s[0], s[1], s[2], … 와 같이 하나의 문자가 배열의 한 부분을 나타낸다.

( ※ 가장 마지막의 \0은 0으로 이루어진 바이트로, 문자열의 끝을 표시하는 약속 )

여기서 변수 s는 결국 이러한 문자열을 가리키는 포인터

더 상세히는 문자열의 가장 첫번째 문자, 즉 주소 0x123에 있는 s[0]를 가리키게 된다.

실제 CS50 라이브러리를 보면 string 자료형은 아래와 같이 정의되어 있다.

여기서 typedef는 새로운 자료형을, char *은 문자에 대한 포인터를, string은 자료형의 이름을 의미

따라서 아래 두 코드는 동일하게 동작할 것

① string 자료형을 이용하여 “EMMA” 출력

② char 포인터를 이용하여 “EMMA” 출력

2번 코드의 char *s에서 s라는 변수는 문자에 대한 포인터가 되고, “EMMA”라는 문자열의 가장 첫 번째 값을 저장하기 때문

// 내가 이해한 바 : string = char*, 즉 문자열 첫 주소에대한 포인터

 문자열 비교

위 코드를 실행하면, s라는 포인터의 값, 즉 “EMMA”라는 문자열의 가장 첫 값인 “E”에 해당하는 메모리 주소를 출력하게 될 것

그렇다면 아래 코드들은 무엇을 출력할까?

s가 가리키는 곳을 시작으로 “EMMA”라는 문자열로 이루어진 문자들의 배열이 있으니, 각각

s라는 문자열의 첫 번째 문자에 해당하는 주소값,

s라는 문자열의 두 번째 문자에 해당하는 주소값,

s라는 문자열의 세 번째 문자에 해당하는 주소값,

s라는 문자열의 네 번째 문자에 해당하는 주소값을 출력

( &s[0]는 “E”의 주소값을, &s[1]은 “M”의 주소값을,  &s[2]은 “M”의 주소값을,  &s[3]은 “A”의 주소값을 의미 )

문자열은 첫번째 문자를 시작으로 메모리상에서 바로 옆에 저장되어 있다.

다시 말해, 가장 첫 번째 문자에 해당하는 주소값을 하나씩 증가시키면 바로 옆에 있는 문자의 값을 출력할 수 있는 것

따라서 아래 코드는 E M M A를 순서대로 출력할 것

문자열을 비교할 때도 아래 코드와 같이 문자열이 저장된 변수를 바로 비교하게 되면

그 변수가 저장되어 있는 주소가 다르기 때문에 다르다는 결과가 나올 것

정확한 비교를 위해서는 실제 문자열이 저장되어 있는 곳으로 이동하여, 각 문자를 하나하나씩 비교해야 한다.

문자열 복사

문자열을 복사하기 위해 아래 코드를 실행하면?

• 사용자에게 입력값을 받아 string s에 저장하고, string t를 s로 정의
• 그리고 t의 첫 번째 문자를 toupper 함수를 이용하여 대문자로 바꾼다면 s와 t는 각각 어떻게 출력 될까?
• 입력값으로 “emma”를 주게 된다면, 단순한 예상과는 다르게 s와 t 모두 “Emma”라고 출력이 된다.
• 그 이유는  s라는 변수에는 “emma”라는 문자열이 아닌 그 문자열이 있는 메모리의 주소가 저장되기 때문
• string s 는 char *s 와 동일한 의미
• 따라서 t도 s와 동일한 주소를 가리키고 있고, t를 통한 수정은 s에도 그대로 반영이 되게 되는 것

그렇다면 두 문자열을 실제로 메모리상에서 복사하려면 어떻게 해야 할까?

아래 코드와 같이 메모리 할당 함수를 사용하면 됩니다

• 위의 코드와 다른 점은 malloc이라는 함수를 이용해서 t를 정의한다는 것
• malloc 이라는 함수는 정해진 크기 만큼 메모리를 할당하는 함수
• 즉 s 문자열의 길이에 널 종단 문자(\0)에 해당하는 1을 더한 만큼 메모리를 할당
• 그리고 루프를 돌면서 s 문자열 배열에 있는 문자 하나 하나를 t 배열에 복사해준다.
• 이 코드를 컴파일 후 실행시키고 입력값으로 “emma”를 주면 우리가 예상한 대로 s는 “emma”가, t는 “Emma”가 성공적으로 출력