MINJU's code story

[ 메모리 안에서 데이터가 저장되는 영역 ]

- 컴파일된 바이너리

- 전역변수

- malloc으로 할당된 메모리의 데이터

- 프로그램 내 함수와 관련된 데이터 (main데이터 포함)

[ swap 함수가 먹히지 않는 이유 ]

#include <stdio.h>

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 함수 -> 실행 후 해당 메모리 할당 종료 -> 여전히 main의 x,y에는 영향을 주지 않음

main 함수

[ 포인터를 사용 ]

#include <stdio.h>

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);
    
    //x와 y의 주소를 전달
    swap(&x, &y);
    printf("x is %i, y is %i\n", x, y);
}

void swap(int *a, int *b)
{
    int tmp = *a;	//Go to the address in a. 
    			//It will lead you to x. 
    			//Put what's in x in tmp, which is 1.
    *a = *b;		
    *b = tmp;
}

x,y가 가리키는 주소를 포인터로 바꿔줌으로써 해결 가능

1. 16진수

0 1 2 3 4 5 6 7 8 9 A B C D E F

16진수 앞에는 10진수 등과 구분하기 위해 숫자 앞에 0x를 붙인다.

255 = 0xff

65 = 0x41

2. 메모리 주소

int n에 50이라는 값을 저장하고 출력 => 아래 그림과 같이 컴퓨터 메모리 어딘가에 4바이트 만큼의 자리를 차지하며 저장되어 있을 것. 

C에서는 변수의 메모리상 주소를 받기 위해 ‘&’이라는 연산자를 사용.

#include <stdio.h>

int main(void)
{
    int n = 50;
    printf("%p\n", &n);
}

예를 들어, 위와 같은 코드를 실행하면 ‘0x7ffe00b3adbc’와 같은 값을 얻을 수 있고, 이는 변수 n의  16진법으로 표현된 메모리의 주소.

‘*’를 사용하면 그 메모리 주소에 있는 실제 값을 얻을 수 있음.

#include <stdio.h>

int main(void)
{
    int n = 50;
    printf("%i\n", *&n);
}

위 코드는 먼저 n의 주소를 얻고, 또 다시 그 주소에 해당하는 값을 얻어와 출력한 것이므로 결국 ‘50’이라는 값이 출력.

3. 포인터

#include <stdio.h>

int main(void)
{
   int n = 50;
   int *p = &n;
   printf("%p\n", p);
   printf("%i\n", *p);
}

• int *p 에서 p앞의 *는 이 변수가 포인터라는 의미, int 는 이 포인터가 int 타입의 변수를 가리킨다는 의미.
• int *p = &n : int n의 주소를 int 타입으로 *p에 저장.
• 만약 int p = &n 이라고 p가 포인터임을 명시하지 않으면 컴파일 에러 발생. 주소는 오직 포인터에만 저장 가능.
• 첫 번째 printf문: 포인터 p의 값, 즉 변수 n의 주소를 출력.
• 두 번째 printft문: 포인터 p가 가리키는 변수의 값, 즉 변수 n의 값을 출력.

🔑 정리하기

& : What's the address?

* : Go to the address.

www.boostcourse.org/cs112

1. 버블 정렬

두 개의 인접한 자료 값을 비교하면서 위치를 교환. O(n^2), Ω(n)

2. 선택 정렬

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식. θ(n^2)

3. 병합 정렬

원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식. θ(n log n)

www.boostcourse.org/cs112

#

##

###

####

1. 중첩루프

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    // 사용자로부터 피라미드의 높이를 입력 받아 저장
    int height = get_int("Height: ");

    // 피라미드 그리기
    draw(height);
}

void draw(int h)
{
    // 높이가 h인 피라미드 그리기
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

2. 재귀(Recursion): 함수가 본인 스스로를 호출해서 사용

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}

void draw(int h)
{
    // 높이가 0이라면 (그릴 필요가 없다면)
    if (h == 0)
    {
        return;
    }

    // 높이가 h-1인 피라미드 그리기
    draw(h - 1);

    // 피라미드에서 폭이 h인 한 층 그리기
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

www.boostcourse.org/cs112

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

위 코드의 경우 names와 numbers 안의 순서가 바뀌면 각 이름에 해당하는 전화번호가 뒤죽박죽이 됨.

아래는 구조체를 사용해서 묶음을 이룬 것.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// 구조체 생성
typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[4];

    people[0].name = "EMMA";
    people[0].number = "617–555–0100";
    people[1].name = "RODRIGO";
    people[1].number = "617–555–0101";
    people[2].name = "BRIAN";
    people[2].number = "617–555–0102";
    people[3].name = "DAVID";
    people[3].number = "617–555–0103";

    // EMMA 검색
    for (int i = 0; i < 4; i++)
    {
        if (strcmp(people[i].name, "EMMA") == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

www.boostcourse.org/cs112

1. Big O

O: "on the order of", "~만큼 커지는"

O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있음.

• O(n^2) - 버블 정렬(bubble sort), 선택 정렬(selection sort)
• O(n log n) - 병합 정렬(merge sort)
• O(n) - 선형 검색(linear search)
• O(log n) - 이진 검색(binary search)
• O(1)

(선형 검색은 정확하지만 비효율적. But, 자료가 정렬되어있지 않을 때는 유용함.)

2. Big Ω

Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것.

예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1).

• Ω(n^2) - 선택 정렬
• Ω(n log n) - 병합 정렬
• Ω(n) - 배열 안에 존재하는 값의 개수 세기, 버블 정렬
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

3. Big θ

Big O = Big Ω 일 때, Big Theta라고 한다.

• θ(n^2) - 선택 정렬
• θ(n log n) - 병합 정렬
• θ(n)
• θ(log n)
• θ(1)

www.boostcourse.org/cs112

1. 컴파일링의 네 단계

#include <cs50.h>
#include <stdio.h>

int main(void)
{
	string name = get_string("What's your name?");
	printf("Hello, %s\n", name);
}

전처리(Precompile)

# 으로 시작되는 C 소스 코드는 전처리기에게 실질적인 컴파일이 이루어지기 전에 무언가를 실행하라고 알려줍니다. 예를 들어, #include는 전처리기에게 다른 파일의 내용을 포함시키라고 알려줍니다. 

컴파일(Compile)

컴파일러라고 불리는 프로그램은 C 코드를 어셈블리어라는 저수준 프로그래밍 언어로 컴파일합니다. C 코드를 어셈블리 코드로 변환시켜줌으로써 컴파일러는 컴퓨터가 이해할 수 있는 언어와 최대한 가까운 프로그램으로 만들어 줍니다. 컴파일이라는 용어는 소스 코드에서 오브젝트 코드로 변환하는 전체 과정을 통틀어 일컫기도 하지만, 구체적으로 전처리한 소스 코드를 어셈블리 코드로 변환시키는 단계를 말하기도 합니다.

어셈블(Assemble)

소스 코드가 어셈블리 코드로 변환되면, 다음 단계인 어셈블 단계로 어셈블리 코드를 오브젝트 코드로 변환시키는 것입니다. 컴퓨터의 중앙처리장치가 프로그램을 어떻게 수행해야 하는지 알 수 있는 명령어 형태인 연속된 0과 1들로 바꿔주는 작업이죠. 이 변환작업은 어셈블러라는 프로그램이 수행합니다. 소스 코드에서 오브젝트 코드로 컴파일 되어야 할 파일이 딱 한 개라면, 컴파일 작업은 여기서 끝이 납니다. 그러나 그렇지 않은 경우에는 링크라 불리는 단계가 추가됩니다.

링크(Link)

만약 프로그램이 (cs50.h와 같은 라이브러리를 포함해) 여러 개의 파일로 이루어져 있어 하나의 오브젝트 파일로 합쳐져야 한다면 링크라는 컴파일의 마지막 단계가 필요합니다. 링커는 여러 개의 다른 오브젝트 코드 파일을 실행 가능한 하나의 오브젝트 코드 파일로 합쳐줍니다. 

이 네 단계를 거치면 최종적으로 실행 가능한 파일이 완성됩니다.

www.boostcourse.org/cs112

의사 코드 (Pseudo code)

컴퓨터가 수행할 작업을 프로그램 언어가 아니라 사람이 사용하는 언어로 알고리즘의 논리적 절차를 작성한 코드.

Overflow

컴퓨터 하드웨어의 한계로 인해 발생하는 문제 중 하나로, 변수가 담을 수 있는 최대 허용 범위를 벗어난 값을 저장해 예상치 못한 결과가 나오는 현상.

#include <stdio.h>

int main(void)
{
    printf("hello, world\n");
}

#include <stdio.h>

stdio.h라는 이름의 파일 추가하기

(Standard Input/Output library)

int main(void)

시작한다

clang

c language compiler

ex.

$clang hello.c

hello.c 파일을 컴파일하시오.

$clang -o hello hello.c -lcs50

hello.c 파일을 hello라는 이름으로 컴파일하고 cs50과 link(연결)하시오.

위 코드는 아래와 같이 간단히 될 수 있음

$make hello

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string answer = get_string("What's your name?");
    printf("hello, %s\n", answer);
}

1. 형식 지정자

• %c : char
• %f : float, double
• %i : int
• %li : long
• %s : string

2. 사용자 정의 함수

#include <stdio.h>

// prototype
void cough(void);

int main(void)
{
    for (int i = 0; i < 3; i++)
    {
        cough();
    }
}

void cough(void)
{
    printf("cough\n");
}

void cough(void);

첫번째 void: output 형식 미지정

두번째 void: input 형식 미지정

C는 순서대로 코드 읽기 때문에 사용자 정의 함수를 뒤에만 두면 main의 cough()함수를 인식하지 못하고 에러 발생.

그래서 main함수 앞에 간단하게라도 언급해줘야 함.

(참고로 main이 위로 오게 하는 것이 좋은 코드 디자인.)

www.boostcourse.org/cs112