[CS50] 컴퓨팅 사고

먼지·2022년 12월 12일

컴퓨터과학

목록 보기

1/2

boostcourse - 모두를 위한 컴퓨터 과학 (CS50 2019)

1. 컴퓨팅 사고

1) 2진법

핵심 단어

컴퓨터 과학
2진법
비트
바이트

컴퓨터 과학이란?

문제를 해결하는 과정이라 표현할 수 있음.

문제를 해결한다는 것은?
어떠한 입력(input)이 있을 때 그로부터 어떠한 출력(output), 그 문제에 대한 답을 찾는 것
그리고 그 중간 과정이 바로 컴퓨터 과학!

그리고 우린 이 블랙박스 안에 무엇이 있는지를 하나하나 채워가며 살펴볼 것

컴퓨터 과학의 첫 번째 개념은 바로 "정보 자체의 표현 방법"
컴퓨터는 0과 1의 조합인 2진법으로만 말할 수 있음. 그럼 어떻게 동작할까?
우리가 손가락을 접어가며 사용해 수를 세듯이 (단일 표기법)
많은 수를 셀 수 없지만 세상엔 10진법이란 기호가 있음.
우리가 일상에서 사용하는 0~9 총 10개의 기호로 표현하는 것이 10진법

하지만 컴퓨터는 그렇게 많은 숫자들이 없음. 오직 0과 1, 두 개의 숫자 뿐으로 데이터를 표현함
이처럼 0과 1로만 표현하는 것을 2진법이라고 함
컴퓨터는 0과 1만으로 숫자 뿐만 아니라 글자, 사진, 영상, 소리 등을 저장할 수 있음

2진법은 전기를 통해 연산하는, 즉 전기를 켜고 끄는 방식으로 작동하는 컴퓨터에게 적합한 방법으로 컴퓨터엔 굉장히 많은 스위치(트렌지스터)가 있고 on/off 상태를 통해 0과 1을 표현함

컴퓨터는 2진법에서 하나의 자릿수를 표현하는 단위를 비트(bit)라고 함

비트

정보를 저장하고 연산을 수행하기 위해 컴퓨터는 비트(bit) 라는 측정 단위를 씀. 비트는 이진 숫자라는 뜻을 가진 "binary digit"의 줄임말이며, 0과 1, 두 가지 값만 가질 수 있는 측정 단위

비트열

하나의 비트는 0과 1, 이 두 가지의 값만 저장할 수 있음. 하지만 비트 한 개는 많은 양의 데이터를 나타내기에 턱없이 부족함. 그렇기 때문에 여러 숫자 조합을 컴퓨터에 나타내기 위해 비트열을 사용함.
"바이트(byte)"는 여덟 개의 비트가 모여 만들어진 것. 하나의 바이트에 8개의 비트가 있고, 비트 하나는 0과 1로 표현될 수 있기 때문에 2^8=256 개의 서로 다른 바이트가 존재할 수 있음. 바이트가 모이면 더 큰 단위가 될 수 있음. 킬로바이트, 메가바이트, 기가바이트 등 더 큰 단위도 존재함

2) 정보의 표현

핵심 단어

ASCII
유니코드
RGB

숫자를 표현하는 방법은 알겠는데,, 컴퓨터는 어떻게 문자와 메일을 보내고 문서를 작성하는 등의 일을 할까? -> 글자를 숫자로 표현함! 그럼 어떤 숫자로 표현할지 다 같이 정해야 함. 간단하게 A는 1, B는 2 이런 식으로

우리 세계는 수십년 전에 대문자 A를 숫자 65로 표현하기로 정했음.
컴퓨터는 8비트 또는 8개의 스위치로 대문자 A를 저장하기 위해 64와 1 두 개를 켤 것임. 전구 대신 0과 1로 나타낸다면!
우선 10진법 기준으로 65이므로 26x1 + 25x0 + 24x0 + 23x0 + 22x0 + 2x0 + 1x1 (64+1)로 표현할 수 있음. 따라서 A를 2진법로 표현하면 01000001

문자를 숫자로 표현할 수 있도록 정해진 약속(표준) 중 하나는 설명미국정보교환표준부호 ASCII(아스키코드/American Standard Code for Information Interchange)
총 128개의 부호로 정의되어 있는데, 가령 알파벳 A는 10진수 기준으로 65, B는 66으로 되어있음

이 외에도 Unicode라는 표준에서 더 많은 비트를 사용해 더 다양한 다른 문자들도 표현이 가능하도록 지원하고 있음. 아스키로는 문자들을 표현하기에 충분하지 않았기 때문임

유니코드는 😂(기쁨의 눈물) 이런 이모지도 표현할 수 있으며 이 이모티콘은 10진법으로 128,514, 2진법으로는 11111011000000010. 만약 여러분이 스마트폰으로 😂 이모티콘을 친구의 스마트폰으로 보낸다면 11111011000000010 이라는 0과 1의 패턴을 보낸 것!

그럼 친구의 스마트폰의 안드로이드 혹은 iOS는 0과 1의 패턴을 받아 노란색 얼굴에 눈물을 흘리고 있는 사진으로 보여줌

그림, 영상, 음악의 표현

문자와 같이 그림도 역시 숫자로 표현할 수 있음.
우리가 스크린을 통해 보는 그림을 자세히 살펴보면 수많은 작은 점들이 빨간색, 초록색, 파란색을 띄고 있음. 이런 작은 점을 픽셀이라고 부름. 각각의 픽셀은 세 가지 색을 서로 다른 비율로 조합해 특정한 색을 갖게 됨. 이 숫자들을 표현하는 방식을 RGB(Red, Green, Blue)라고 함.

영상 또한 수많은 그림을 빠르게 연속적으로 이어 붙여놓은 것이기 때문에 숫자로 표현이 가능함. 음악도 마찬가지로 각 음표를 숫자로 표현할 수 있다!

3) 알고리즘

핵심 단어

알고리즘
의사코드

위에서 숫자, 글자, 색깔 등을 컴퓨터가 이해할 수 있는 2진법으로 표현하는 것을 배움. 이 것은 입력(input)에 해당하는 것

그럼 입력으로부터 어떻게 출력(output)?
컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정
그게 바로 이 블랙박스라는 곳에서 일어나는 일. 그리고 여기가 바로 컴퓨터 과학이 사용되는 곳

알고리즘은 INPUT에서 받은 자료를 OUTPUT 형태로 만드는 처리 과정을 뜻함

즉, 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열

문제 해결의 관점에서 보면 알고리즘은 그저 문제를 해결하는 단계적 방법일 뿐임. 그럼 우리가 원하는 문제를 풀기 위해선 어떤 알고리즘을 사용해야 할까?

정확한 알고리즘

예를 들어, 1000페이지 정도 페이지의 전화번호부에서 Mike Smith를 찾는 일을 함

첫 페이지부터 찾을 때까지 반복
2페이지씩 넘김 (속도2배)
중간에 지나칠 수 있음
언젠간 찾을 수 있겠지만, 정확성과 효율성이 중요함

멍청한 알고리즘? 올바른 좋은 알고리즘인지 어떻게 알 수 있을까?

정확하고 효율적인 알고리즘

전화번호부 가운데 펴기
만약 Mike가 존재하면 알고리즘은 끝
없다면 이름순으로 정렬돼있으므로 Mike가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 알고있음
그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 수행
한 페이지가 남을 때까지 계속 수행
이 알고리즘은 기존 알고리즘보다 더 효율적

Y축 혹은 수직축 : 문제 해결에 걸린 시간을 나타냄
X축 혹은 수평축 : 문제의 크기를 나타냄
X로 갈수록 페이지 수가, Y축으로 갈수록 페이지를 넘기는 시간이 길어짐

의사코드 (Pseudo-code 수도코드)

-> 영어로든 혹은 다른 언어로든 우리의 생각을 간결하게 정리한 코드와 비슷한 구문
의사코드는 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 도와줌

Mike Smith를 찾는 알고리즘을 이와 같은 의사코드로 나타낼 수 있음

1. 전화번호부를 집어 든다
2. 전화번호부의 중간을 편다
3. 그 페이지를 살펴본다
4. `If` Smith가 그 페이지에 있으면 (일종의 종속 관계를 확실히 하기 위해 들여쓰기로)
5.     4가 참이면 5단계로 넘어가 그에게 전화
6. `Else if` Smith가 책 앞쪽, 그러니까 왼쪽에 있다면
7.     책의 왼쪽 절반에서 가운데를 펴기
8.     3번째 줄로 돌아가기 (결과적으로 이걸 어떻게 반복할지. 페이지를 보고 어느 쪽으로 갈지 결정하는 코드. 만약 Smith가 정말로 책 앞쪽에 있다면 3으로 돌아가기)
9. `Else if` 만약 Smith가 책 뒤쪽에 있다면 
10.     오른쪽 절반의 중간을 펴고 
11.     3번째 줄로 돌아가기
12. `Else` 이 알고리즘에서 또 어떤 경우? - 그가 없을 수도 있음
13.     `Quit` 만약 그가 어느 페이지에도 없다면 탐색을 그만두기

의사코드를 보면 C언어나 파이썬과 같은 언어에서도 볼 수 있는 여러가지 공통점이 있음. 소위 절차적 프로그래밍이라 하는 특정한 건설법이 모든 언어들에 공통적으로 존재함

노란색으로 강조된 부분들은 함수(functions) 로, 컴퓨터에게 이 경우엔 사람에게 무엇을 할 지 알려주는 동사와 같음