#1. 수강 과목 : 컴퓨터 과학 기초(4~5과)
#2. 수강 콘텐츠 : 모두를 위한 컴퓨터 과학(CS50 2019)

  1. 알고리즘
  • 검색 알고리즘 : 선형(순서대로 다 찾기) vs 바이너리(반 씩 쪼개서 찾기)
    상황에 따라(정렬에 따라) 어떤 것이 효율적일까 고민해보기

  • 알고리즘 표기법 : 알고리즘의 실행 시간 상한 / 하한(얼마나 잘 구현되는지)

Big-O 표기법(추정값 표현) : 추이가 같다면 같은 표현식 사용한다.(굳이 숫자로 쪼개지 않는다.) e.g O(n), Log(n)...
그에 따른 실행 시간 : O표기법을 속도 순으로 나열.(상한선 순)

반대로 실행 시간의 하한을 나타내는 척도
오메가 : 최선의 경우, 횟수로 나열(운 좋으면 한 번에도 끝날 수 있다에 대해서도 가정)

p.s 터미널 상에서 cd 가 안 먹힐 때 확인하는 법 : pwd로 위치 확인 후 그 다음 칸으로 갈 때 바로 다음 것 모를 때는 dir 로 검색해서 바로 상위 폴더 확인 후 이동한다.

  • 선형 검색
    예시1
#include <cs50.h>
#include <stdio.h>

int main(void){
    int numbers[6] = {4, 8, 15, 16, 23, 42};

    for (int i = 0; i < 6; i++){
        if (numbers[i] == 50){
            printf("Found\n");
        }
    }
    printf("Not found\n");
}
Not found // 50이 없으니까.

p.s

make: *** No rule to make target 'names'.  Stop.

에러는 파일명과 내가 하려는 것의 스펠 차이 혹은 위치 차이가 나서 생기는 것이었다. 별 거 아니니 s같은 거 잘 빠졌는지 확인하거나 pwd를 자주 해주자.(파일명은 name.c인데 내가 names로 컴파일링 하려고 했던 것에서의 차이. 진짜 예민한 친구다. c언어.

숫자 말고 문자열을 찾고 싶다면? ; 함수를 사용해야 한다.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void){
    string name[4] = {"EMMA", "RODIGO", "BRIAN", "DAVID"};

    for (int i = 0 ; i < 4; i++){
        if strcmp(name[i], "EMMA") == 0) {
            printf("Found\n");
        }
    }
    printf("Not found\n");
}

전화번호부 예시2

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void){
    string name[4] = {"EMMA", "RODIGO", "BRIAN", "DAVID"};
    string number[4] = {"617-555-0100", "617-555-0103", "617-555-0102","617-555-0104"};

    for (int i =0 ; i < 4 ; i++){
        if (strcmp(name[i], "EMMA") == 0){
            printf("%s\n", number[i]);
            return 0;
        }
    }
    printf("Not Found\n");
    return 1;
}

하지만 여기서 전화번호부와 사람 이름이 항상 일치한다고 볼 수 있는가??
-> 새로운 typedef 개념 살펴보기
(dictionary 비슷한 개념 같음)

#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 = "RODIGO";
    people[1].number = "617-555-0103";
    people[2].name = "BRIAN";
    people[2].number = "617-555-0102";
    people[3].name = "DAVID";
    people[3].number = "617-555-0104";


    for (int i =0 ; i < 4 ; i++){
        if (strcmp(people[i].name, "EMMA") == 0){
            printf("%s\n", people[i].number);
            return 0;
        }
    }
    printf("Not Found\n");
    return 1;
}

위에서 사용한 struct : 여러 데이터 타입을 담는 그릇이라 생각. 앞서 배운 내용들 종합해서 응용할 수 있는 개념.

  • 버블 정렬 : "비효율"
    정렬하는데는 얼마나 걸리지? 정렬을 꼭 해야 하는지?
    정렬에 대한 알고리즘 알아보기(정렬 안 된 배열을 정렬하는 것이 목표)
    버블 정렬(서로 크기 비교하며 옆자리씩 바꾸고 바꾸고 바꾸고....큰 값을 한 쪽에 몰아서 정렬하는 스타일)은 탐색 시간이 더 많이 걸림(숫자가 정렬이 안 되어 있기 때문에 정렬 하면서 찾아야 함.)
    & (n-1)의 제곱 형태
  • 선택 정렬 : "비효율"
    먼저 가장 작은 수를 왼쪽으로 옮김(옮겨서 놓을 자리에 있는 거랑 서로 바꾸는 식으로 정렬해 나감)
    그래서 이것이 더 나은 방법인가? : (작은 것을 계속 골라서 정렬하는 것이?)
    & n(n+1)/2 방식 ; 다른 것을 보기 전까지는 그 수가 제일 작은 수인지 장담할 수 없다. 최선의 경우에도 시간이 낭비될 수 있다.

  • 정렬 알고리즘의 실행 시간 : 만일 시간을 단축할 수 있는 명령어가 있다면?
    -> 버블 정렬도 시간이 줄 수 있다

  • 재귀 : 스스로를 계속 호출.
    반복문 중복으로 피라미드 만들기(1+ 1+1 + 1+1+1 ....재귀적 정의)
# include <cs50.h>
# include <stdio.h>
void draw(int h);
int main(void){
  int height = get_int("Height: ");
  draw(height);
  }

  void draw(int h){
      for (int i = 1; i<= h; i++){
          for (int j = 1; j <= i ; j++){
              printf("#");
          }
          printf("\n");
      }
  }
Height: 5
#
##
###
####
#####

위와 같은 이중루프를 재귀로 바꾸면 다음과 같이 바뀐다고 함.(더 작은 함수라는 값으로 재귀되면서 그려진다는 개념만 일단 이해하면 된다고 함.)

# include <cs50.h>
# include <stdio.h>

void draw(int h);
int main(void){
  int height = get_int("Height: ");
  draw(height);
  }

  void draw(int h){
      if (h==0){ // 음수가 되지 않게 막아줌
         return; 
      }
      draw(h-1); // 재귀되는 부분

      for (int i = 0; i < h ; i++){
          printf("#");
      }
    printf("\n");
  }
  • 병합 정렬 : 뛰어난 알고리즘. 다양한 분야에서 사용중. 다른 정렬에 비해 빠르다.
    왼쪽정렬 + 오른쪽정렬 + 병합정렬(맹목적으로 같은 알고리즘을 반복)
    nlog n 방식
    7 4 /5 2 / 6 3/ 8 1
    4 7 5 2 / 3 6 1 8
    2 4 5 7 / 1 3 6 8
    1 2 3 4 / 5 6 7 8(끝)
    따로 정렬하고 병합(계속 나누고 나눠서 서로 정렬하고 정렬함 그걸 병합함.)
    전화번호부 짜르고 짤랐던 '로그 방법' 생각하면 이해할 수 있다고 함.

  1. 메모리
  • 메모리 주소(16진법 읽기, 메모리에서 쓰고 있는 진법)
    0 1 2 3 4 5 6 7 8 9 A B C D E F
    e.g RGB 칼라 이름
    ox가 붙은 수는 모두 16진수 수라고 약속해놨음.
#include <stdio.h>

int main(void){

    int n =50;
    printf("%p\n", &n);
}
0x7fff808841ac // 실제 n값의 메모리 상 위치 확인하는 것, 주소

그 주소로 가달라는 명령어 :

    printf("%i\n", *&n); 
    // 프린트는 50 그대로 나오지만 그 주소로 가긴 감.(사용자가 볼 수는 없음)
  • 포인터 : 관리하기 어려운 메모리 주소를 쉽게 저장하고 접근할 수 있게 하는 개념(위에꺼는 포인터를 안 쓰고 정규표현식 쓴거고 이건 포인터를 쓴 개념. 결과는 같음.)
#include <stdio.h>

int main(void){

    int n =50;
    int *p = &n;
    printf("%p\n", p); // 포인터 사용.(별모양)
}
0x7ffe838e24bc //보안상 계속 바뀐다고 함. 여하튼 주소를 바로 보여줌.

그냥 50을 바로 표현하려면?
#include <stdio.h>

int main(void){

    int n =50;
    int *p = &n;
    printf("%i\n", *p);
}

이해한 개념 : n = 50도 어떤 주소를 가지고 있고, p도 어떤 주소를 가지고 있다. 근데 n의 주소와 p의 주소가 같아 n을 표현만 해주고 p도 어딘가 메모리에 저장 되어 있어 서로 화살표로 연결되어 있다.

뭔가 공통의 16진수 주소를 공유해서 필요할 때 그 짝이 맞는 걸 포인터가 데리고 오는 방식 같은데 자세히 이해하기가 어렵다. 오히려 예제로 들어준 우체통 이야기가 더 무슨 소린지 어렵게 만들었다.

  • 문자열 : 문자열이 실제로 메모리에 어떻게 저장되어 있는지?
    포인터는 첫글자만 안다.(종단, 중간 문자 다 모름) ; 더 이상 문자열은 없다.
    (typedef char *string) : 문자를 가르키는 주소, 마지막에 0을 저장해서 끝을 알려줌. 이걸 쓰는거지 사실 문자열은 없었다....(???!)
#include <stdio.h>

int main(void){

    char *s = "EMMA";
    printf("%s\n", s);
}
// include<cs 50> 쓴 것과 유사

    //printf("%p\n", s); 하면 string의 주소를 확인할 수 있다.
    0x42adba(첫번째 열의 주소. 굳이 인덱싱 안 해도 이 주소가 맞음)
    // 그 외 주소는 인덱싱하면 번호가 하나씩 이동하는 것을 알 수 있음.
#include <stdio.h>

int main(void){

    char *s = "EMMA";
    printf("%c\n", *s);

}
앞에 한 글자만(E)
// 여기에 s+1, 2... 하면 인덱싱이 됨.
  • 문자열 비교

방식 1(문자가 같은지)

#include <cs50.h>
#include <stdio.h>

int main(void){
    int i = get_int("i: ");
    int j = get_int("j: ");

    if (i == j){

        printf("Same\n");
    }else{
        printf("Different\n");
    }
}

방식 2(문자가 같은지)

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

엄밀히 말하면 두 주소를 비교해야하는데 지금은 문자열만 비교한 것임.
근데 주소를 비교하면 다음과 같음.

#include <stdio.h>
#include <cs50.h>

int main(void){
    char *s = get_string("s: ");
    char *t = get_string("t: ");
    if (s == t){

        printf("Same\n");
    }else{
        printf("Different\n");
    }
}
$ ./compare
s: 2
t: 2
Different
  • 문자열 복사
#include <stdio.h>
#include <cs50.h>
#include <ctype.h>

int main(void){
    string s = get_string("s: ");
    
    string t = s; // 복사

    t[0] = toupper(t[0]);

    printf("%s\n", s);
    printf("%s\n", t);
}
s: emma
Emma
Emma

알아서 s, t가 한 글자씩 복사되어서 결과값도 같아짐.(t는 s에 할당된 동일하게 움직이는 한 몸이라 생각)

만일 s와 t가 독립적이러면?(deepcopy생각)

#include <stdio.h>
#include <cs50.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

int main(void){
    char *s = get_string("s: ");
    
    char *t = malloc(strlen(s)+1);

    for (int i = 0, n = strlen(s) ; i < n + 1; i++){
        t[i] = s[i];
    }
    t[0] = toupper(t[0]);
    printf("%s\n", s);
    printf("%s\n", t);
}

  • 메모리 할당과 해제 : malloc된 것 완전한 메모리적 독립까지 시키려면?
    일단 위의 코드는 메모리 누수가 생긴다고 함. -> free
#include <stdio.h>
#include <cs50.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

int main(void){
    char *s = get_string("s: ");
    
    char *t = malloc(strlen(s)+1);

    strcpy(t, s);

    t[0] = toupper(t[0]);
    printf("%s\n", s);
    printf("%s\n", t);

    free(t); //메모리 누수를 해제시켜줌 : 오버플로우를 막아주는 역할한다고 함.
}
  • 메모리 교환, 스택, 힙 : 응용
    메모리 교환을 위해서는 두 컵에 든 물을 위치 바꾸듯 한 컵 정도의 여유 공간이 필요하다고 함.(by swap)
void swap(int a, int b)
{
	int tmp = a;
    a = b;
    b = tmp;
}

되는 것처럼 보이지만 실제로 안 됨(원본말고 복사본이 교환된 것이라 실제 사례로 해보면 안 됨.)
실제로 제대로 사용하기 위해서는 메모리의 작동 원리를 봐야 함

스택 > 힙 > 글로벌 > 머신코드 순으로 올라감

식이 이동하는 순서

메인(x, y)>스왑(a, b, tmp ; 여기서 값이 서로 바뀜)>근데 스왑부터 먼저 꺼내가버림..(먼저 넣었다고 먼저꺼를 꺼내는 개념이 아니라 나중에 넣은 것을 순서대로 꺼내는 개념이라 그렇다.)
결국 x, y는 바뀌지 않은 상태로 남음.

그렇다면 해결책은? : x, y 주소 자체를 스왑해버리면 된다

메인(x, y)>a, b가 x,y의 주소값과 연결(*)

void swap(int *a, int *b)
{
	int tmp = *a;
    *a = *b;
    *b = tmp;
}
  • 파일 쓰기 : 사용자로부터 값을 입력 받아 출력하는 프로그래밍
    사용자가 직접 입력한 주소를 저장하여서 전달하여 출력하는 형식
#include <stdio.h>

int main(void){
    char s[5];
    printf("s : ");
    scanf("%s", s);
    printf("s: %s\n", s);
}

설정된 용량에 맞게 string이 저장됨(여기서는 5까지밖에 안 됨.) 용량을 임의로 늘리기 위해 다른 코드를 쓰면 인식하지 못하고 NULL 처리 되는 듯.(확실히 이해한 개념은 아님.)

(사용자로부터 전달받아 파일을 만들어나가는 과정) ; 파이썬에서 파일 다루는 것과 유사
파일 컨트롤 :

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void){

    FILE *file = fopen("phonebook.csv", "a");

    char *name = get_string("Name: ");
    char *number = get_string("Number: ");

    fprintf(file, "%s, %s\n", name, number);
    fclose(file);
}
// .csv 내에 사용자가 입력한 내용이 적힘
  • 파일 읽기
    그림파일 예시로 찾기. ./ jpeg ~(파일 이름)
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[]){

    if (argc != 2){

        return 1;
    }
    FILE *file = fopen(argv[1], "r");
    if (file == NULL){
        return 1;
    }

    unsigned char bytes[3];
    fread(bytes, 3, 1, file);

    if (bytes[0] == 0xff && bytes[1]== 0xd8 && bytes[2] == 0xff){
        printf("Maybe\n");

    }else{
        printf("No\n");
    }
}

이 때 사진 파일도 마찬가지로 2진법으로 찾는다고 함.

profile
커피 내리고 향 맡는거 좋아해요. 이것 저것 공부합니다.

0개의 댓글