스터디플래너/복습하기

모두를 위한 컴퓨터 과학(CS50 2019) 완강

술 2021. 10. 4. 21:24

 

부스트코스의 모두를 위한 컴퓨터 과학(https://www.boostcourse.org/cs112)

 

 

 네이버 부스트코스의 모두를 위한 컴퓨터 과학(CS50 2019)를 완강했다. 강의 소개에 '하버드대학 최고 인기강좌'라는 말을 인정할 수 밖에 없었다. 포인터 변수 부분이 약간 어려웠지만 수업 대부분이 재밌었다. 수업 내용은 더 길고, 과제도 많은 것 같은데 그런 것들에 직접 접근할 수 없어 아쉬웠다. 고등학교 때 이런 수업방식으로 C언어를 배웠다면 열심히 공부했을지도 모른다. 그나저나 배운 내용을 정리하고싶은데 강의 내용을 옮겨 적는 건 적합하지 않다고 생각한다. 그래서 수업 끝자락에 있는 생각해보기의 답변을 블로그에 정리하는 것으로 대신 해보려고 한다. 강의의 목차는 아래와 같다.

  1. 컴퓨팅 사고
    1. 2진법
      • 5를 2진법으로 바꿔보면 어떻게 될까요?
        - 101
    2. 정보의 표현
      • CS50을 2진법으로 표현해보세요.
        - C, S, 50의 아스키코드 값: 67, 83, 50 ->01000011, 01010011, 00110010 
    3. 알고리즘
      • 친구와 1부터 100까지 숫자 중 1가지 숫자를 맞추는 스무고개 게임을 하려고 합니다. 이 때 사용할 알고리즘을 의사코드로 표현하면 어떻게 될까요?
        -  1. 친구에게 1부터 100 사이의 숫자 중 하나를 말하라고 한다.
        　2. 친구가 숫자를 말한다.
        　3. 내가 생각한 숫자와 같다면
        　　4. 정답이라고 말해준다.
        　5. 내가 생각한 숫자보다 작다면
        　　6. 그 숫자보다 크다고 말한다.
        　7. 내가 생각한 숫자보다 크다면
        　　8. 그 숫자보다 작다고 말한다.
        　9. 2번째 줄로 돌아간다.
    4. 스크래치: 기초
    5. 스크래치: 심화
  2. C언어
    1. C기초
      • 아래의 실습하기로 "hello, boostcourse"를 출력해보세요.
    2. 문자열
      • "좋아하는 동물을 알려주세요"로 질문하여 동물 이름을 animal이라는 변수에 저장하고, 이를 "내가 좋아하는 동물은"으로 출력해주는 코드를 작성해보세요.
    3. 조건문과 루프
      • 학습한 다양한 방법을 이용하여 "개발공부는 재미있다!"를 10번 출력하는 코드를 작성해보세요.


    4. 자료형, 형식 지정자, 연산자
      • 짝수인지 홀수인지 알려주는 코드짜기에 자신의 스타일 대로 주석을 달아보고 다른 수강생은 어떻게 주석을 달았는지 비교해보세요.
    5. 사용자 정의 함수, 중첩 루프
      • 사용자 정의 함수를 사용하는 것의 장점은 무엇일까요?
        - 사용자 정의 함수를 사용하면 반복되는 코드를 함수로 선언하고 호출해서 사용함으로써 코드를 단축시킬 수 있다. 또한 함수의 내용을 변경해야 할 때 함수를 선언한 부분만 수정하면 되기 때문에 유지보수가 쉽다.
    6. 하드웨어의 한계
      • Y2K와 보잉787과 같은 문제를 방지하기 위해서는 프로그램을 어떻게 설계해야 할까요?
        - 프로그램을 설계할 때 사용하는 변수의 크기가 유한함을 인지해야 한다. 즉 변수의 크기가 해당 자료형의 크기보다 커졌을 때 어떻게 할 것인가를 생각하고 설계해야 한다. 당장에 프로그램을 제대로 설계하는데 드는 비용이 커보일 수 있어도 나중에 유지 보수할 일이 생기면 해결하는데 드는 비용이나 시간이 훨씬 크기때문이다.
  3. 배열
    1. 컴파일링
      • 만약 컴파일링 과정을 거치지 않기 위해 바로 머신코드로 우리가 원하는 프로그램을 작성하려고 한다면 어떤 문제가 있을까요?
        - 컴파일링이란 우리가 작성한 C언어를 어셈블리어라는 저수준 프로그래밍 언어로 변환하는 과정을 말한다. 따라서 컴파일링 없이 바로 머신코드로 원하는 프로그램을 작성하기 위해서는 C언어가 아니라 어셈블리어로 코드를 작성해야 한다. 자연어와 비슷한 C언어 코드보다 훨씬 복잡한 코드로 프로그램을 작성해야한다.
    2. 디버깅
      • 디버깅을 도와주는 프로그램은 어떤 경우에 더 큰 도움이 될까요? 만약 이런 프로그램의 도움 없이 직접 디버깅을 해야 한다면 어떻게 코드를 작성하는 것이 좋을까요?
        - 먼저 긴 코드로 작성한 프로그램에게 큰 도움이 될 것이다. 디버깅 프로그램은 몇 번째 줄에 에러가 발생했다고 알려주기 때문이다. 두 번째로 코드상 문제가 없는 프로그램에게 도움이 된다. 자주 사용한 cs50.h 라이브러리의 get_string 함수의 경우 라이브러리를 포함하지 않아도 코드상으로 문제가 없기 때문 디버깅하기 어렵다.
         디버깅 프로그램의 도움 없이 직접 디버깅해야한다면 메소드별로 직접 값을 출력해보거나 조건을 추가하여 조건에 어긋날 때 'return 1'과 같은 처리를 하면 될 것 같다.
    3. 코드의 디자인
      • 만약 여러 사람들이 함께 참여하는 프로젝트에서, 각자가 작성하는 코드 스타일 서로 다르다면 어떤 비효율적인 일이 발생할까요?
        - 여러 사람이 참여하는 프로젝트에서 각자 작성하는 코드 스타일이 다르다면 중복된 코드가 발생할 수 있다. 그리고 코드를 수정해야할 때 그 코드를 작성한 사람이 아니라면 코드를 수정할 수 없거나 코드를 수정하는게 더 번거로울 수 있어 생산성이 저하된다.
    4. 배열(1)
      • 실생활의 어떤 데이터를 배열로 표현할 수 있을까요?
        - 주차장에 주차된 차번호, 학교의 출석부나 회사의 인사기록카드와 같은 사람의 명단을 배열로 표현할 수 있을 것 같다.
    5. 배열(2)
      • 점수의 평균을 구하는 예제에서, 동적으로 작성한 코드는 그렇지 않은 코드에 비해 어떤 장단점이 있을까요?
        - 동적으로 작성하지 않은 코드는 점수의 평균을 구할 때 점수의 수가 바뀐다면 배열의 크기를 바꿔줘야 한다. 그리고 합계를 나눌 숫자도 바꿔줘야 하기때문에 번거롭다는 단점이 있다. 장점은... 코드를 쉽게 작성할 수 있다...?
    6. 문자열과 배열
      • 널 종단 문자는 왜 필요할까요?
        - 문자열 string은 기본 자료형이 아니라 문자형 char의 배열을 일컫는다. 널 종단 문자가 없다면 이 것이 문자열인이 문자인지 구분 할 수 없기때문에 종단문자가 필요하다고 생각한다.
    7. 문자열의 활용
      • string.h와 ctype.h의 라이브러리에 다른 어떤 함수가 있는지 확인해 보고, 어떤 함수를 어떻게 활용해 볼 수 있을지 생각해봅시다.
        - string.h 라이브러리에는 강의에서 문자열을 비교하는데 사용한 strcmp() 외에도 문자열을 연결하는 strcat(), 연결할 문자열의 갯수를 정할 수 있는 strncat()이 있다. ctype.h라이브러리에는 대문자와 소문자로 변환해주는 toupper()와 tolower() 외에도 아스키 문자로 변환할 수 있는지 확인해주는 isasciii를 비롯하여 문자에 사용하는 다양한 함수가 있다.  (출처: https://www.ibm.com/docs/ko/i/7.3?topic=files-stringh )
    8. 명령행 인자
      • 명령행 인자는 프로그램의 확장성에 어떤 도움이 될까요? 구체적인 예시를 떠올려보세요.
        - 데이터를 입력받는 코드를 작성하지 않아도 되기때문에 코드의 길이를 줄일 수 있다. 예를 들어 점수를 입력받아 평균을 구하는 프로그램을 작성할 때, 프로그램 실행 후 정보를 입력받으면 그 입력받은 정보도 따로 저장해야 한다. 하지만 ./argc 1001 75 85 90 로 입력받는다면 굳이 입력받는 함수를 정의할 필요 없이 1001번 학생의 국 영 수 점수가 받고, 평균을 바로 계산해줄 수 있을 것이다.
  4. 알고리즘
    1. 검색 알고리즘
      • 만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요?
        - 정렬되지 않은 배열은 선형 검색이 빠르다. 이진 검색은 배열이 정렬되어있다는 가정하에 사용할 수 있기때문에 비교하기 전에 정렬해줘야 한다.
    2. 알고리즘 표기법
      • 실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?
        - 실행시간의 상한이 낮은 알고리즘이 좋다. 식당에서 주문할 때를 예로 들자면 어떤 손님은 주문한 지 1분만에 음식을 받고 어떤 손님은 1시간이 지나야 겨우 음식을 받을 수 있는 식당과 모든 손님이 20분에서 30분을 기다리면 음식을 받을 수 있는 식당이 있다. 최악의 경우만 비교했을 때 한 시간을 기다려야 하는 식당과 30분 기다려야하는 식당 중 당연히 30분 기다리는 식당을 선택할 것이다. 상한이 높은 알고리즘은 시간복잡도로 보았을 때 빅 오부터 오메가까지의 범위가 넓어 그래프의 대부분을 차지할 것이다. 반면 상한이 낮은 알고리즘은  범위를 덜 차지할 것이다. 당연히 세타와 거리도 좁을테니 상한이 낮은게 좋다.
    3. 선형 검색
      • 전화번호부와 같이 구조체를 정의하여 관리 및 검색을 하면 더 편리한 예는 또 무엇이 있을까요?
        실생활 이곳저곳에 많은 것들이 구조체로 정의하여 관리 검색하면 편할 것이다. 학생시절 학생부나 회사의 인사기록의 경우 모두 학번과 직원번호 외 개인 정보들을 구조체로 정의할 수 있다.
    4. 버블 정렬
      • 버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?
        - 정렬되어있지 않은 배열을 순서대로 정렬할 때 효율적이다. 반면 정렬되어 있는 배열에 버블 정렬을 적용한다면 굳이 하지 않아도 될 일을 하므로 비효율적이다.
    5. 선택 정렬
      • 선택정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까요?
        - 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수가 증가는 정렬방식이다. 따라서 교환 횟수를 늘리고 비교 횟수를 줄여 적절하게 교환하고 비교한다면 효율적으로 바꿀 수 있다.
    6. 정렬 알고리즘과 실행시간
      • 선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?
        - 선택 정렬은 최선의 경우와 최악의 경우 n-1번 교환하고 n^2번 비교하므로 단축하기 어렵다.
    7. 재귀
      • 반복문을 쓸 수 있는데도 재귀를 사용하는 이유는 무엇일까요?
        - 검색해보니 반복문과 재귀문을 비교하여 사용하는 이유를 말해준 사람도 있지만 반복문과 재귀문을 비교하지 말라는 사람이 있다. 일단 반복문이 있는데 재귀를 사용하는 이유는 알고리즘이 재귀로 표현하는 것이 자연스러울 때, 변수의 사용을 줄일 수 있기 때문이다. 비교하지 말라는 사람의 의견은 재귀는 트리를 제어하기 위함이므로 반복문이 쓰여야하는 곳에 재귀를 써서 굳이 스택 오버플로우의 위험을 감수하지 말라고 했다. 어렵다.
    8. 병합 정렬
      • 병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까요?
        - 일단 시간복잡도로 보아도 선택 정렬과 버블정렬은 n^2인데 병합 정렬은 n (log n)이니까 훨씬 빠르다. 하지만 나누고 합치며 정렬하는 동안 중간 단계의 배열을 임시로 저장하고 정렬이 끝날 때까지 기억해둬야 하기때문에 메모리 공간이 필요하다는 것이 단점이다.
  5. 메모리
    1. 메모리 주소
    2. 포인터
    3. 문자열
    4. 문자열 비교
    5. 문자열 복사
    6. 메모리 할당과 해제
    7. 메모리 교환, 스택, 힙
    8. 파일 쓰기
    9. 파일 읽기
  6. 자료구조
    1. malloc과 포인터 복습
    2. 배열의 크기 조정하기
    3. 연결 리스트: 도입
    4. 연결 리스트: 코딩
    5. 연결 리스트: 시연
    6. 연결 리스트: 트리
    7. 해시 테이블
    8. 트라이
    9. 스택, 큐, 딕셔너리

수료 조건을 충족하면 이런 수료증도 받을 수 있다.