[CS50] 1. 컴퓨팅 사고(1)

1. 2진법

인간은 숫자인 0~9 기호를 사용하여 숫자를 나타내고(10진법), 기계는 0과 1로만으로 모든 것을 나타낸다(2진법). 간단히 정리하면 1은 참, 0은 거짓인데, 이 논리가 컴퓨터에 굉장히 유용한 이유는 컴퓨터에게는 거짓과 참만이 중요하지, 인간과 달리 맞기도 하고 틀린 것 같기도 하고 같은 개념이 없기 때문이다. 0과 1은 전구에 빛이 들어왔는지 아닌지, 버튼이 눌러있는지 아닌지 등등 수많은 개념을 설명할 수 있는데, 컴퓨터에서는 최소의 단위가 비트다. 1비트는 0, 1을 나타내고, 8비트가 1바이트다. 숫자 0은 0, 1은 1, 2는 01이런 식으로 계속해서 자릿수를 늘려가며 숫자를 표현할 수 있다.

2. 정보의 표현

2.1 아스키 코드

그럼 문자는 어떻게 표현하는가? 문자를 나타내기 위해 문자를 숫자로 치환하여 표현하기로 약속했는데, 그 약속이 바로 아스키 코드이다. 알파벳 A는 65라고 약속을 했기 때문에, 컴퓨터가 65를 이진수(100001)로 받으면 A라고 인식할 수 있는 것이다.

2.2 유니코드

이 외에도 Unicode라는 표준에서는 더많은 비트로 더 다양한 문자들을 표현 가능하게 도와준다. 예로 들어 아이폰에서 사용할 수 있는 기쁨의 눈물 이모티콘은 128514로 나타내는데 이를 이진법으로 나타내면 더 길기 때문에 유니코드가 생겨난 것이다.

1.2 사진과 동영상, 음악

그럼 사진과 동영상, 음악은 어떻게 컴퓨터가 표현하는 것일까? 사진은 색이 있는 점들의 모임이다. 알다시피 색은 빨간색(R), 초록색(G), 파란색(B)로 현존하는 모든 색을 표현할 수 있다고 한다. 때문에 컴퓨터에서는 RGB 3 값을 입력받으면 빨간색 얼마, 초록색 얼마, 파란색 얼마로 결합된 색을 출력하게 된다. 사진은 그저 이러한 수많은 색들의 모임일 뿐이다. 사진을 보면 자세한 픽셀로 이루어져 있는데, 인간이 눈치채지 못할 정도로 작은 점들이다. 동영상은 이러한 사진들이 결합되어 만들어져 있는거다. 동영상은 사실 사진을 연속적으로 나타내는 사진들의 모임일 뿐인데, 인간은 그 차이를 느끼지 못하는 것 뿐이다. 이러한 동영상이 수많은 사진들을 다 저장하려면 용량 낭비가 굉장할 것이다. 그래서 동영상 압축 방법이 여러가지 나왔는데, 그 중 하나는 연속되는 사진들을 하나로 압축시키는 것이다. fps가 높아질수록 비슷한 사진들이 많아질텐데, 이 모든 사진들을 다 저장하면 용량낭비가 심하므로 변화가 있는 부분을 제외하고는 모두 같은 픽셀 값으로 저장하는 것이다. 음악 또한 각 음을 0과 1로 나타내어 음, 주기, 볼륨 등을 나눠서 음악을 저장하는 것이다.

3. 알고리즘

3.1 알고리즘의 정의

요즘 알고리즘이란 단어는 어딜가도 있다. 그러나 과연 알고리즘은 무엇인가? 교수님 말씀에 의하면 컴퓨터 공학은 문제를 푸는 학문이라고 한다(solving problems). 컴퓨터는 입력을 받고(input) 어떤 과정을 거쳐서 출력을 하는데(output)이 중간 과정이 알고리즘이다. 즉 알고리즘은 어떤 문제를 푸는데 필요한 일련의 처리 과정을 뜻한다.

3.2 정확한 알고리즘

강의에서는 전화번호부에서 Mike Smith를 찾는 방법을 예로 들며 알고리즘을 설명했다. 우리가 전화번호부에서 Mike Smith씨를 찾을 때, 수많은 방법이 있다. 제일 간단한 것은 한 페이지씩 읽으며 Smith씨를 찾는 것이다. 물론 굉장히 느리겠지만, 정확한 알고리즘은 맞을 것이다. 또는 2페이지씩 넘기며 찾는것이다. 이 방법은 앞에 얘기한 방법보다 빠를 수는 있지만, 중간에 넘긴 페이지 중에 Smith씨가 있을 수 있으므로 정확하지 않다. 이렇듯 한 문제를 푸는데에는 수많은 알고리즘이 있지만, 더 정확하고 효율적인 알고리즘은 따로 있다.

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

자 이제 앞에 문제에 대해 정확하고 효율적인 알고리즘을 찾아보자. 교수님이 예시로 든 방법은 이분 탐색에 기초를 둔 방법이다. 먼저 전화번호부의 중앙으로 간다. 우리는 Smith를 찾고 있기 때문에 알파벳 순서로 봤을 때 편 페이지가 S보다 앞에 있으면 중간을 기준으로 뒷 페이지 전부를 찢어 버린다. 그런 다음 다시 앞에 절반 부분의 중앙으로 가서 같은 과정을 반복한다. 이러한 방법을 계속 반복했을 때 결국에는 한페이지만 남게 되고, 만약 그 페이지에 Smith씨가 있으면 찾은 거고 없으면 멈추면 된다. 앞에 한장씩 넘기는 알고리즘은 페이지 수 n에 대하여 O(n)의 시간복잡도를 가지지만, 현재 설명한 알고리즘은 연속적으로 반을 남기고 나머지는 버리므로 로그2인 log2N의 복잡도를 가지게 된다. N이 증가함에 따라 그 효율성은 극명하게 갈리게 된다.

3.4 의사 코드(pseudo code)

의사 코드란 컴퓨팅 언어로 적진 않았지만 알고리즘의 명령을 인간이 알아들을 수 있는 언어로 적은 것을 의미한다. 예로 들어 위의 이분탐색 알고리즘을 의사 코드로 나타내면:

1. 책을 들어

2. 전화번호부의 중간으로 가

3. 페이지를 봐

4. 만약 Smith가 페이지에 있으면

5.         Mike에게 전화해

6. 앞에 해당하지 않고 만약(else if) Smith씨가 중간보다 앞에 있으면:

7.         책 중간을 기준으로 앞에 부분의 중앙을 펴

8.         3번 과정으로 돌아가

9. 위 두 조건 다 해당하지 않고 만약 Smith씨가 중간보다 뒤에 있으면:

10.       책 중간을 기준으로 뒷 부분의 중앙을 펴

11.       3번 과정으로 돌아가

12.만약 앞에 다 해당하지 않는다면:

13.       그만둬

중간 띄어쓰기를 해준것은(indentation) 종속관게를 나타낸다고 한다. 위에서 동작을 명령하는 단어들(펴, 전화해, 그만둬)등은 함수라고 불린다. 만약(else if) 등은 조건이라고 불린다. 결정 내리기 위한 질문(Smith가 페이지에 있으면, 중간보다 앞에 있으면 등)은 Boolean이라고 한다. Boolean 값은 참(True) 혹은 거짓(False)로 나타내거나 2진법(0 또는 1)로 나타낸다. 반복하는 순환(3번과정으로 돌아가)은 루프라고 한다.

 

생각해보기

Q) 친구와 1부터 100까지의 숫자 중 1가지 숫자를 맞추는 스무고개 게임을 할라고 하는데 이를 의사 코드로 나타내시오.

1. 시도 횟수는 0입니다.

2. 1부터 100까지의 숫자 중 하나를 고르시오.

2. 만약 고른 숫자가 맞다면 당신의 승리입니다. 게임을 종료합니다.

3. Else if 고른 숫자가 틀리다면

4.          시도 횟수에 하나를 더하십시오.

5.          만약 시도 횟수가 20번이 되었으면 당신이 졌습니다, 게임을 종료합니다.

6.          2번 과정으로 돌아가시오.