[edwith CS50] 컴퓨팅 사고 1 (2진법, 정보의 표현, 알고리즘)

 

CS50이란?

* CS50은 하버드 대학교의 컴퓨터과학 입문 강좌이다.

https://www.edwith.org/introduce

에듀케이션위드 : edwith

 

edwith 네이버 커넥트재단에서 운영하는 온라인 교육 플랫폼에서 

입문 cs지식을 얻고자 해당 강의를 신청하여 수강하고 있다.

---

1. 2진법

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 총 10개의 기호로 표현하는 것이 10진법이다.

 

하지만 컴퓨터는 오직 0과 1로만 데이터를 표현한다.

이처럼 0과 1로만 표현하는 것이 2진법이다.

 

 

 

비트

정보를 저장하고 연산을 수행하기 위해 컴퓨터는 비트(bit)라는 측정 단위를 쓴다.

비트는 이진 숫자라는 뜻을 가진 “binary digit”의 줄임말이며, 0과 1, 두 가지 값만 가질 수 있는 측정 단위이다.

 

비트열

하나의 비트는 0과 1, 이 두 가지의 값만 저장할 수 있다.

컴퓨터 내부에서 물리적 표현될 때는, 켜고 끌 수 있는 스위치라고 생각할 수 있다. (켜기=1, 끄기=0)

 

생각해보기

1) 5를 2진법으로 바꿔보면 어떻게 될까요? 

정답 : 101 

---

2. 정보의 표현

앞서 2진법으로 숫자를 표현해보았다. 과연 문자는 어떻게 표현할까 ?
문자를 숫자로 표현 할 수 있도록 정해진 약속(표준)이 있다.
 
그 중 하나는 설명미국정보교환표준부호 ASCII(아스키코드/American Standard Code for Information Interchange)이다.

총 128개의 부호로 정의되어 있는데, 가령 알파벳 A는 10진수 기준으로 65, 알파벳 B는 66로 되어있다.

 

 

이 외에도 Unicode라는 표준에서는 더 많은 비트를 사용하여 더 다양한 다른 문자들도 표현가능 하도록 지원하고 있다.

Unicode는 😂(기쁨의 눈물) 이런 이모티콘 까지 표현할 수 있게 해주었다.

이 이모티콘은 10진법으로 128,514이며. 2진법으로는 11111011000000010 이다.

 

그림, 영상, 음악의 표현 

예를 들어 빨간색 72, 초록색 72, 파란색 33을 섞게 되면 노란색이 되는 것과 같은 방식이다.

이 숫자들을 표현하는 방식을 RGB(Red, Green, Blue)라고 한다.

즉, 노란색의 커다란 이미지는 72 73 33 으로 정의되는 무수히 많은 픽셀들의 RGB코드(숫자)로 표현할 수 있다.

 

생각해보기

1) 5를 2진법으로 바꿔보면 어떻게 될까요? 

정답 : 101 

2) CS50을 2진법으로 표현해보세요.

정답 : 67 83 50 -> 1000011 / 1010011 / 110010

(64 + 2 + 1) / (64 + 16 + 2 +1 ) / (32 + 16 + 2)

---

3. 알고리즘

전 강의에서 숫자, 글자, 색깔 등을 컴퓨터가 이해할 수 있는 2진법으로 표현 것을 배웠다.
이러한 내용은 입력(input)에 해당하는 것이다.

이제는 출력(output)에 대해 알아보자.

그럼 어떻게 입력(input)에서 출력(output)을 얻을 수 있을까 ?
알고리즘은 입력(input)에서 받은 자료를 출력(output)형태로 만드는 처리 과정을 뜻한다.

 

정확한 알고리즘

예를 들어, 전화번호부에서 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.     그만둔다

 

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

다음으로 노란색으로 강조된 부분들은 조건이다.
이 것은 여러 선택지 중 하나를 고르는 것이다.

첫 if문에서는 스미스의 이름이 페이지에 언급되어 있는 지를 확인하며

그 다음은 알파벳 순서로 정렬된 책에 따라 스미스의 이름이 지나쳤는지

아니면 뒤에서 나오는 것인지를 확인하여 뒤로 가거나 조금 더 앞 페이지로 이동하는 것이다.

 

마지막으로 노란색으로 강조된 부분은 루프(loop)이다.
이 것은 뭔가를 계속해서 반복하는 순환이다.

 

만약 Smith 이름이 앞에서 언급되어 있는 것으로 확인된다면, 다시 왼쪽 절반의 책을 열고 3번 루프로 돌아가

책의 내용을 확인하는 것이다.

 

 

생각해보기

3) 친구와 1부터 100까지 숫자 중 1가지 숫자를 맞추는 스무고개 게임을 하려고 합니다.

이 때 사용할 알고리즘을 의사코드로 표현하면 어떻게 될까요?

정답:

1. 숫자를 부른다.

2. if문 숫자 = 정답  종료.

3. 숫자 < 정답.  실패한 숫자보다 높은 나머지 숫자들의 중간값을 다시 부른다. 2번으로 loop한다. (기회 -1)

4. 숫자 > 정답.  실패한 숫자보다 낮은 나머지 숫자들의 중간값을 다시 부른다. 2번으로 loop한다. (기회 -1)

 

* 중간값이므로 소수점인 숫자는 부르지 않는다. 

* 기회는 20번 이므로 3번 4번에서는 기회를 한번씩 잃는다.