트라이(Trie) 데이터 구조‘트라이(Trie)’는 기본적으로 ‘트리’ 형태의 자료 구조이다. 특이한 점은 각 노드가 ‘배열’로 이루어져 있다는 것이다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 각 노드는 a부터 z까지의 값을 가지는 배열이 된다. 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킨다. 아래 그림과 같이 "Hermione", "Harry", "Hagrid" 세 문자열을 트라이에 저장해보겠다. 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가며 노드를 이어주면 된다.  트라이에서 값을 검색하는 데 걸리는 시간은 ‘문자열의 길이’에 의해 한정된다. 단순히 문자열의 각 문자를 보며 트리를 탐색해 나가기만 하면 되기 때문이다. 일반적인 영어 이..

해시 테이블은 '연결 리스트의 배열'이다. 여러 값을 몇 개의 바구니에 나눠 담는 상황을 생각해보자. 각 값들은 '해시 함수'라는 맞춤형 함수를 통해 어떤 바구니에 담길지가 결정된다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다. 이와 같이 연결 리스트가 담긴 바구니가 여러 개 있는 것이 '연결 리스트의 배열', 즉 '해시 테이블'이 된다.  해시 테이블의 동작 원리쉬운 예로 사람의 이름이 해시 테이블에 저장되고 해시 함수는 '이름의 첫 글자'인 경우를 생각해보자. 이 경우 알파벳 개수에 해당하는 총 26개의 포인터가 있을 수 있으며 각 포인터는 그 알파벳으로 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다. 해시 함수가 이상적이라면 각 바구니에는 단 하나의 값..

연결 리스트 소개데이터 구조는 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체다. 일종의 메모리 레이아웃 또는 지도로 생각할 수 있다. 이번 포스팅에서는 데이터 구조 중 하나인 연결 리스트에 대해 알아보겠다. 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다. 그러나 꼭 그럴 필요가 있을까? 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있다. 이를 '연결 리스트'라고 한다. 아래 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다.  연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리..

일정한 크기의 배열이 주어졌을 때 그 크기를 키우려면 어떻게 해야 할까? 단순하게 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 일정 크기의 메모리를 더 덧붙이면 되겠지만 실제로는 다른 데이터가 저장되어 있을 확률이 높다. 따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다. 이런 작업은 O(n), 즉 배열의 크기 n만큼의 실행 시간이 소요될 것이다. 이 과정을 아래 코드와 같이 나타낼 수 있다.#include #include int main(void){ // int 자료형 3개로 이루어진 list라는 포인터를 선언하고 메모리 할당 int *list = malloc(3 * sizeof(int)); // 포인터가 잘 선언되었는지 확..

아래와 같은 main 함수 코드가 있다. 여기서 문제가 될 만한 지점을 발견할 수 있는가?int main(void){ int *x; int *y; x = malloc(sizeof(int)); *x = 42; *y = 13; free(x);}main 함수 안의 첫 두 줄에서는 포인터 x와 y를 선언한다.  그 후 x에는 malloc 함수를 이용해 int 자료형 크기에 해당하는 메모리를 할당한다.그리고 x가 가리키는 지점에 42를 저장하고 y가 가리키는 지점에 13을 저장한다. 여기서 문제가 될 만한 부분은 *y = 13이다. y는 포인터로만 선언되었을 뿐이지 어디를 가리킬지에 대해서는 아직 정의되지 않았다. 따라서 초기화되지 않은 *y는 프로그램 어딘가를 임의로 가리키고 있..

지난 강의에서는 아래 그림과 같은 메모리 구조에 대해 간략하게 알았다.  머신 코드 영역에는 프로그램이 실행될 때 그 프로그램이 컴파일된 바이너리가 저장된다. 글로벌 영역에는 프로그램 안에서 저장된 전역 변수가 저장된다. 힙 영역에는 malloc으로 할당된 메모리의 데이터가 저장되고 스택에는 프로그램 내의 함수와 관련된 데이터가 저장된다. 힙 영역에서는 malloc에 의해 메모리가 더 할당될수록 점점 사용하는 메모리의 범위가 아래로 늘어난다. 마찬가지로 스택 영역에서도 함수가 더 많이 호출될수록 사용하는 메모리의 범위가 점점 위로 늘어난다. 이렇게 메모리 사용 범위가 늘어나다 보면 제한된 메모리 용량 하에서는 기존의 값을 침범하는 상황도 발생할 수 있다. 이를 힙 오버플로우 또는 스택 오버플로우라고 한다..

아래 코드에서 함수 swap은 정수 a와 b를 입력받아 서로의 값을 바꾸는 일을 수행한다. main 함수에서는 x에 1, y에 2를 입력하고 swap 함수를 통해 그 두 값을 바꾸려고 하고 있다. 과연 의도대로 잘 바뀌어서 출력이 될까?#include void swap(int a, int b);int main(void){ int x = 1; int y = 2; printf("x is %i, y is %i\\n", x, y); swap(x, y); printf("x is %i, y is %i\\n", x, y);}void swap(int a, int b){ int tmp = a; a = b; b = tmp;}위 코드를 컴파일하고 출력해보면 의도와는 다르게 swap..