모두를 위한 컴퓨터 과학(CS50 2019) <1>

컴퓨팅 사고

• 2진법

  컴퓨터 과학은 문제해결에 대한 학문.
  문제 해결은 입력(Input)을 전달받아 출력(Output)을 만들어내는 과정.
  이러한 입력과 출력을 표현하기 위해선 2진법을 사용한다.
  2진법에서 100 은 2²x1 + 2¹x0 + 1x0 = 4 이다.
  컴퓨터에는 굉장히 많은 스위치(트랜지스터)가 있고 이를 통해 0과1 / on off /yes no 만으로 영상, 사진, 소리 등을 저장하고 출력한다.
  이러한 0과 1의 단위는 비트(bit), 8개가 모여 바이트(byte), 킬로바이트, 메가바이트, 기가바이트... 수없이 확장 되어 가고 있다.

• 정보의 표현

  컴퓨터는 스위치를 on/off 하면서 숫자를 표현함.
  그리고 문자를 표현하기위해 문자를 숫자로 정한 약속이 있는데 그중 하나가 아스키코드(ASCII)이다.
  
  이외에도 Unicode라는 표준에서는 더 다양한 문자들및 😂(기쁨의 눈물) 이런 이모티콘 까지 표현가능하게 해준다.
  우리가 스크린을 통해 보는 그림을 자세히 살펴보면 수많은 작은 점들이 빨간색, 초록색, 파란색을 띄고 있다. 이런 작은 픽셀은 세가지 색을 서로 다른 비율로 조합하여 특정한 색을 갖게 된다.
  예를들어 빨강 72, 초록 73, 파랑 33을 섞게 되면 노란색이 되는 것과 같은 방식이다.
  이 숫자들을 표현하는 방식을 RGB(Red, Green, Blue)라고 한다.
  영상은 이러한 그림들을 빠르고 연속적으로 이어 붙여 놓은것이며 음악은 각 음표를 숫자로 표현할 수 있다.

• 알고리즘

  숫자, 글씨, 색깔 등을 컴퓨터가 이해할 수 있도록 2진법으로 표현하여 입력을 해준다.
  컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정이다.
  알고리즘은 입력에서 받은 자료를 출력 형태로 만드는 처리과정을 뜻한다.
  즉, 알고리즘은 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적나열이다.
  
  일련의 순서적 규칙들을 어떻게 나열하는지에 따라 알고리즘의 종류가 달라진다.
  같은 출력값이라도 알고리즘에 따라 출력을 하기까지의 시간이 다를 수 있다.

  예를 들어, 전화번호부에서 Mike Smith를 찾는 일을 한다고 합시다.
  첫번째 방법)
  전화번호부를 집어 들고 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾습니다.
  없으면 그 다음 페이지에서 찾습니다.
  Mike Smith 를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복합니다.
  하지만 언젠가는 Mike Smith 가 전화번호부에 있다면 이 알고리즘을 통해 Mike Smith 를 찾을 수 있을 것입니다.

  두번째 방법)
  한 번에 두 페이지를 넘기게끔 하여 알고리즘을 개선할 수 있습니다.
  하지만 이 알고리즘을 그대로 사용한다면 Mike Smith가 있는 페이지가 그냥 넘어갈 수도 있으니 주의해야 할 것입니다.
  이럴 때는 이전 페이지를 확인하면 되지만 이 알고리즘마저도 이 문제를 해결하기에 가장 효율적이지는 않습니다.

  세번째 방법)
  먼저, 전화번호부 가운데를 폅니다. 만약 Mike Smith가 그 페이지에 있다면 우리 알고리즘은 끝납니다.
  없다면, 전화번호부가 이름순으로 정렬되어 있으므로 우리는 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 알고 있습니다.
  그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 수행합니다.
  한 페이지가 남을 때까지 계속 수행합니다.
  마지막에 남은 한 페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일 겁니다.
  이 알고리즘은 기존 알고리즘보다 더 효율적입니다.

알고리즘의 평가할 때는 정확성도 중요하지만, 효율성도 중요하다.
효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것이다.
위와 같은 알고리즘은 아래와 같은 의사코드 방식으로 보다 명료하게 정리 할 수 있다.

1. 전화번호부를 집어 든다
2. 전화번호부의 중간을 편다
3. 페이지를 본다
4. 만약 Mike Smith가 페이지에 있으면
5. Mike Smith에게 전화한다.
6. 그렇지 않고 만약 Mike Smith가 앞 페이지에 있으면
7. 앞 페이지의 절반을 편다
8. 3번째 줄부터 다시 실행한다
9. 그렇지 않고 만약 Mike Smith가 뒷 페이지에 있으면
10. 뒷 페이지의 절반을 편다
11. 3번째 줄부터 다시 실행한다
12. 그러지 않으면
13. 그만둔다

이것을 C언어나 파이썬언어로 바꾼다면

이렇게 될 것이다.

출처 : https://www.boostcourse.org/cs112/joinLectures/41307