[정글] c언어 특강

오늘 c언어 특강에서 들은 내용 간단 정리

각 주제에 대해 자세하게 설명하기보다는 공부할 때 한 번 생각해볼만한 것들을 던져주신 것 같다.

재귀 구현

하노이탑 문제 

점화식 : h(n) = 2*h(n-1) + 1

 

n개의 원판을 움직이기 위해서는

1) n-1개의 원판을 1번 기둥에서 2번 기둥으로 옮기고

2) 가장 큰 1개의 원판을 1번 기둥에서 3번 기둥으로 옮기고

3) 다시 n-1개의 원판을 2번 기둥에서 3번 기둥으로 옮기는

과정이 필요하기 때문

이진 트리의 노드 개수를 구하는 문제

참고) 트리 vs 그래프?

트리는 사이클이 없고 모든 노드가 연결되어있는 그래프

 

점화식 : count(t) = count(t->left) + count(t->right) + 1

struct{
	struct* node left;
    struct* node right;
}node;

countNode(struct node* root){
	if(root==NULL) return 0;
    return countNode(root->right) + countNode(root->left) + 1
}

 

이렇게 트리를 탐색할 때 재귀를 사용해야 간단히 점화식으로 탐색할 수 있음

재귀를 쓰지 않으면 bfs, dfs로 전, 중, 후위 순회를 구현해야 하는데 굉장히 어려움

-> 재귀를 쓰는 이유를 잘 생각해보기

 

포인터

int main(){
	//선언(declaration)
	char* p;
    int a;
    
    //연산(statement)
    &a;
    *p;
    
    printf("%d", sizeof(p)); //8 출력
}

int가 a의 타입이듯

char* 자체가 p에 대한 타입 (char형 포인터 타입)

 

&와 *는 단항 연산자

&는 int 타입 변수 a의 주소, *는 포인터 타입 변수 p의 값을 가져오는 연산

 

sizeof()는 변수의 크기를 byte수로 리턴하는 함수

 

참고) 32bit OS application에서는 데이터의 주소를 2^32bit 크기로 표현함

따라서 데이터 하나를 표현하려면 2^32bit 즉 4byte짜리 공간이 필요함

 

Big Endian, Little Endian

Big Endian : network 상에서 tcp/ip로 데이터를 주고받을 때 데이터를 저장하는 방법

Little Endian : 대부분의 amd cpu 상에서 쓰는 방식

 

c언어는 Call By Value만 사용

int main(){
    int change(int* a){
        *a = *a + 1;
        return *a;
    }

    int a = 0;
    change(&a);
}

c언어는 항상 call by value로 동작

-> 인자로 받은 값이 항상 스택 상에 복사되고 그 복사된 값을 사용해서 함수가 실행됨

 

이 때 인자로 포인터를 넘겨주면 원본 데이터의 주소를 참조할 수 있게 되므로

call by value에 의해 복사된 값을 사용하더라도 원본 데이터를 변경 가능

 

이처럼 c언어에서는 함수 인자로 포인터를 넘겨주어 call by reference'처럼' 동작할 수 있음

복사된 값을 사용한다는 것은 변함 없다는 점을 기억하기

 

Operator overloading

int* a = 0;
int b = 0;
char** c = 0;

++a;
++b;
++c;

printf("%d, %d, %d", a, b, c); //4 1 8

a, b, c는 타입이 모두 다름

a는 int형 포인터, b는 int, c는 문자열 포인터

 

그리고 세 변수에 똑같이 전위 증가 연산자를 적용함

출력해보면 결과가 4 1 8로 다름

 

-> 연산자의 동작이 피연산자의 타입에 따라 달라질 수 있다

참고로 ++연산의 피연산자 타입이 포인터이면 그 타입이 역참조하는 타입의 크기 만큼 뒤에 있는 곳으로 점프함

 

배열과 포인터

c언어에서 배열은 포인터임

배열 = (0번째 인덱스의 데이터를 가리키고 있는 포인터)+(배열에 저장될 데이터의 개수, 크기)

이 두 가지만 알고 있으면 되므로 

 

0번째 인덱스를 가리키고 있는 포인터를 1씩 증가시키면서 값을 넣으면 배열과 같이 쓸 수 있음

 

메모리 구조

 

c언어서 함수 밖에 static으로 선언한 변수, 함수 내에 선언한 local 변수, char* a = "abc" 등의 데이터가

메모리의 어떤 공간에 쌓이는지 알아보기

 

참고) %s -> 시작 주소부터 NULL이 나올 때까지 그 곳에 저장된 값을 출력함

 

이중 포인터

int** a = (int**)0x1;
int* b = (int*)0x1;

printf("%d", sizeof(*a)); //8
printf("%d", sizeof(*b)); //4

이중 포인터는 역참조 했을 때의 값이 int냐 *int냐의 차이임

 

https://www.scaler.com/topics/size-of-a-pointer-in-c/

What is the Size of a Pointer in C? - Scaler Topics

https://medium.com/huawei-developers/stack-vs-heap-understanding-memory-allocation-in-programming-a83a54901416

Stack vs Heap: Understanding Memory Allocation in Programming

https://m.blog.naver.com/nsj6646/221486028315

[C언어] 포인터의 역참조(dereference)

https://www.reddit.com/r/C_Programming/comments/xwx8p4/why_is_everything_in_c_call_by_value/

From the C_Programming community on Reddit

https://captainlink.medium.com/what-is-little-endian-and-big-endian-byte-ordering-3768c065f45e

What Is Little-Endian And Big-Endian Byte Ordering?