[CS] CS50에서 배운 것 정리

1. C언어

사용자 정의 함수

// 사용자 정의 함수의 형태
출력형태 함수명(입력형태)

// 예
int main(void){
    float price = get_float("What's the price?\n");
    printf("Your total is %.2f\n",price*1.0625);
}

printf는 포맷출력 함수인데, 자료형과 placeholder를 맞춰쓰면 원하는 변수를 출력할 수 있다.
(파이썬의 .format()과 비슷하다)

%c 같은 placeholder 대신 %i를 넣고 (int)를 안 넣어도 되는데 넣으면 casting이 일어남

컴파일 방법

clang ~~  또는 make ~~

 

2. 배열

// 헤더파일이라고 한다.
// C로 작성된 함수를 불러온다.
#include <stdio.h>

컴파일 순서

preprocessing -> compiling -> assembling -> linking

컴파일링 과정이 따로 있긴 하지만 이 전체를 컴파일이라고 하기도 한다.

자료형

• bool: 불리언, 1바이트
• char: 문자, 1바이트
• int: 정수, 4바이트
• float: 실수, 4바이트
• long: (더 큰) 정수, 8바이트
• double: (더 큰) 실수, 8바이트

배열과 종단문자

문자열들이 메모리에 늘어져있는 경우, 각 문자열들을 구분하기 위해 하나의 문자열(배열)이 끝날 때 마다 \0이라는 종단문자(null terminating character)를 넣어줌. 그래서 실제 길이는 문자열 +1이다.

명령행 인자(command line argument)

int main(int argc, string argv[])

argc => arguement count, 입력의 개수
argv => arguement vector, 실제 입력들의 vector

// 왜 main은 return이 있을까?
실제로 0을 return을 돌려주기 때문이다.(문제가 없다면)

argv[0]에는 프로그램의 이름이 들어간다.

 

3. 알고리즘

표기법

Big-O와 Omega가 있는데, Big-O는 worst case를 가정하고 Omega는 best case를 가정한다.

버블정렬

가장 왼쪽부터 기준을 잡고 오른쪽으로 가면서 비교한다. 크면 둘의 위치를 swap한다.

(n-1) * (n-2) 이므로 복잡도는 N^2

선택정렬

0부터 n-1까지 가면서 가장 작은 애를 찾아 해당 iteration의 index로 넣는다. N^2이다.

병합정렬

왼쪽 정렬, 오른쪽 정렬, merge의 순서로 진행하는데 재귀적으로 재귀적으로 실행되기 때문에 가장 왼쪽의 원소부터 정렬된다. merge할 때는 left와 right의 index 0를 비교하면서 가장 작은 애를 하나씩 뒤에 붙여준다. 시간 복잡도는 n * logn이다.

4. 메모리

16진법

• 1,2,3,4,...,9,A,B,C,D,E,F을 사용
• 256개(0~255), 8비트, 32바이트
• 0x가 앞에 붙으면 16진법 수라는 것을 알 수 있음

int *p -> p라는 포인터가 가리키는 값이 int이다 선언

&n -> n의 메모리 주소

• 메모리에서 서로를 참고하게끔 만들어 정교한 무언가(가계도(계층구조, hierarchy), 배열 등)를 만들 수 있음
• 요즘은 64bit 포인터를 사용함(메모리가 커져서 → 주소값이 커져서 → 포인터도 커져야 함)
• string은 문자열의 첫 글자의 주소만 포인터로 알고 있으면 null terminating character가 나올 때 까지 가면 되니까 포인터로 구현 가능

메모리 할당, 해제

• 할당: malloc
• 해제: free
• 할당만 하고 해제를 안 하면? -> memory leakage
• 내가 할당한 배열의 인덱스를 넘어서려고 하면? -> buffer(배열) overflow

메모리 힙, 스택

• heap: malloc이 하나씩 할당해주는 메모리
• stack: 현재 호출한 함수나 인자가 담기는 메모리

overflow

• stack overflow: func(), func(), func(), func(), func()
• heap overflow: malloc, malloc, malloc, malloc, malloc

5. 자료구조

포인티: 포인터가 가리키는 곳

연결리스트

• 내가 넣고자 하는 값에 대해 메모리를 2개 할당하여, 하나는 실제 값을, 다른 하나에는 다음 값의 포인터(주소)를 저장한다.
• 삽입: *list로부터 하나씩 숫자를 탐색하면서 다음 노드를 가리키게 한 후, 같은 값을 가리키는 노드가 새로 삽입한 값을 가리키게 한다.
• 삭제: 뒤에서부터 하나씩 free해준다

트리

• next대신 left, right를 가지게 함

해시테이블

• 특정 첫번째 글자의 개수가 너무 많으면 → 2개 사용
• 이상적인 해시함수를 찾으면 검색을 O(1)에 가능
• 공간 시간 trade-off 고려

트라이

• 각 노드가 배열로 되어있는 트리
• 메모리 많이 먹지만, 탐색하려는 문자열의 길이만큼만 가면 돼서 O(1)

 

느낀 점

• C의 악명높은 포인터가 생각보다 어려운 개념은 아니었다.
• CS50에서 정말 기초적인 내용을 쉽게 설명해줘서 나도 잘 이해할 수 있었다.
• 하지만 CS50 자체가 중간에 skip한 내용이 많은 것 같아서 더 깊은 공부가 필요할 것 같다.
• 자투리 시간에 듣기 딱 좋았다.