https://www.boostcourse.org/cs112/joinLectures/41307
David J. Malan (데이비드 J. 말란)의 <모두를 위한 컴퓨터 과학(CS50 2019)> 수강 내용
1) 메모리 주소
학습목표
16진법을 읽고 쓸 수 있다.
메모리 주소에 접근하고 값을 받아오는 코드를 C로 작성할 수 있다.
16진수
- 8비트로 셀 수 있는 가장 큰 값: 255(128+64+32+16+8+4+2+1)
- 16진수를 사용할 때는 모든 수 앞에 0x를 붙이기로 약속
- 아스키코드 -> 10진수에서 2진수로 -> 4자리씩 나누어서 16진수로 -> 0x를 붙임
메모리주소
#include <stdio.h>
int main(void)
{
int n = 50;
printf("%p\n", &n);
//%p : 포인터의 주소를 출력, &:~의 주소,추가 *:~의 주소로 가줘
}0x7ffe00b3adbc 와 같이 16진수의 메모리 주소 출력
2) 포인터
학습목표
포인터 변수를 정의하고 사용
포인터(pointer)
- 메모리의 주소값을 저장하는 변수
#include <stdio.h>
int main(void)
{
int n = 50;
int *p = &n; // 포인터 선언: p가 50의 주소를 가리키고 있음
printf("%p\n",p);
printf("%i\n",*p);3) 문자열
학습목표
문자열 형태의 새로운 자료형인 string이 어떻게 정의되었는가
효율성
- 아주 효율적이지 못한 방법
- 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용
구조체
- 여러 자료형을 가진 변수들을 하나로 묶어 자료형으로 사용할 수 있도록 정의하는 것
#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";
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;
}4) 문자열 비교
학습목표
문자열이 저장되어 있는 방식에 근거하여 문자열을 비교하는 방법에 대해 설명할 수 있다.
문자열
#include <stdio.h>
int main(void)
{
char *s = "EMMA";
printf("%p\n", *s); // 그 문자로 가세요 -> E 출력
printf("%p\n", *(s+1)); // -> M 출력
}문자열 비교
#include<cs50.h>
#include<stdio.h>
int main(void)
{
string s = get_string("s: ");
string t = get_string("t: ");
if (s==t)
{
printf("Same\n")
}
else
{
printf("Different\n")
}
}s = EMMA t = EMMA 라고 입력하여 컴파일을 하면, Different로 출력될 것이다.
이유는 s와 t가 각기 다른 메모리에 할당된 주소를 가지고 있기 때문에 컴퓨터는 이것이 다르다고 판단한다.
문자열을 비교하는 코드를 작성한다면,
5) 선택 정렬
학습목표
선택 정렬의 원리와 실행 시간을 설명하고 구현
선택 정렬
배열 안의 자료 중 가장 작은 수를 찾아 첫번째 위치의 수와 교환해주는 방식의 정렬. O(n^2),Ω(n^2)
//의사코드
for i from 0 to n-1
find smallest item between i'th item and last time
swap smallest item with i'th item 6) 정렬 알고리즘의 실행시간
학습목표
여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있다.
키워드
- Big O
- Big Ω
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
-
선택 정렬, 버블 정렬, 선형 검색, 이진 검색 4가지 알고리즘이 최선인 경우일 때의 실행시간이(하한) 빠른 순서대로 나열한 것은 무엇인가요?
(단, 하한이 같은 경우 상한이 빠른 순으로 나열한다)
이진 검색 - 선형 검색 - 버블 정렬 - 선택 정렬 -
오답체크
병합 정렬, 선택 정렬, 버블 정렬의 실행시간의 하한을 빠른 순서대로 정렬한 것은 무엇인가요?
버블 정렬 - 병합 정렬 - 선택 정렬
7) 재귀
학습목표
함수를 재귀적으로 사용하는 코드를 작성할 수 있다.
재귀
- 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)
{
// 높이가 h인 피라미드 그리기
for (int i = 1; i <= h; i++)
{
for (int j = 1; j <= i; j++)
{
printf("#");
}
printf("\n");
}
}- 피라미드 예시(재귀)
#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");
}스택
- 재귀 함수에서 동일한 함수를 계속해서 호출할 때마다 함수를 위한 메모리가 계속 할당된다. 이 메모리를 스택이라 한다.
- stack overflow: 재귀 함수를 무한 호출 했을 때 발생.
8) 병합 정렬
학습목표
재귀를 활용한 병합 정렬을 구현.
병합 정렬(합병 정렬)
- 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
- O(n log n), Ω(n log n)
//의사코드
on input of n elements
if n<2
return
else
sort left half of elements
soret right half or elements
merge sorted halves