200tmdghks 님의 블로그

목차트라이의 개념 및 구조트라이의 동작 방식트라이의 시간 복잡도와 효율성해시 테이블과 비교 1. 트라이의 개념 및 구조트라이는 문자열을 저장하기 위해 특화된 트리 형태의 자료 구조로, 노드들이 문자 배열 형태로 구성되어 있음. 각 노드는, 다음 문자로 이어지는 자식 노드들을 배열 형태로 가짐. (영어 알파벳 기준으로 보면 각 노드는 최대 26개의 포인터(또는 링크)를 가짐.) 1-1. "hello"를 저장할 경우루트 노드에서 'h' 자식 노드로 이동그 다음 'e' 자식 노드로 이동'l' → 'l' → 'o' 순으로 이동하며 노드 연결이 구조를 통해, 공통 접두사를 갖는 문자열들이 같은 경로를 공유 가능.  2. 트라이의 동작 방식 Hermione, Harry, Hagrid를 트라이에 저장예를 들어, "H..

목차해시 테이블 (Hash Table) 해시 함수의 개념과 구현 방법해시 테이블 구조와 작동 원리해시 충돌과 해결 방법해시 테이블의 시간 복잡도 1. 해시 테이블 (Hash Table) 데이터를 해시 함수를 통해 적절한 위치(버킷)에 저장함으로써, 빠른 데이터 검색을 가능하게 하는 자료 구조.일반적으로 검색, 삽입, 삭제를 평균 O(1)의 시간 복잡도로 처리 가능.  전통적인 배열, 연결 리스트, 트리와 달리 해시 테이블은 key를 통해 직접 접근 가능=> (다만, 해시 함수의 품질과 충돌 해결 방식에 따라 성능 차이 발생)기본 개념은 "해시 함수로 키를 변환 => 배열 인덱스로 사용 => 해당 인덱스에 값을 저장"예를 들어 "apple"이라는 값을 저장한다고 할 때, 이 값을 숫자로 변환하고 특정 크기..

목차연결 리스트 시연배열과 연결 리스트 비교배열이 정렬되지 않았을 때의 검색 시간 비교연결 리스트 기반 트리 구조 이해이진 검색 트리의 장단점 1. 연결 리스트 시연 연결 리스트는 데이터를 선형으로 저장하는 구조로, 각 노드가 다음 노드를 가리키는 포인터를 포함. 중요각 노드는 값과, 다음 노드의 주소를 포함중간에 노드를 추가할 경우 포인터만 수정하면 됨배열처럼 연속된 메모리 공간 필요 없음그러므로, 삽입/삭제가 자주 일어나는 환경에서 유리. 1-1. 예시node *list = NULL;node *n = malloc(sizeof(node));n->number = 1;n->next = NULL;list = n;이후 노드를 계속 이어 붙이며 리스트를 확장 가능. 2. 배열과 연결 리스트 비교 배열: 임의 접..

목차연결 리스트배열과의 차이점 및 장단점 비교연결 리스트 구조체 정의연결 리스트 구현 예시연결 리스트의 중간 삽입 및 삭제 1. 연결 리스트 연결 리스트(Linked List)는 메모리를 효율적으로 관리하기 위한 자료 구조로, 데이터와 다음 데이터를 가리키는 포인터로 구성된 노드(node)들의 모음. 배열은 메모리 상에 연속적으로 저장되지만, 연결 리스트는 각각의 노드가 메모리의 흩어진 공간에 존재하면서 다음 노드의 주소를 기억함으로써 연결. [1 | *] -> [2 | *] -> [3 | NULL] 각 노드는 두 개의 필드를 가진다데이터 값 (예: 1, 2, 3)다음 노드의 주소를 가리키는 포인터2. 배열과의 차이점 및 장단점 비교  1. 배열의 장점인덱스 기반으로 빠른 접근 가능메모리 캐싱 효율 높음..

목차배열 크기 조정이 어려운 이유메모리 재할당의 기본 원리malloc과 수동 복사 방식realloc을 이용한 재할당임시 메모리를 새로 할당하는 이유 1. 배열 크기 조정이 어려운 이유C 언어에서 배열은 한번 선언하면 크기 변경 불가. int arr[3];위처럼 선언하면, 이 배열은 정확히 3칸만 사용 가능.그 이유는 메모리 공간이 연속적으로 배정되기 때문.만약 그 옆 공간에 이미 다른 데이터가 존재하면 배열을 확장 불가능.즉, 기존 공간을 확장하는 것이 아니라 새로운 공간에 복사해야 한다.  2. 메모리 재할당의 기본 원리 2-1. 배열 크기를 늘리기 위한 일반적 방식새로운 메모리 공간을 malloc으로 할당기존 배열의 데이터를 for 루프로 복사기존 배열 메모리를 free포인터를 새로운 배열로 이동 이..

목차사용자 입력 함수 직접 구현 (get_int, get_string, get_long, get_float, get_char)파일 쓰기 (fopen, fprintf, fclose)파일 읽기와 JPEG 파일 판별다양한 파일 형식의 식별 방식메모리 영역을 나누는 이유 1. 사용자 입력 함수 직접 구현 1-1. get_int 구현 방식#include int main(void) { int x; printf("x: "); scanf("%i", &x); printf("x: %i\n", x);}scanf를 통해 정수 입력 받음.주소 연산자 & 필수. 1-2. get_string 구현 방식#include int main(void) { char s[5]; printf("s: "); ..

목차값 교환의 문제와 원인함수 호출 시 복사되는 값메모리 영역 구조: 스택, 힙, 등포인터를 이용한 교환메모리 영역을 나누는 이유  1. 값 교환의 문제와 원인  두 정수 값을 교환하려는 코드 예시#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;}  출력x is 1, y is 2x is 1, y is 2겉보기에 swap() 함수는 a, b의 값..

목차메모리 동적 할당메모리 누수  (Memory Leak) 버퍼 오버플로우 (Buffer Overflow)메모리 해제 방법 및 free 함수Valgrind를 통한 메모리 오류 검사제한된 메모리 환경에서 해제하지 않았을 때 발생할 수 있는 문제  1. 메모리 동적 할당 프로그램 실행 중에 필요한 만큼 메모리를 직접 할당할 수 있는 기능을 동적 메모리 할당이라고 한다.C 언어에서는 malloc 함수를 이용해 특정 크기의 메모리를 요청 가능.  int *x = malloc(10 * sizeof(int)); 위 코드는 int형(4바이트) 변수 10개를 저장할 수 있는 메모리(총 40바이트)를 힙 영역에 동적으로 할당.할당된 메모리의 시작 주소가 포인터 x에 저장.  2. 메모리 누수  (Memory Leak) ..

목차1. 문자열 복사 (String Copy)2. 문자열 복사 문제3. 문자열을 안전하게 복사하는 방법4. 문자열 주소만 복사했을 때 발생하는 문제   1. 문자열 복사 (String Copy)단순히 변수에 문자열을 대입하는 것과 메모리를 할당하여 복사하는 것은 다르게 동작하므로, 그 차이를 이해하는 것이 중요하다.  2. 문자열 복사 문제 #include #include #include int main(void){ string s = get_string("s: "); string t = s; t[0] = toupper(t[0]); printf("s: %s\n", s); printf("t: %s\n", t);}이 코드에서 s에 문자열을 입력받고, t에 s를 할당했다. 그다음 t..

목차1. 문자열의 저장 방식2. 문자열 비교3. 문자열 비교의 핵심4. 추가 개념: string 자료형의 장점   1. 문자열의 저장 방식C에서 문자열은 문자들의 배열로 저장. 문자열의 시작 주소를 가리키는 포인터 변수를 사용하여 문자열을 저장 가능.#include int main(void){ char *s = "EMMA"; printf("%p\n", s); // 문자열의 첫 문자 'E'가 저장된 주소 출력}이 코드에서 s는 "EMMA" 문자열의 첫 번째 문자 'E'의 주소를 가리키는 포인터.각 문자들은 메모리에서 연속적으로 저장되며, &s[0], &s[1], &s[2], &s[3]은 각각 'E', 'M', 'M', 'A'의 주소를 의미. printf("%p\n", &s[0]); // 'E'의..