[WEEK04] 정글 5기 - 탐험준비 - C언어, 자료구조, 알고리즘

1. 포인터

포인터란?	- C언어는 메모리에 접근해서 우리가 원하는 방식으로 데이터를 사용할 수 있게 해주는 언어이다. - 변수를 사용해 메모리에 접근하려면 변수 선언으로 메모리에 공간을 확보하고, 그곳을 데이터를 넣고 꺼내 쓰는 공간으로 사용한다. - 이 때 변수 대신 메모리의 주소 값을 이요해 메모리에 접근하는 것이 포인터다.
포인터를 사용하는 이유	- 포인터를 사용하면 사용 범위를 벗어난 경우에도 데이터를 공유할 수 있다. - 하지만 포인터를 사용하려면 추가적인 변수 선언이 필요하고 주소 연산, 간접 참조 연산 등 각종 연산을 수행해야 한다. - 굳이 힘들게 포인터를 일부러 즐겨 사용할 필요는 없다.   - 하지만, 임베디드 프로그래밍을 할 때 메모리에 직접 접근하는 경우나 동적 할당한 메모리를 사용하는 경우에는 포인터가 반드시 필요하다.
포인터 사용 시 주의점	- 포인터 변수 선언시 초기화하기     · 포인터 선언 후 초기화를 하지 않는다면 쓰레기값 존재 - NULL 포인터의 사용     · 포인터가 아무것도 가리키지 않을 때 NULL 설정     · NULL은 헤더 파일 stdio.h에 0으로 정의     · 주소 0은 CPU가 사용하는 영역이어서 일반 프로그램은 주소 0에 접근할 없기에 안전성이 높다 - 포인터 자료형과 변수의 자료형 일치     · 만약 포인터의 자료형이 변수의 자료형보다 크다면, 포인터를 통해 변수의 주소를 통해 쓰게 될 경우.       변수의 범위가 넘어가서 이웃 바이트를 덮어쓰게 되어 문제가 생길 수 있다. - 절대 주소 사용 금지     · 절대 주소는 아두이노와 같은 임베디드 시스템에만 사용     · 그 이유는 PC는 윈도우와 같은 운영체제가 프로그램을 관리하기 때문에 프로그래머가 사용하고자 하는 주소가        어떠한 용도로 사용되는지 모른다.     · 실행할 때마다 할당되는 주소가 다르기에 절대 주소를 사용하면 안된다.

 

ex01)

#include <stdio.h>

void swap(int *num1, int *num2) {
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

int main() {
    int num1 = 10;
    int num2 = 20;

    printf("num1의 값 : %d\n", num1);
    printf("num2의 값 : %d\n", num2);

    swap(&num1, &num2);
    printf("\nSwap함수 실행 후\n\n");
    
    printf("num1의 값 : %d\n", num1);
    printf("num2의 값 : %d\n", num2);
}

 

2. 가상화

가상화란?	- 가상화는 하나의 실물 컴퓨팅 자원을 마치 여러 개인 것처럼 가상으로 쪼개서 사용하거나, 여러 개의 실물 컴퓨팅 자원들을 묶어서 하나의 자원인 것처럼 사용하겠다는 것이다. - 이때 컴퓨팅 자원(리소스)이란, CPU, 메모리, 스토리지, 네트워크 등 컴퓨터를 구성하는 요소들을 말한다. - 가상화를 관리하는 소프트웨어(주로 Hypervisor)를 사용하여 하나의 물리적 머신에서 가상 머신(VM)을 만드는 프로세스
Hypervisor란?	- 가상화 층을 구현하여 물리적 머신의 컴퓨팅 리소스로부터 가상 환경을 분리하고 가상 머신(VM)을 생성 - VM은 물리적 머신과 동일한 역할 및 성능을 수행하지만, cpu와 메모리 및 스토리지와 같은 물리적 머신의 컴퓨팅 리소스를 사용한다. - Hypervisor는 필요에 따라 각 VM에 이러한 컴퓨팅 리소스를 할당한다 - 최근에는 Docker와 같은 컨테이너 가상화 기술이 등장하기도 했다. - 도커를 윈도우에서 사용하는 경우에는 Hypervisor를 사용하지만, 리눅스에서 사용하는 상황에서는 커널의 특징을 이용하기 때문에 Hypervisor를 사용하지 않는다고 한다.
가상화의 장점	1. Server Consolidation   : 물리적인 서버의 개수를 줄여 1개의 서버로 통합함으로써 서버의 전력 및 냉각 비용, 하드웨어 공간 비용 등을 감소 2. Isolation   : 기능에 맞게 여러 개의 머신으로 분리하여 Failures나 Security Leaks 등에 더욱 잘 대처 가능 3. Efficiency   : 컴퓨팅 자원의 사용을 최대화하고 보다 쉽게 관리 가능 4. Flexibility   : 한 서버의 데이터를 마이그레이션하기에 용이
가상화의 유형	- 데스크탑 가상화 - 네트워크 가상화 - 스토리지 가상화 - 데이터 가상화 - 애플리케이션 가상화 - 데이터 센서 가상화 - CPU 가상화 - GPU 가상화 - Linux 가상화 - 클라우드 가상화

 

3. GCC

GCC란?	- GCC는 GNU 컴파일러 모음(GNU Compiler Collection)의 약자이다. - GNU 프로젝트의 일환으로 개발되어 널리 쓰이고 있는 컴파일러이다.
GNU란?	- GNU는 GNU's not UNIX의 재귀 약자로, 리처드 스톨먼이 각종 자유 소프트웨어들이 돌아가고 번영할 수 있는 기반 생태계를 구축하기 위해 시작한 프로젝트이다.
컴파일러란?	- 컴파일(Complie)은 어떤 언어의 코드를 다른 언어로 바꿔주는 과정 - 예를 들어, 사람이 인식하고 이해할 수 있는 C언어 코드를 컴퓨터가 이해할 수 있는 기계어로 바꿔주는 것이다. - 즉, 컴파일러(Compiler)는 어떤 프로그래밍 언어로 쓰여진 소스 파일을 다른 언어로 바꿔주는 번역기다.

 

소스 코드가 실행 파일이 되는 과정
- 소스코드를 실행 파일로 만들기 위해 네 가지 단계를 거친다.     · 전처리 단계     · 컴파일 단계     · 어셈블 단계     · 링크 단계 - gcc hello.c 명령어를 입력하면 네 가지 단계를 거쳐서 실행 파일이 생성되지만, 각 단계의 파일들은 임시 파일로 생성되었다가 사라진다.
1. 전처리 단계	- 전처리기가 소스 파일 내의 전처리기 지시자를 처리한다. * 전처리기 지시자     · #으로 시작하고 세미콜론 없이 개행문자로 종료되는 라인을 의미     · #include : 지정된 특정 파일의 내용을 해당 지시자가 있는 위치에 삽입     · #define : 매크로 함수 및 상수 정의에 사용한다. 코드 내의 해당 상수를 프로그래머가 정의한 문자열로 대체한다. - 전처리 단계를 거치면 소스 파일 hello.c에서 확장 소스 파일인 hello.i가 생성
2. 컴파일 단계	- 전처리된 파일인 hello.i 로부터 어셈블리어로 된 파일인 hello.s 파일을 생성한다. * 어셈블리어란?     · 기계어보다 한 단계 위에 있는 언어이며, 기계어와 함께 단 두 가지  뿐인 저급 언어에 속한다.     · 기계어는 컴퓨터 관점에서 바로 읽을 수 있지만, 인간이 사용하기 불편한 언어이기 때문에 이를 보완하기 등장한 것이       어셈블리어이다.
3. 어셈블 단계	- 어셈블리어 파일 hello.s를 기계어로 된 오브젝트 파일 hello.o파일로 변환한다.     · 즉, 컴퓨터가 읽을 수 있는 0과 1로 이루어진 2진수 코드로 변환하는 것이다.
4. 링크 단계	- 링크 단계는 작성한 프로그램이 사용하는 다른 프로그램이나 라이브러리를 가져와서 연결하는 과정이다 - 그 결과로 실행 가능한 파일을 생성한다. (hello.o → hello)

 

GCC 컴파일 옵션
-o [파일명] [*.c]	- 지정한 파일명으로 실행 파일을 저장한다. - ex) gcc -o result.out main.c
-E	- 전처리 단계를 수행한 후, 컴파일 과정을 거치지 않는다. - 실행 결과는 standard output에 출력된다.
-S	- 컴파일 단계를 수행한 후, 어셈블 과정을 거치지 않는다. - 실행 결과로 어셈블리어로 변환된 *.s 파일이 생성된다.
-c [파일명] [*.c]	- 소스 코드를 컴파일 또는 어셈블하며, 링크하지 않는다. - 파일명으로 오브젝트 파일을 생성한다. - ex) gcc -c ft_isalnum.c
-I(아이 대문자) [디렉토리명]	- 디렉토리명에서 헤더 파일을 검색한다.
-l(엘 소문자) [라이브러리]	- 라이브러리 파일과 링크한다. - 접미사나 확장(.a/.o)가 없어도 링크한다. - ex) 라이브러리 파일이 libmath.a 일 때 다음과 같이 작성     · gcc myfile.c -lmath -o myfile
-L [디렉토리명]	- 디렉토리 내에서 라이브러리 파일을 찾는다.
-D [매크로상수명]=[값]	- 매크로 상수를 정의하기 위한 옵션이다. - ex) gcc -D BUFFER_SIZE=42     · BUFFER_SIZE 라는 매크로 상수의 값을 42로 설정한다.
-c	- 옵션은 링크를 하지 않고 컴파일만 진행한다. - 이 옵션을 생략하면 main 함수를 찾을 수 없다는 오류가 출력된다.

 

4. 포인터 연산

포인터 연산이란?

- 포인터는 값을 증가시키거나 감소시키는 등의 제한된 연산만 할 수 있다. - C언어의 포인터 연산의 규칙     · 1. 포인터끼리의 덧셈, 곱셈, 나눗셈은 아무런 의미가 없다.     · 2. 포인터끼리의 뺄셈은 두 포인터 사이의 상대적 거리를 나타낸다.     · 3. 포인터에 정수를 더하거나 뺄 수 있지만, 실수와의 연산은 허용하지 않는다.     · 4. 포인터끼리 대입하거나 비교할 수 있다.

 

ex01)

// 포인터 연산의 증가값을 비교하는 예제
char* ptr_char = 0;
int* ptr_int = NULL;
double* ptr_double = 0x00;  

printf("포인터 ptr_char가 현재 가리키고 있는 주소값은 %#x입니다.\n", ptr_char);
printf("포인터 ptr_int가 현재 가리키고 있는 주소값은 %#x입니다.\n", ptr_int);
printf("포인터 ptr_double이 현재 가리키고 있는 주소값은 %#x입니다.\n", ptr_double);  

printf("포인터 ptr_char가 1 증가 후에 가리키고 있는 주소값은 %#x입니다.\n", ++ptr_char);
printf("포인터 ptr_int가 1 증가 후에 가리키고 있는 주소값은 %#x입니다.\n", ++ptr_int);
printf("포인터 ptr_double이 1 증가 후에 가리키고 있는 주소값은 %#x입니다.\n", ++ptr_double);

// 포인터   ptr_char가 현재 가리키고 있는 주소값은 0입니다.
// 포인터   ptr_int가 현재 가리키고 있는 주소값은 0입니다.
// 포인터   ptr_double이 현재 가리키고 있는 주소값은 0입니다.
// 포인터   ptr_char가 1 증가 후에 가리키고 있는 주소값은 0x1입니다.
// 포인터   ptr_int가 1 증가 후에 가리키고 있는 주소값은 0x4입니다.
// 포인터   ptr_double이 1 증가 후에 가리키고 있는 주소값은 0x8입니다.

// ========================================================================
// 포인터끼리의 비교 연산과 대입 연산
int num01 = 10;
int num02 = 20;
int *ptr_num01 = &num01;
int *ptr_num02 = &num02;  

if (ptr_num01 != ptr_num02) // 포인터끼리의 비교 연산
{
    printf("포인터 ptr_num01이 가리키고 있는 주소에 저장된 값은 %d입니다.\n", *ptr_num01);
    printf("포인터 ptr_num02가 가리키고 있는 주소에 저장된 값은 %d입니다.\n", *ptr_num02);
    printf("포인터 ptr_num01과 ptr_num02는 현재 다른 주소를 가리키고 있습니다.\n\n");
    ptr_num02 = ptr_num01; // 포인터끼리의 대입 연산
}  

printf("포인터 ptr_num01이 가리키고 있는 주소에 저장된 값은 %d입니다.\n", *ptr_num01);
printf("포인터 ptr_num02가 가리키고 있는 주소에 저장된 값은 %d입니다.\n", *ptr_num02);  

if (ptr_num01 == ptr_num02) // 포인터끼리의 비교 연산
{
    printf("포인터 ptr_num01과 ptr_num02는 현재 같은 주소를 가리키고 있습니다.\n");
}

// 포인터 ptr_num01이 가리키고 있는 주소에 저장된 값은 10입니다.
// 포인터 ptr_num02가 가리키고 있는 주소에 저장된 값은 20입니다.
// 포인터 ptr_num01과 ptr_num02는 현재 다른 주소를 가리키고 있습니다. 

// 포인터 ptr_num01이 가리키고 있는 주소에 저장된 값은 10입니다.
// 포인터 ptr_num02가 가리키고 있는 주소에 저장된 값은 10입니다.
// 포인터 ptr_num01과 ptr_num02는 현재 같은 주소를 가리키고 있습니다.

 

*(++ptr) = 20;	*(ptr + 1) = 20;
- 이 코드는 'ptr'이 가리키는 메모리 주소를 1 증가시킨 후 해당 주소에 20을 할당 - 즉, 포인터 'ptr'이 현재 가리키고 있는 메모리 주소를 증가시킨 다음 그 주소에 20을 할당 - 즉, 포인터를 증가시킨 다음 해당 위치에 값을 할당	- 이 코드는 'ptr'이 가리키는 메모리 주소에 1을 더한 주소에 20을 할당 - 이때, 'ptr'은 증가하지 않고 그대로 둔다. - 따라서 현재 'ptr'이 가리키는 주소의 다음 주소에 20을 할당한다. - 즉, 현재 포인터를 가리키는 위치에서 오프셋을 적용하여 값을 할당

 

5. 동적 메모리 할당

정적 할당 (static allocation)	- 프로그램이 실행되기 위해서는 메모리가 필요하다.     · 컴파일러는 컴파일 시점에 소스 코드를 읽고, 변수 타입들의 크기에 따라 메모리를 할당한다. - 프로그램이 실행되기 전, 컴파일 시점에 소스 코드를 읽고 메모리 공간을 확보하는 것이 정적 할당이다.
동적 메모리 할당 (Dynamic Memory Allocation)	- 동적 메모리 할당이란 컴퓨터 프로그래밍에서 실행 중(런타임)에 사용할 메모리 공간을 할당하는 것     · 컴파일 타임이 아닌 프로그램이 실행되는 중인 런타임에 필요한 만큼의 메모리 공간을 확보
동적 할당이 필요한 이유	- 시점마다 필요한 만큼만 메모리 공간을 확보하고, 다 사용했다면 free 시켜줌으로써 메모리 공간을 해제함으로서 한정된 메모리 공간을 효율적으로 사용할 수 있게 되는 것이다. - 이는 함수가 종료되거나 변수의 영역을 벗어나면 자동으로 메모리 해제가 이루어지는 스택과는 다르다     · 동적 할당은 스택이 아닌 힙에서 일어난다.
힙(heap) 영역	- 힙(heap)이란 C언어나 자바와 같은 프로그래밍 환경에서 원시 자료형(primitive type)이 아닌 보다 큰 크기의 데이터를 담고자 동적으로 할당하는 메모리 공간을 지칭한다. - 정리하자면 C언어에서 말하는 동적 할당은 힙 영역에 필요할 때마다 메모리 공간을 할당하고, 더 이상 필요하지 않을 경우 메모리를 해제해주는 과정을 의미한다. - 장점     · 상황에 따라 원하는 크기 만큼의 메모리가 할당되므로 경제적이다. (malloc or calloc)     · 이미 할당된 메모리라도 언제든 크기를 조정할 수 있다(realloc) - 단점     · C언어의 경우 GC(Garbage Collector)가 없기 떄문에, 개발자가 직접 명시적으로       메모리를 해제해야 한다.(free)     · 만약 이를 하지 않았을 경우, 메모리 누수가 나타나고 이는 디버깅하기 매우 까다롭다.

 

6. malloc, calloc, realloc

메모리 할당	- malloc 또는 calloc을 호출하게 되면 힙 영역에 필요한 만큼의 메모리 공간을 확보하고 이후 반환 타입으로 해당 메모리 공간의 시작 위치를 포인터로 반환한다. - 또한 할당된 메모리를 어떤 목적에 사용할지 함수에서 판단하기 어렵기 때문에, return 타입은 void * 형을 return 하며, 반환 받는 쪽에서 타입 캐스팅을 통해 사용해야 한다.
malloc 과 calloc 의 차이	- 두 명령어 모두 똑같은 크기의 공간을 확보한다. - 두 명령어의 차이는 초기화 값에 그 차이가 있다. - malloc     · 매개변수로 입력한 크기 만큼을 그대로 할당하는 것     · 메모리 공간만 할당하므로, 초기화되지 않는 메모리 공간에는 쓰레기 값들이 들어있다. - calloc     · 두번째 매개변수의 크기를 첫번째 매개변수 갯수 만큼을 할당해 달라는 식으로 요청한다.     · 할당 후 해당 메모리 공간을 0으로 초기화한다. - 성능 자체는 초기화를 시키지 않는 malloc이 조금 더 낫다.     · 그러나 상황에 따라 초기화가 필요한 경우에는 calloc을 선택하는 것도 좋은 방법
메모리 해제	- 메모리 공간은 한정적이며, 더 이상 사용되지 않을 메모리 공간이라면 해당 메모리 공간을 할당 해제 해줌으로써 다른 프로그램이 해당 공간을 재활용할 수 있게 된다. - C언어에서 free함수를 이용해 특정 주소의 메모리 공간을 할당 해제 해줄 수 있다.
메모리 누수	- 메모리 누수란 동적으로 할당한 메모리가 할당 해제(free) 될 수 없는 상태가 된 것을 의미한다. - 메모리 누수가 반복되면 동적으로 할당된 메모리가 해제되지 못하고 계속 남아있게 되기 떄문에, 결국 시스템의 메모리가 부족해져 운영체제가 메모리 할당에 실패하여 프로그램을 종료시킨다. - 위와 같은 상황이라면, b는 결국 힙 영역에 해제되지 않고 계속 남아있게 된다.     · 이러한 상황을 바로 메모리 누수(Memory leak)라고 한다.
메모리 재할당	- 이미 할당되어 있는 메모리 공간의 크기를 변경하여 재할당하는 것을 의미 - 재할당은 realloc 함수를 이용해 메모리 공간 재할당이 가능하다. - 이를 해석해보면 ptr 위치에 해당하는 메모리 공간의 블록의 크기를 size로 조절한다는 의미가 된다. 1. ptr == NULL 일 경우     · 재할당을 위한 메모리 공간이 선언되어 있지 않는 것이므로, malloc 또는 calloc을 이용해        새로운 메모리 공간을 할당하는 것과 동일한 기능을 수행하게 된다. 2. size == 0 일 경우     · 현재 ptr 위치의 메모리 블록 크기를 0으로 만든다는 의미이므로, 이는 곳 해당 메모리 공간을        할당 해제 한다는 의미와 같다.     · 따라서 이는 free 함수를 호출하는 것과 동일한 기능을 수행ㅎ하게 된다. 3. ptr != NULL 일 경우     · 현재 ptr 위치는 할당되어 있는 메모리가 있고, 이 메모리 블록의 크기는 size로 변경하기 위한 동작을 수행한다.     · 기존에 ptr 다음 블록이 이어서 위치한 상태라면, ptr이 해당 위치에서 메모리 공간의 크기를 늘리는 것은        어렵기 때문에, 어쩔 수 없이 기존 ptr 블록의 내용을 유지한 채로 확장된 메모리 블록을 새로운 주소에 할당받게 된다.     · 재할당은 일반적으로 기존 블록 크기보다 크게 할당되는 것이 보편적이긴하다.     · 그러나 반대로 기존 블록보다 작게 할당되는 경우도 가능하다.     · 만약 기존의 8byte 크기만큼의 블록 4byte 만큼으로 축소시키려고 한다면,        재할당하는 4 byte 블록의 내용은 기존 8byte 블록의 4byte까지의 내용으로 채워지게 된다.

 

---

7. B Tree & 8. 위상정렬 & 9. Trie

 

10. KMP 알고리즘

 

11. 보이어-무어 알고리즘