[CS50] CS50 강의 기록

승민·2022년 6월 26일
0

공부해도 자주 까먹는 부분들을 기록하고 정리해봅시다!

C언어 특징

  • C언어는 문자열 비교시 == 연산자를 사용할 수 없고 string.h를 include하여 strcmp를 통해 문자열을 비교할 수 있습니다.
  • C언어는 main에서 사용자 정의 함수를 사용하기 위해서는 사용자 정의 함수의 정의를 main함수 위에 쓰거나 proto type을 맨 위에 적어주어야 사용 가능합니다.

컴파일링(소스 코드 -> 오브젝트 코드)

C언어의 컴파일링 과정은 다음과 같이 4단계를 거칩니다.

  • 전처리(Precompile)
    전처리기에 의해 수행되는 것으로 #으로 시작되는 C언어 소스 코드는 전처리기에게 실질적인 컴파일이 이루어지기 전에 무언가를 실행하라고 알려줍니다. 예를 들어 #include는 전처리기에게 다른 파일의 내용을 포함시키라고 알려줍니다.
  • 컴파일(Compile)
    전처리기가 전처리한 소스 코드를 생성하고 나면 컴파일을 합니다. 컴파일러라고 불리는 프로그램은 C 코드를 어셈블리어로 컴파일합니다. 어셈블리어로 코드를 변환시켜줌으로써 컴파일러는 컴퓨터가 이해할 수 있는 언어와 최대한 가까운 프로그램으로 만들어 줍니다.
  • 어셈블(Assemble)
    소스 코드가 어셈블리 코드로 변환되면 어셈블러가 어셈블리 코드를 오브젝트 코드로 변환시킵니다. 컴퓨터의 중앙처리장치가 프로그램을 어떻게 수행해야 하는지 알 수 있는 명령어 형태인 연속된 0과 1들로 바꿔주는 작업입니다. 소스 코드에서 오브젝트 코드로 컴파일 되어야 하는 파일이 1개라면 컴파일 작업은 여기서 끝이 나지만 그렇지 않으면 링크라는 단계가 추가됩니다.
  • 링크(Link)
    만약 프로그램이 여러 개의 파일로 이루어져 있어 하나의 오브젝트 파일로 합쳐야 한다면 링크라는 단계가 필요합니다. 링커는 여러 개의 다른 오브젝트 코드 파일을 실행 가능한 하나의 오브젝트 코드 파일로 합쳐줍니다.

정렬

버블 정렬의 하한 시간복잡도는 Ω(n^2)입니다. 이미 정렬이 된 값이 들어온 상태여도 정렬 상태를 확인하지 않고 n-1번씩 n-1번 순회를 하며 정렬 작업을 수행하기 때문입니다. 하지만 버블 정렬에서 조건문을 추가하여 더 이상의 swap이 없으면 정렬이 된 상태로 간주하여 정렬을 종료하는 코드를 추가하면 Ω(n)이 됩니다. 선택 정렬 또한 마찬가지입니다. 선택 정렬은 배열을 순회하면서 가장 작은 값을 찾아 맨 앞으로 옮기는 작업이 필요한데 최선의 결과로 배열을 입력 받아도 가장 작은 값을 찾기 위해서는 모든 배열을 순회하며 확인해야 하기 때문에 하한 시간복잡도는 Ω(n^2)입니다.
병합 정렬도 정렬 도중에 현재 배열이 정렬되었는지 알 방법이 없기 때문에 Ο(nlogn)과 Ω(nlogn)을 가집니다.

메모리 구역

그림과 같이 메모리 안에는 데이터가 저장되는 구역이 나누어져 있습니다. machine code 영역에는 프로그램의 컴파일된 바이너리가 저장됩니다. globals 에는 전역 변수들이 저장됩니다. heap에는 malloc으로 할당된 메모리의 데이터가 저장됩니다. stack에는 프로그램의 함수와 관련된 내용이 저장됩니다.

메모리 할당

정수는 4byte의 메모리를 차지합니다. 만약 정수의 배열 arr[3]이 있다면 arr[0]는 정수 배열의 첫 번째 메모리 주소를 가리키게 됩니다. arr[1]은 arr[0]의 바로 다음 메모리 주소가 아닌 4byte 뒤의 메모리 주소를 가리키게 됩니다.

profile
안녕하세요 승민입니다

0개의 댓글