CS50 Study

2진법

• 0과 1로만 데이터를 표현하는 방식

비트

• 2진법에서 하나의 자릿수를 표현하는 단위
• 0과 1 두 가지 값만 가질 수 있는 측정 단위

비트열

• 비트 한 개는 많은 양의 데이터를 나타내기에 턱없이 부족하기에 비트열을 사용
• 비트열들이 모여 더 큰 단위들이 될 수 있다.
• 바이트 => 8 비트, 킬로바이트 => 1,000 바이트 ...

문자의 표현

1. ASCII : 128개의 부호로 정의된 문자의 표현

1. Unicode : 더 많은 비트를 사용하여 더 다양한 다른 문자들도 표현가능하도록 지원 (ex. 이모티콘)

그림, 영상, 음악의 표현

• 빨간색, 초록색, 파란색을 띄는 수만은 점들의 조합으로 표현 => RGB 방식

C언어

• 오래된 언어이기 때문에 변수가 저장하는 데이터의 종류를 정확하게 명시해야 한다.

데이터 타입

• bool: 불리언 표현, (예) True, False, 1, 0, yes, no
• char: 문자 하나 (예) 'a', 'Z', '?'
• string: 문자열
• int: 특정 크기 또는 특정 비트까지의 정수 (예) 5, 28, -3, 0
• long: 더 큰 크기의 정수
• float: 부동소수점을 갖는 실수 (예) 3.14, 0.0, -28.56
• double: 부동소수점을 포함한 더 큰 실수

형식 지정자

• %c : char
• %f : float, double ('.원하는 자리수'를 넣어 소수점 n번째 자리까지 표시 가능)
• %i : int
• %li : long
• %s : string

사용자 정의 함수의 장점

1. 코드의 가독성이 올라간다.

2. 유지보수가 쉬워진다. 

3. 코드를 효율적으로 작성할 수 있다. 

 

명령어를 실행했을 때의 과정

전처리 -> 컴파일 -> 어셈블링 -> 링킹

 

1. 전처리: 전처리기에 의해 수행, #으로 시작되는 C소스 코드는 전처리기에게 실질적인 컴파일이 이루어지기 전에 무언가를 실행하라고 알려준다.

 

2. 컴파일: C코드를 어셈블리어라는 저수준 프로그래밍 언어로 컴파일한다. (컴퓨터가 이해할 수 있는 언어와 가깝도록)

 

3. 어셈블: 어셈블리 코드를 오브젝트 코드로 변환한다. (연속된 0과 1들로 바꿔주는 작업 -> 어셀블러에 의해 수행)

 

4. 링크: 프로그램이 여러 개의 파일로 이루어져 있어 하나의 오브젝트 파일로 합쳐져야 할 경우 필요하다.

 

디버깅

- 코드에 있는 버그를 식별하고 고치는 과정이다.

 

메모리

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

 

C언어 함수

• strlen(): 문자열의 길이를 알려주는 함수 (string.h 라이브러리)
• tolower(), toupper(): 문자를 대소문자로 변환해주는 함수 (ctype.h 라이브러리)

 

선형 검색

- 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.

- 정확하지만 아주 효율적이지 못한 방법 (? 최악의 경우 리스트의 모든 원소를 확인)

 

버블 정렬

- 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식 (단 두개의 요소만 정렬해주는 좁은 범위의 정렬)

- 최대: O(n^2) 최소: Ω(n^2)

 

선택 정렬

- 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식

- 최대: O(n^2) 최소: Ω(n^2)

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n)
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

 

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬
• Ω(n log n)
• Ω(n)
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색