0. Introduction of Data Structure
- 자료구조란?
- 자료구조(Data Structure) : 자료(data)를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법.
- 자료(data)
- 질적(qualitive)또는 양적(quantative)값의 집합으로 구성된 의미 단위.
- 자료를 의미 있게 정리한 것이 정보(information)
- 자료구조와 알고리즘
- 알고리즘(algorithm) : 문제를 해결하기 위한 동작들의 유한한 순열.
- 알고리즘이 잘 동작하려면, 자료를 효율적으로 처리해야 함 -> 알고리즘에는 좋은 자료구조가 필요
- 자료를 효율적으로 처리하려면, 효율적인 알고리즘이 필요 -> 자료구조에는 좋은 알고리즘이 필요
- 즉, 알고리즘 <-> 자료구조
- Algorithms + Data Structures = Programs
- 자료구조를 배워야 하는 이유
- 모-든 분야의 기초지식
- 알고리즘, 운영체제, 네트워크, 데이터베이스, PL, 그래픽 프로그래밍, 통계학, 보안, AI, ...
- 좋은 자료구조를 사용하는 것 -> 좋은 프로그램을 만드는 것 -> 좋은 개발자가 되는 것
- 좋은 프로그래머와 나쁜 프로그래머의 차이는, 코드와 자료구조중 어느 쪽을 더 신경쓰냐는 것이다. 나쁜 프로그래머는 코드에 신경쓰고, 좋은 프로그래머는 자료구조와 그 관계에 대해 신경쓴다. - 리누스 토르발즈https://lwn.net/Articles/193245/
1. Pre-Requirements for Data Structure
- c언어 기초지식(c언어 마무리)
- 포인터, 동적 메모리 할당
- *, & 연산자
- void 포인터
- 배열과 포인터
- address
[num] == *(address + num)
- void* malloc(size_t);
- void* calloc(size_t, size_t);
- void free(void*);
- 함수 포인터
- 구조체, 공용체, 열거형(struct, union, enum)
- typedef
typedef type new_typename
typedef struct {/**/} struct_name
- realloc, memset, memcpy
void* realloc(void*, size_t);
void* memset(void*, int, size_t);
void* memcpy(void*, const void*, size_t);
- 자료구조/알고리즘 기초 지식
- 계산복잡도(complexity)
- 시간 복잡도(time complexity), 공간 복잡도(space complexity)
- big-O 표현법(big-O notation)