공부한 것을 정리해두는 곳

부스트코스에서 진행한 '모두를 위한 컴퓨터 과학(CS50 2019)'을 수강한 뒤 작성한 내용입니다.

몰랐던 내용을 위주로 정리했기 때문에 빠진 부분이 많을 수 있습니다.

1. malloc과 포인터 복습

포인터로 메모리 상의 실제 주소를 확인할 수 있다.

*, malloc, free 같은 함수로 메모리 관리하는 방법이 존재한다.

*은 역참조 연산자(그 주소로 가라는 말)

할당하지 않은 메모리를 사용하면 안 좋은 일이 벌어질 수 있다.

2. 배열의 크기 조정하기

배열로 많은 데이터를 한번에 캡슐화 할 수 있다.

배열의 크기를 늘리려면 배열이 위치한 메모리를 다른 곳으로 이동시키거나 복사한다. 주변에 다른 데이터들로 꽉 차 있기 때문이다.

옮기거나 복사해서 이전에 사용한 메모리는 버리거나 free를 실행한다. O(n), 배열의 크기 n만큼 시간이 소요된다.

malloc은 메모리 동적 할당 함수이다.

포인터 이름 옆에 대괄호를 쓰면 컴퓨터는 자동으로 그 메모리 덩어리의 첫번째 바이트로 이동한다. 모두 malloc이 반환했던 범위 안에 있다. 

메모리 덩어리. int arr[3]

메모리가 부족할 때 좋은 방법은 메모리를 할당 할 때마다 리스트가 null이 반환되었는지 확인해보는 것이다.

realloc : malloc의 메모리 할당, 직접 값들을 옮기거나 free를 모두 할 필요없이 한번에 합칠 수 있다. 이미 할당받은 기존 메모리 덩어리를 새롭게 가져오고 새롭게 설정된 크기로 바꾸는 작업을 한다.

배열은 본질적이고 메모리의 덩어리이다.

배열은 자동으로 free를 해준다. 컴파일러를 통해서 자동으로 진행된다.

3. 연결 리스트 : 도입

자료구조는 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해준다.

struct : 구조체, 자신만의 구조를 만들 수 있는 키워드. 비트맵, 비트맵 헤더 등에서 사용한다.

* : 메모리 덩어리로 접근할 수 있는 역참조 연산자.

연결 리스트 : 값들의 리스트를 저장하는 방법.

배열의 장점 : 쉬운 인덱싱, 랜덤접근으로 일정한 시간에 접근할 수 있어 빠르다.

바이너리 검색에 적용 가능하다.

연결 리스트는 값이 모두 떨어져 있기 때문에 대괄호로 인덱싱하여 접근할 수 없다.

문자 \0을 뜻하는 NUL과 NULL(포인터)은 다르다. 둘 다 0이긴 하다.

어떤 값이 실제로 메모리의 어디에 있는지는 중요하지 않다.

연결리스트는 메모리 덩어리 여러 개를 포함한 데이터구조이다.

node란 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미(컴퓨터 공학에서), 그래프의 노드와 비슷한 역할을 한다.

node 안에서 node를 쓸 수는 없다. typedef struct node라고 선언한다.

struct node *next;

4. 연결 리스트 : 코딩

연결 리스트에 값이 없으면 리스트가 없다는 것을 알려주는 변수가 있어야 하는데, 값이 없을 때 이를 표현하는 가장 간단한 방법은 0을 저장해서 'null'이라는 새로운 별명을 가지도록 하는 것이다.

(*n).number=2; == n->number=2; 두 코드는 같은 의미이다.

노드가 null이 아닌지 확인되기 전까지는 노드를 건드리거나 화살표 기호를 사용해서는 안된다.

얼마나 리스트가 크든 계속해서 임시 포인터를 움직여서 null을 찾을 때까지 따라간다.

값들이 어디에 있는지 기억하고 있는 변수가 없다면 메모리 누수가 발생하고, 컴퓨터에 요청할 수 있지만 다시 되돌려 받을 수 없다.

5. 연결 리스트 : 시연

컴퓨터는 한번에 하나의 메모리만 볼 수 있다. 노드의 한 칸만 보인다.

값을 정렬하기 위해서 각각의 값을 찾으려면 최대한으로 모든 값을 확인해야 한다.

연결리스트로 리스트에 동적으로 추가할 수 있다. 추가적인 값들을 malloc 하면 된다.

장점 : 배열처럼 숫자를 추가하기 위해서 크기를 조절하고 기존의 값을 모두 옮기지 않아도 된다.

단점 : 임의 접근을 할 수 없다. 처음부터 끝까지 가기 위해서 포인터를 따라가야 한다. 중간값으로 바로 갈 수 없다.

임의 접근을 사용하면 이진 탐색을 잘 할 수 있다. 연결 리스트는 이진 검색이 되지 않는다.

6. 연결 리스트 : 트리

트리는 두 개의 포인터를 가진 노드(이진 탐색 트리)

'탐색'트리는 순서를 맞추기 위해 신경을 썼다는 의미이다.

트리의 높이는 로그를 따른다.

재귀에 가장 적합한 방법이다.

트리에서 재귀적으로 정의되었다라는 의미는 어떤 노드에서라도 왼쪽이 더 작고 오른쪽이 더 크다는 것이다.

트리를 탐색하려면 트리의 루트릐 주소를 받는다.

log n : 이진 탐색 트리의 탐색 속도

이진 텀색 트리에 추가할 때 : 계속해서 작거나 큰 숫자를 넣으면 트리가 아주 얇고 길어진다.

이진 검색 트리의 균형을 유지할 수 있는 알고리즘이 있다. 어떤 값을 넣으면 요소들을 움직이게 되는 것이다.

그래서 이진 탐색이 가능한 배열과 같은 실행 시간을 가진다(log n)

연결 리스트는 크기를 줄이거나 늘릴 수 있지만 이진 탐색이 불가능하다. 공간을 더 써서 노드에 포인터가 두개씩 들어가게 하면 탐색하는 시간을 log로 단축시킨다.

7. 해시 테이블

배열과 연결 리스트를 조합한 것이다.

해시 테이블에서는 단어나 이름같은 입력값이 들어온다면 그 단어에 포함된 문자를 보고 어디에 그 이름을 넣을지 결정하는 방식이 흔하게 사용된다.

세로는 배열, 가로는 연결 리스트(예시)

충돌 : 어떤 값을 넣으려고 하는데 이미 무언가 들어있는 경우. 해시 테이블은 이것을 연결 리스트로 해결한다.

여기서 인덱싱을 하는데 사용하는 배열은 해시함수이다.

최악의 경우 O(n)의 시간이 추가하거나 탐색할 때 필요하게 된다. 대부분의 이름, 단어가 같은 문자로 시작될 때 첫 한글자가 아닌 첫 두글자를 본다. 공간은 더 많이 필요하지만 충돌할 확률은 낮아진다.

하지만 이렇게 글자를 늘려가다가 어느 순간부터는 그냥 연결하는 것이 낫다. 시간은 좀 더 걸린다. 시간과 공간 사이에 균형이 필요하다.

해시 테이블은 O(n)이 될 수 있지만 이론적으로는 느려질 수 있다.

8. 트라이

검색(retrieval)의 줄임말이다.

어떤 자원을 절약하기 위해 다른 자원을 소비하는 패턴이기 때문에 많은 메모리가 든다.

자료 구조 안에 있는 이름이나 단어를 찾는데 일정한 실행 시간을 가진다.

각각의 노드가 배열로 이루어진 트리다.

만약 트라이에 이름을 저장하고 싶은 경우 그 이름의 모든 글자들을 봐야한다.

해당 노드에 자식 노드가 없다면 그 아래에 다른 트리, 혹은 가지가 없으면 새로운 노드를 할당한다. 새로운 노드는 새로운 배열이다.

C에서는 boolean 연산식으로 여기에 이름 하나가 끝난다는 것을 표기할 수 있다.

이름의 각 글자에 대해서 하나의 노드(배열)이 저장된다.

Hagrid, Harry, Hermionie는 최소 하나의 노드를 나누어 가진다. 

고정된 값은 수학적, 컴퓨터 과학적으로 상수라고 한다. O(1) 상수 시간.

이 자료구조를 탐색, 삽입할 때 k값이 상수인 O(k)라는 것을 달성한다.

상수는 점근적으로 O(1)과 같다.

다른 자료구조는 이름들의 갯수에 따라 실행시간이 길어졌지만 트라이는 그렇지 않다.

빠를 대신 메모리를 많이 사용한다. 이름을 많이 삽입할수록 몇 노드들은 나누어 사용한다.

9. 스택, 큐, 딕셔너리

큐 : FIFO, 선입선출.

enqueue : 줄에 서서 들어가는 것 / dequeue : 줄을 바져나오는 것

스택 : LIFO 후입선출.

push : 넣는다. / pop : 뺀다.

딕셔너리 : 해시 테이블이라고도 생각할 수 있는 개념이다. 키/값, 단어/값, 단어/페이지 번호 등 쌍으로 이루어진 자료구조이다.

부스트코스에서 진행한 '모두를 위한 컴퓨터 과학(CS50 2019)'을 수강한 뒤 작성한 내용입니다.

몰랐던 내용을 위주로 정리했기 때문에 빠진 부분이 많을 수 있습니다.

1. 메모리 주소

16진수는 알파벳을 이용하여 한자리로 15까지 셀 수 있다.

16의 거듭제곱을 사용한다.

RGB 값을 표현할 때 사용한다.

진수 간의 모호함을 없애기 위해 16진수 앞에는 '0x'를 붙인다.

C는 변수의 메모리 위치를 확인할 수 있다. &이라는 주소 연산자를 사용한다. %P(가져온다는 의미).

메모리 주소는 16진수이다.

포인터 : 컴퓨터 메모리의 주소를 가리키는 것.

*는 그 주소로 가달라는 의미이다.

'*&n'의 의미는 주소를 받아서 다시 그 주소로 가서 n에 저장된 값을 볼 수 있다는 것이다.

C에서 자료형을 알려주는 기능은 없다.

2. 포인터

어떤 변수에 주소를 저장하고 싶다면 변수 앞에 *을 붙인다.

그 앞에 int는 *(포인터)가 가리키는 값의 type이다.

최근 컴퓨터는 보안상 문제로 메모리를 여기저기로 바꾼다.

주소를 저장하려고 할 때, *를 입력하지 않으면 에러가 난다. int p = &n, 주소는 반드시 포인터에 저장한다.

포인터는 추상화를 위해 사용된다.

포인터 변수는 다른 변수를 가리킨다. 아주 정교한 자료형을 만들 수 있다. 가계도, 배열 등.

최신 컴퓨터는 64bits 포인터로 사용한다. long 타입과 같은 크기이다.

3. 문자열

문자열을 저장하는 변수 s(예시)는 포인터로 메모리에 있는 저장된 문자열을 가리킨다. 첫글자가 있는 위치를 저장한다.

문자열의 첫번째 글자를 가리키면 널 종단 문자를 마주칠 때까지 루프를 돌면서 끝을 알아낸다.

C에는 문자열이라는 자료형이 존재하지 않는다.

포인터로 문자를 가리키는 주소를 저장한다. 문자열을 문자 배열의 첫번째 바이트 주소이다.

마지막 바이트에는 0을 저장하여 끝을 알려준다.

String은 char *와 동일하다(추상화).

문자의 나열을 결국에는 주소 하나로 나타낼 수 있다는 사실을 단순화 시킨 것이다. 문자열은 여러 문자의 묶음을 추상화한 것이다.

4. 문자열 비교

*(변수명+1)을 하면 문자열의 두번째 문차가 출력된다. 컴퓨터 내부에서 '변수명[1]과 같은 문법을 위처럼 바꿔주고 실행한다.

문자열 비교가 ==으로 안되는 이유는 값이 아닌 주소로 비교하기 때문에 같은 값을 입력해도 다르게 인식한다.

5. 문자열 복사

문자열 복사는 임시 변수나 다른 무언가처럼 =으로 되지 않는다. 그렇게 하면 주소가 복사된다.

서로 다른 메모리 공간에 문자열을 복사하려면 메모리를 추가로 사용해서 복사하려는 문자열과 동일한 크기의 변수를 만들고 복사하려는 문자열의 글자를 하나씩 복사한다.

malloc : 메모리 할당 함수, 인자로 받는 것은 할당받을 메모리의 크기이다. 할당된 메모리 공간의 시작 주소를 반환한다.

동일한 질문을 반복해서 물으면 나쁜 설계이다.

malloc은 요청한 메모리 크기를 할당할 뿐, 위치는 중요하지 않다.

쓰레기 값 : 초기화하지 않은 변수의 값

6. 메모리 할당과 해제

메모리 할당이란 메모리 일부분을 가져와서 그곳을 가리키는 포인터를 주는 것이다.

malloc의 반대(해제)는 free이다. 즉, 메모리 반환.

메모리 할당 후 반환을 해줘야 더 많은 메모리를 사용할 수 있다. 그렇지 않으면 느려진다. 그래서 사용하지 않는 메모리는 해제하는 것이 좋다.

이러한 실수를 찾기 위한 디버깅 도구는 valgrind를 사용한다.

sizeof를 쓰고 괄호 사이에 자료형을 쓰면 크기를 알려준다. 이는 동적으로 알아내는 방법이다.

버퍼 오버플로우 : 지정된 메모리, 메모리 배열의 공간을 넘어 접근한다면 발생한다. 버퍼는 배열이다.

프로그램에서 '쓰기'란 값을 바꾼다는 의미이다.

7. 메모리 교환, 스택, 힙

함수는 인자를 받을 때 변수 자체가 아니라 변수의 복사본을 전달 받는다.

메모리는 조직적인 방법으로 사용한다.

메모리의 맨 위에는 clang이 컴파일한 0과 1의 값(머신코드)가 들어간다.(./이름, 아이콘 더블클릭)

그 아래에는 전역 변수가 놓인다.

그 아래에는 힙(메모리를 할당 받을 수 있는 커다란 영역)이 놓이는데, malloc을 호출하면 메모리를 이 영역에서 가져온다.

힙은 아래로 자라기 때문에 메모리를 더 사용할수록 점점 더 아래로 내려간다.

힙 아래에는 스택(프로그램에서 어떤 함수를 호출할 때마다 함수의 지역변수들은 스택이라는 메모리 제일 아래 영역에 놓인다).이 놓이는데, 기본 함수 main에서 한 개 이상의 인자와 지역변수가 있다면 변수들은 스택에 놓인다.

다른 함수를 호출하면 그 위에 있는 메모리를 사용한다.

main 함수를 호출하면 메모리 맨 아래에 C의 기본 작동 방식으로 스택 프레임이라는 공간이 주어진다. 이곳은 지역 변수를 저장하는 공간이다.

main에게 x와 y의 주소를 알려줘서 값을 교환하는 함수가 그 주소로 가서 값을 바꾸게 한다.

int *a의 의미는 정수의 주소를 받아 a라고 부르는 것이다.

8. 파일 쓰기

스택 오버플로우 : 시작점 없이 자기 자신을 계속 호출

힙 오버플로우 : malloc을 계속 호출해서 너무 많은 메모리를 할당해 메모리 속 다른 내용을 덮어쓴다.

버퍼 오버플로우 : 컴퓨터가 너무 많은 메모리를 쓰면 정지하거나 아예 동작하지 않는다.

scanf는 사용자의 입력을 저장하고 싶은 변수의 주소를 적는다.

지정한 타입 외의 것을 입력하면 프로그램이 죽거나 예상하지 못한 방식으로 동작한다. scanf에는 에러 확인 기능이 없다.

포인터 변수는 그 자체가 주소로 정의된다.

null은 특별한 포인터로 가리키는 곳이 없다는 뜻이다.

배열 : 메모리가 연속적으로 할당된 공간.

문자열 : 문자가 연속적으로 있는 것, 그 메모리 공간의 첫번째 주소를 의미한다.

이러한 문맥에서 포인터는 배열과 같다.

clang 컴파일러는 문자 배열의 이름을 포인터처럼 다룬다. scanf의 상황에서는 배열 첫 바이트 주소를 넘겨준다.

fopen은 해당 파일을 가리키는 포인터를 반환한다.

fprintf : 파일용 printf로 파일에 출력할 수 있다.

csv : 쉼표로 분리된 값

9. 파일 읽기

fopen, malloc, get, string과 같은 함수는 에러가 생기면 null을 돌려준다.(반환)

모든 JPEG 파일의 첫 세바이트는 무조건 FF, D8, FF로 시작한다.

C에서는 16진수를 그대로 적을 수 있다.

변수 타입 앞에 붙는 unsigned char는 -128부터 127(char)이 아닌 0부터 255 범위의 값을 의미한다.

포인터로 파일에 적을 뿐 아니라 읽을 수도 있다. 

부스트코스에서 진행한 '모두를 위한 컴퓨터 과학(CS50 2019)'을 수강한 뒤 작성한 내용입니다.

몰랐던 내용을 위주로 정리했기 때문에 빠진 부분이 많을 수 있습니다.

1. 검색 알고리즘

배열의 값들이 정렬되어있는지 모를 때 최선의 방법은 선형검색이다.

이진탐색은 문제를 계속해서 두 갈래로 나눈다.

2. 알고리즘 표기법

Big-O 표기법 : 알고리즘이 얼마나 잘 설계되었는지, 코드가 얼마나 잘 구현되었는지 알려준다.

O(n), O(n/2), O($log_2^n$)으로 표기한다.

대략적인 추정값을 표현한다.

데이터가 커지면 결국 같게 보일 것이기 때문에 O(n), O($log_n$)으로 표기한다.

실행시간 : 프로그램이나 알고리즘이 동작하는데 걸리는 시간으로 몇 초가 걸리는지, 몇 번의 계산과정이 필요한지 나타낸다.

Big-O는 알고리즘을 수행하는 데 필요한 시간의 상한선을 의미한다.

$\Omega$(omega)는 최상의 경우를 나타낸다.

$\Omega(1)$이면 한 번에 성공하는 것을 의미한다(입력값이 특정 순서로 들어온다면, 실행 시간이 예상보다 짧아질 수 있다).

Omega 값보다 Big-O의 값이 좋아야 더 좋은 알고리즘인데, 컴퓨터 과학자가 가장 걱정하는 부분은 최악의 경우에 프로그램이 어떻게 동작할지 또는 평균적으로 어떻게 동작하는지이기 때문이다.

3. 선형 검색

C에서 string 비교는 ==을 사용할 수 없다. 문자열은 문자의 배열이기 때문에 문자열 속에 문자를 하나씩 비교해야 한다. 전체를 한번에 비교할 수 없다. 자바, 파이썬은 가능하다.

C는 모든 것이 로우 레벨로 진행된다. Strcmp라는 함수를 사용한다.

보통 return 0은 성공, return 1은 실패를 의미한다.

맨 앞의 0은 생략된다.

구조체 : 여러가지 자료형을 담을 수 잇다(struct)

4. 버블 정렬

가장 큰 수가 왼쪽에서 오른쪽으로 움직인다.

큰 숫자가 올바른 위치로 갈 때까지 움직인다.

n-1번 반복한다. n명이 서로를 비교한다면 최대 n-1번 비교할 수 있다.

Big-O 표기법 : (n-1) X (n-1). 앞부분은 바깥 반복문이고 뒷부분은 안쪽 반복문으로 0부터 n-2까지로, 숫자의 자리를 바꾸는 부분이다.

지수가 가장 큰 $n^2$의 영향력이 가장 크다. n이 커질수록 $n^2$가 미치는 영향은 더 커지기 때문이다. O($n^2$)은 선형 탐색이나 이진탐색보다 오래 걸린다.

Omega 값도 $\Omega(n^2)$인데 여전히 같은 횟수를 반복해야 하기 때문이다.

5. 선택 정렬

버블정렬의 장점은 직관적으로 보고 작은 문제를 풀어나간다는 것이다.

선택정렬은 매번 목표를 세워 가장 작은 값을 찾고 다음 작은 값을 찾는 방법이다. 반복할 때마다 다음으로 가장 작은 수를 맹목적으로 고른다.

반복횟수 : n+(n-1)+(n-2)+...+1 = n(n+1)/2

Big-O : O($n^2$)

$\Omega(n^2)$인데 프로그램은 배열 속 다른 값을 전부 보기 전까지 알 수 없기 때문이다. 최선의 경우에도 시간 낭비.

6. 정렬 알고리즘의 실행시간

교환이 없을 때까지만 반복하도록 바꾸면 알고리즘이 맹목적으로 n-1번 반복하지 않아도 된다.

이렇게 바꾸면 버블정렬은 $\Omega(n)$이 되므로 알고리즘의 실행시간을 줄일 수 있다.

O($n^2$)은 실행 시간으로 좋은 상한선은 아니다.

7. 재귀

재귀 : 프로그램이나 알고리즘이 스스로를 계속 호출하는 것.

재귀 함수는 내부에서 자기 자신을 호출한다.

재귀적 구조 : 가상의 물체의 구조를 그 물체 자체를 이용해서 설명하는 것

시작점에 대해서는 직접 '이건 특별한 경우이므로 아무것도 하지 말고' 이런 식으로 재귀적으로 자기 자신을 호출하지 않도록 알려줘야 한다.

재귀적으로 스스로를 호출하면서 기존 문제보다 더 작은 크기의 문제를 풀어간다(이진 탐색이나 분할 정복법처럼).

#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");
}

• 강의에서 궁금했던 점

예시 코드 중에 draw 함수에 나온 return이 return 0이 아닌 이유는 프로그램이 끝나는 게 아니라 그 뒤로 계속 실행되어야 하기 때문에 return인건가요?

→ draw함수에서 return 0이 아닌 return을 하는 이유는 draw함수의 반환값 타입이 void이기 때문입니다. 일반적으로 main 함수를 정의할 때 int main()으로 적었습니다. 즉 main함수는 int형 값을 반환하는 함수라는 뜻입니다. draw 함수의 경우 void draw()로 선언되었기 때문에 void 즉 아무것도 반환하지 않습니다. 따라서 반환값 없이 그냥 return하는 것입니다.

반복문 다음에 다시 되돌아가서 출력을 하는 방법은 가장 먼저 출력하는 것이다(디버깅 기능 사용). 출력을 하기 전에 draw 함수를 출력하기 때문이다. 함수가 초기에 주어진 입력보다 더 작은 입력을 가지고 계속해서 자신을 호출한다.

8. 병합 정렬

받은 입력에 항목이 하나라면 그냥 반환한다. 이미 정렬된거나 다름없다(순서가 틀린 게 없다).

병합 정렬의 순서는 1. 왼쪽정렬, 2. 오른쪽 정렬, 3. 두 배열의 병합.

병합이란 두 배열 중에서 가장 작은 값을 꺼내 다른 배열의 가장 작은 값 다음에 두는 과정이다. 크기 8의 배열을 쪼개어 크기 1의 배열 8개를 만든다. 항목이 1개면 더 이상 할 게 없으니 반환한다. 크기가 2인 배열 4개로 만들고, 크기가 4인 배열 2개를 만들고 크기가 8인 하나의 배열로 합친다.

무언가를 계속 절반으로 나눈다면 로그 함수로 표현한다. 크기가 8인 배열은 $log_n^2$($log_n$)이므로 $log^8$번 반복한다.

O(n $log_n$) : 병합 정렬의 실행시간

Omega (n $log_n$)

최악의 경우 훨씬 빠르지만, 최선의 경우에는 시간을 낭비한다.

$\theta$ : 어떤 알고리즘의 상한선과 하한선이 같을 때 사용한다.

맹목적으로 같은 알고리즘을 계속 반복한다.

알고리즘을 만들 때 목표는 정확하게 만들고 잘 설계하는 것이다.

부스트코스에서 진행한 '모두를 위한 컴퓨터 과학(CS50 2019)'을 수강한 뒤 작성한 내용입니다.

몰랐던 내용을 위주로 정리했기 때문에 빠진 부분이 많을 수 있습니다.

1. 컴파일링

메인함수는 시작버튼을 누르는 것과 같다.

<stdio.h>는 헤더파일(라이브러리)

파이썬은 자동으로 컴파일된다.

make나 clang을 사용(컴파일)할 때의 작업 처리 단계

1. preprocessing(전처리) : #_____라이브러리의 실제 코드로 대체된다.

2. compiling : 소스코드를 머신 코드로 바꾸는 단계. 어셈블리어로 변경. 어셈블링(0과 1로 이루어진 머신 코드로 바뀌는 과정). clang이 수행하며, 어셈블리어를 입력으로 받는다.

3. linking : hello.c, cs50.c, stdio.c를 하나로 뭉친다.

• 강의에서 궁금했던 점

stdio.h의 h는 헤더파일이라고 했는데, 그럼 hello.c 같은 파일도 헤더파일로 쓸 수 있나요? 

→ hello.c 와 같은 코드도 헤더 파일로 사용 가능합니다. .so 혹은 .a 파일은 이미 다른 누군가가 적어둔 코드가 있고 이 코드를 라이브러리 형태로 만들어 둔 것입니다. 그럼 링커는 어떻게 이런 라이브러리 파일을 찾아갈까요? 우리 컴퓨터 내부 어딘가에 모든 라이브러리가 모여있는 폴더(예, /usr/lib in Linux)가 있습니다. 사용자가 새로운 라이브러리를 설치할 때 해당 라이브러리의 .so 혹은 .a 파일이 이 폴더에 저장됩니다. 컴퓨터는 이미 라이브러리가 모여있는 이 폴더의 위치를 알고 있기 때문에 어떤 프로그램을 컴파일할 때 알아서 이 폴더를 찾아갑니다. 만약 이 폴더에 없는 특정 라이브러리를 사용하고 싶다면 컴파일할 때 옵션으로 사용하고 싶은 라이브러리의 경로를 줄 수도 있습니다. 즉, 여러분이 적은 hello.c와 같은 코드도 hello.so로 커파일 하면 충분히 가능합니다.

2. 디버깅

논리적 오류는 printf를 사용하여 확인하고, 문법적 오류는 에러 메시지를 확인한다.

IDE에서 디버깅 할 때, 행의 번호를 클릭하면 나오는 빨간점은 여기서 멈춘 뒤 사용자가 한 단계씩 진행할 수 있도록 미리 말해주는 것이다.

debug50이라는 프로그램을 사용할 때는 debug50 ./buggy2 로 실행.

노란색 줄은 디버거가 프로그램을 이 지점에서 멈췄으니 여기저기 살펴볼 수 있다는 의미이다.

스텝 오버 : 프로그램 실행 과정을 느리게 만드는 것으로 메모리 안에서 벌어지는 일을 실행 도중에 확인 가능하다.

3. 코드의 디자인

코드를 작성할 때는 나와 다른 사람들이 알아보기 쉽게, 유지보수하기 쉽도록 해야 한다.

4. 배열 1

문자 → 정수(ASCII) → 이진법

형변환 : 하나의 자료형을 다른 종류로 바꾼다. 

형변환은 형식지정자를 바꿔준다.

5. 배열 2

실수로라도 변하지 않는 값을 만들고 싶다면 상수를 사용하고, 메인함수 위에 작성한다. (ex. const int N = 3;) 이런 상수를 전역 변수(상수 바깥에서 선언하는 변수)라고 한다.

프로토타입은 메인함수 위에 반환값 함수명 (입력값); 으로 작성한다.

C에서 정수를 정수로 나누면 정수가 출력된다 → 형변환으로 처리

C의 배열은 스스로의 길이를 기억하지 않는다.

반올림이 가능하다.

• 강의에서 궁금했던 점

자바나 파이썬은 배열 스스로의 길이를 기억하나요? 예시가 궁금합니다.

→ 자바나 파이썬은 배열의 길이를 스스로 기억할 수 있습니다. C는 메모리에 값을 적고 그 값을 얼마큼 읽고 어떻게 해석하는지가 모두 프로그래머에게 달려있습니다. 하지만, 자바나 파이썬의 경우 객체 기반으로 구현되어 있습니다. array A를 만들면 프로그램은 A를 계속 배열로 인식합니다. 그리고 A에 대한 메타정보 또한 들고 있습니다. 따라서 자바에서는 A.length로 파이썬에서는 len(A)로 배열의 길이를 알 수 있습니다. 사진에서 보이듯 파이썬은 A라는 변수의 타입을 type(A)를 통해 확인할 수도 있습니다.

6. 문자열과 배열

배열 내 원소의 순서는 바이트 수와 무관하다. int가 4바이트라고 해서 0번째, 4번째, 8번째처럼 셀 필요가 없다.

string은 char의 배열이다.

string은 정해진 크기를 가질 수 없다.

널문자 \0, 8개의 비트가 모두 0을 나타내는 상태이며 문자열의 끝을 나타낸다. 예를 들어, HI!는 H, I, !, \0의 4바이트가 필요하다. 즉, 글자수+1 바이트만큼의 공간을 차지한다.

문자열의 출력방식에서 printf가 하는 일은 일종의 루프를 만들어 첫번째 글자부터 반복해서 확인한다.(널문자가 아니면 출력, 맞으면 break)

문자열의 길이 제한은 컴퓨터가 가진 메모리의 용량만큼이다.

7. 문자열의 활용

'\0'으로 쓰는 이유는 \n처럼 하나로 묶여있기 때문이다. 

프로그래밍이란 추상화를 이용해서 복잡한 기계어를 간단하게 처리하는 것이다. 

for문 안에 (strlen(s))처럼 함수를 넣으면 계속 함수가 호출되기 때문에 좋지 않은 디자인이다.

for문 괄호 안에 두 변수의 타입이 같다면 뒤에 오는 하나는 타입 선언을 생략해도 된다.

8. 명령행 인자

-o : 원하는 파일로 출력을 바꿀 수 있다.

보통 실행하고자 하는 프로그램 뒤에 적는다.

argv는 관습적인 표현, 인자 벡터를 의미, 인자들의 배열이라는 뜻이다.

argc는 인자 갯수를 의미한다.

C에서 프로그램 이름 뒤에 단어를 입력하면 그 단어들은 argv라는 배열에 들어간다.

argc에는 단어의 갯수가 저장된다.

메인 함수에 반환값이 있는 이유는 기본적으로 반환값을 가지며, 특별한 이유가 없으면 0을 반환한다. 0은 보통 문제 없음을 의미한다.

프로그램을 중단하려면 아무 문제 없다는 의미인 return 0을 반환하고, 문제가 있다면 다른 값을 반환한다.

argv에서는 처음에 입력하는 프로그램의 이름이 argv[0]에 저장된다. 그 다음에 첫번째로 입력하는 인자가 argv[1]이다.

return 값이 생략되어도 main함수에서는 암묵적으로 0을 반환한다.

부스트코스에서 진행한 '모두를 위한 컴퓨터 과학(CS50 2019)'을 수강한 뒤 작성한 내용입니다.

몰랐던 내용을 위주로 정리했기 때문에 빠진 부분이 많을 수 있습니다.

1. C 기초

printf의 f는 '형식화'를 의미한다.

컴파일러 : '소스코드'를 컴퓨터가 이해하는 이진법으로 바꾸는 프로그램

소스코드 → 컴파일러 → 머신코드

clang : 코드를 컴파일하는 프로그램의 이름

ls로 나온 파일들 중 *가 붙어있으면 머신코드

2. 문자열

형식지정자 %

-l : 두 파일을 연결

hello : 머신코드, hello.c : 소스코드

make hello는 hello.c라는 파일을 찾아서 hello라는 파일을 만든다. (clang -o hello hello.c -lcs50)

3. 조건문과 루프

효율적으로 코딩하기(적은 CPU와 메모리 사용)

for(___; ___; 변수를 어떻게 수정할 것인가;)

4. 자료형, 형식 지정자, 연산자

가독성이 좋은 코드로 작성하기

뒤에 /가 붙으면 폴더.

cd는 기본 디렉터리로 간다.

• 강의에서 궁금했던 점

get_char를 쓸 때 문자 외에 다른 것을 입력하면 아무일도 안 일어난다고 하고, get_int를 쓸 때 정수 외에 다른 것을 입력하면 계속 물어본다는데 왜 다를까요??

→ 여러분이 사용하는 라이브러리는 cs50 라이브러리입니다. 수업에서 배운 것처럼 라이브러리를 사용하여 다른 프로그래머가 이미 구현해둔 코드를 우리가 쉽게 가져다 쓸 수 있습니다. get_int와 get_char가 어떻게 동작하는지는 https://man.cs50.io/에서 확인할 수 있습니다. 링크에 들어가 보면 여러분이 이해한 것과 달리 두 함수 모두 이상한 입력을 넣었을 때 사용자에게 다시 입력을 요청한다고 나와 있습니다 (user is reprompted). 실제로 제가 코드로 테스트를 해본 결과 get_char 함수와 get_int 함수 모두 이상한 입력값을 넣었을 때 계속해서 물어봅니다. 강의 19:20에서 강연자가 아무 일도 일어나지 않는다고 한 상황의 조건은 문자 외 다른 것을 입력했을 때가 아니라 'y' 혹은 'n'이 아닌 문자를 입력했을 때입니다. 그 예시로 'x'를 입력하여 아무 일이 일어나지 않는다는 것을 보여줍니다. 이는 'x'라는 입력을 처리하는 조건문이 없기 때문이죠. 실제로도 문자가 아닌 다른 값 (예, 문자열)를 입력한다면 get_int와 똑같이 올바른 입력값이 들어올 때까지 계속 물어본답니다. 꼭 직접 해보시기를 추천합니다 :)

5. 사용자 정의 함수, 중첩 루프

추상화 : 어떤 함수가 printf로 구현된 것을 몰라도 그 함수가 있다는 것만 알면 된다.

main 함수는 위에 있을수록 좋다. 함수명만 메인함수 위에 입력한다(프로토타입).

void는 입력을 받지 않는다.

함수 왼쪽에 있는 단어는 출력의 종류를 의미한다.

괄호 안은 입력의 종류를 의미한다.

중첩루프에서 보통 i는 열, j는 행을 의미한다.

사용자 정의 함수는 코드 재사용이 가능하여 효율적이고 간결하여 유지보수에 효과적이다.

6. 하드웨어의 한계

RAM은 모든 프로그램이 실행 중 저장되는 곳이다.

컴퓨터는 계산 결과 값에 가장 가까운 값을 저장한다. 유한한 정보를 사용해서는 무한한 숫자들을 100% 정확하게 저장할 수 없기 때문이다.

for문에 가운데 값을 입력하지 않거나 ture를 입력하면 무한루프가 된다.

부동소수점 부정확성

오버플로우가 나타났을 때 0이 나오는 이유 : 111에 1을 더하면 1000이기 때문이다.

오버플로우 방지를 위해서는 자료형을 크게 잡는다.

부스트코스에서 진행한 '모두를 위한 컴퓨터 과학(CS50 2019)'을 수강한 뒤 작성한 내용입니다.

몰랐던 내용을 위주로 정리했기 때문에 빠진 부분이 많을 수 있습니다.

1. 이진법

트랜지스터 : 컴퓨터 내의 작은 스위치. 물리적으로 이용하여 정보를 표현하고 값을 저장

2. 정보의 표현

ASCII코드 : 영문만 표현, 8비트 사용

유니코드 : ASCII코드의 상위집합. 최대 32비트 사용

점(픽셀)은 RGB로 표현

3. 알고리즘

함수는 '동사'와 같다.

함수 외에도 조건 Boolean, loop 등이 알고리즘에 사용된다.

• 미션 중 궁금했던 점

내 컴퓨터는 레지스터가 64비트이므로, 한번에 2의 64승의 바이트를 처리할 수 있다. 라고 적은 부분이 있습니다. 왜 2의 64승의 비트가 아니라 바이트인지가 궁금합니다.

→ 여러분이 이해하신 것처럼 최근 컴퓨터는 64비트 레지스터를 사용하며 이는 한 번에 2의 64승의 비트를 처리할 수 있습니다. 예를 들면, 10101111.... 의 길이가 64라는 것입니다. 1 바이트는 8비트를 의미하기 때문에 64비트 레지스터를 8바이트 레지스터라고도 합니다. 자료를 찾는 과정에서 오타가 있었던 것 같습니다.