CS 50 - 컴퓨터 과학과 컴퓨팅 사고

컴퓨터 과학이란 무엇인가?

컴퓨터 과학이란 문제 해결에 대한 학문으로, 정보 자체보다는 정보의 수집, 전달, 축적, 가공 등에 대해 다루는 기계, 즉 컴퓨터를 다루는 학문이다.

실생활에서 컴퓨터 과학과 컴퓨터 공학에 대해 헷갈려하는 사람들이 많은데, 컴퓨터 과학은 응용수학과 전산학 이론 등 자연 과학의 Theory를 다루는 학문이라면, 컴퓨터 공학은 그 Theory를 이용해 실제 application을 만들어내는 학과라고 생각하면 쉽다.

 

컴퓨팅 사고

binary, 2진법

만약 당신이 "123"이라는 글자를 본다면 본능적으로 백의 자리 1, 십의 자리 2, 1의 자리 3이라는 계산을 해서 10진수 123으로 읽을 것이다.

당신도 모르는 사이 100 * 1 + 2 * 10 + 3 * 1 => 100 + 20 + 3 = 123을 연산했다는 것 .. 천재 아닐까요?

컴퓨터도 이와 같은 방식을 사용한다. 그렇지만 컴퓨터는 10을 기준으로 수를 나누는 게 아닌 0과 1 두 개를 사용하는 2진법을 사용해 수를 연산한다.

우리가 100의 자리(10 ^ 2), 10의 자리(10 ^ 1) 1의 자리(10 ^ 0)로 나눈 것처럼 컴퓨터는 16의 자리(2 ^ 4), 8의 자리 (2 ^ 3), 등등 ...

이러한 0과 1은 컴퓨터에 들어가는 반도체의 트랜지스터에 전류가 들어왔을 때 1, 아닐 때에는 0이 되는 것처럼 연산하게 된다.

2진법을 사용하는 컴퓨터와 10진법을 사용하는 우리나 원리적으로 정확히 같다!

우리의 123이 사실은 "1" "2" "3" 그 문자 자체에 지나지 않는 것처럼 컴퓨터의 0과 1도 따로 있으면 그저 의미가 없게 되고 이 숫자 하나씩이 bit, 8개 묶음이 byte가 된다.

만약 컴퓨터가 1(2진법 1)이라는 숫자를 가져올 때는 1bit를 읽어오고, 8(2진법 1000)이라는 숫자를 읽어올 때에는 4bit를 읽어온다면 연산 속도가 떨어지기 때문에 8bit씩(1byte)이 자료의 기본 단위가 된다.

 

쉽게 생각해서 택배 상하차를 한다고 생각했을 때, 박스에 들어있는 다양한 물건을 택배차에 싣는 게 물건을 따로따로 빼서 차에 싣는 것보다 적게 들어갈지는 몰라도 속도는 훨씬 빠르겠죵?

해서 "자료형"이라는 것이 필요한데 이 자료형이 박스의 크기 역할을 한다.

예를 들어 10 * 10 * 10 크기의 박스에는 해당 크기만 한 물건밖에 담을 수 없을 것이고, 더 큰 물건을 담기 위해선 더 큰 박스가 필요할 것이다.

이 박스의 크기별로 char(1byte), int(4byte), long long(8byte) 등의 자료형이 생기게 되는데, 만약 정수 50을 저장한다고 하면, 컴퓨터의 수십억 개 이상의 트랜지스터 중 4byte(32비트)만큼의 트랜지스터를 할당해두고 32(2 ^ 5), 16(2 ^ 4), 2(2 ^ 1) 위치의 트랜지스터에 약간의 전류를 저장하고 해당 위치를 기억해 사용한다.

그런데 만약 이 박스보다 큰 물건이 들어오게 되면 박스가 터져버리게 되는데, 그것이 overflow이다.

 

오버플로우

자 0과 1은 각각 0, 1이며 만약 십진 2를 표현하려면 비트가 하나 더 써서 10으로 표현해야 한다. 그리고 char라는 자료형의 박스는 이미 8개의 비트가 들어갈 공간을 미리 준비 중이다.

우리가 1, 2, 3... 9에서 10으로 다음 비트를 올리고 이전 비트를 0으로 초기화시키는 것처럼 컴퓨터도 0, 1, 10, 11, 100...으로 연산을 하고 있는데 만약 준비된 공간이 다 찼을 때 자릿수를 올려버린다면? 

char 자료형은 1바이트, 즉 8비트를 표현할 수 있는 컨테이너이다.

해당 자료형은 [11111111](2)까지 표현할 수 있는데 여기에 1을 더해버린다면 해당 자료는 1 [00000000]이 되어버린다. (편의를 위해 unsigned로 표현함, 전공자들은 그냥 넘어가셈)

이러한 현상을 오버플로우라고 하며, 오버플로우가 일어나지 않도록 하기 위해 저장하고자 하는 정보의 크기의 경곗값을 계산해 적절한 자료형에 저장해야 한다.

 

아스키 코드

컴퓨터가 0과 1로 모든 자료를 저장하는 건 알겠는데,, 어떻게 이거로 문서를 작업하고 메일을 보내나요?

 

생각할 시간 10초

 

문자를 숫자로 저장하고 이를 약속하면 되겠죵?

예를 들어 A는 1, B는 2 이런 식으로 약속하고 모두가 같은 방식을 사용하면 수를 이용해 문자열들을 나타낼 수 있게 된다.

실제로 이런 방식을 사용하고 있는데, 그것이 아스키코드이다.

ASCII Table

0 ~ 31까지는 줄 바꿈, 들여 쓰기 등등 실제로 사용하는 문자는 아니고, 32 ~ 126 사이의 문자가 화면에 실제로 표시되는 문자이다.

실제로 A는 수십 년 전부터 숫자 65였다 !

엥 그런데 지금 이 글은 한글인데 아스키코드에 없는데용?

넵 ASCII는 알파벳 등을 표현하지만 악센트가 있는 문자, 한글, 이모티콘까지 표현할 필요성이 있고, 이를 표현하기 위해 규약이 확장되게 되고 이를 유니코드(unicode)라고 표현함니당.

 

기존 아스키는 1바이트의 크기를 가져 0 ~ 255개까지의 문자를 표현할 수 있었지만, 이보다 더 많은 문자를 표현할 필요성이 있었고, 유니코드는 2바이트의 확장 문자형을 통해 0 ~ 65535개(16비트) 혹은 그 이상 (32비트)까지 표현할 수 있게 되었다.

😂  <-이 녀석은 10진수로 128514에 해당하는 숫자이다.(16bit 유니코드의 최댓값인 65535도 초과한다)

그리고 저 이모티콘을 나타내는 정보는 128514라는 숫자로 전송되어 128514라는 숫자를 받은 기계는 화면에 저 이모티콘을 출력하게 되는데, 이모티콘은? 텍스트가 아닌 사진이다. 실제로 이모티콘을 확대해보면 노랑, 파랑, 검정 등등의 색깔로 표현되는데, 화질이 낮은 이미지에서 실제로 이 점(픽셀)들을 볼 수도 있다.ㅎ

 

그럼 색깔은 어떻게 처리가 되나?

바로 RGB라는 방식으로 처리되는데 각 점들은 (Red : 1byte, Green : 1byte, Blue : 1byte) 총 3바이트로 이루어져 있으며, 0~255까지 각 색상의 양만큼을 더해 출력하게 된다.

 

이렇게 컴퓨터의 모~든 정보는 0과 1 둘로 이루어진 "패턴"이며, 컴퓨터의 기초이다.

---

문제의 해결, 알고리즘

우리가 작성하는 모든 코드는 입력과 출력이 있으며, 그 사이에 입력된 value를 다루어 원하는 "출력"을 만들어내는 과정이 생기게 되는데, 이 입력과 출력 사이에 존재하는 블럭이 알고리즘이다.

 

문제 해결의 관점에 있어 알고리즘은 문제를 해결하는 단계적 방법이다.

 

예를 들어 백과사전에서 원하는 단어(알고리즘)를 찾기 위해서 우리는

1. 가나다 순으로 이루어진 백과사전을 편다.
2. "ㅇ"에 해당하는 페이지를 편다.
3. 많은 "ㅇ" 중 모음이 "ㅏ"인 곳으로 페이지를 이동한다.
4. "아"가 들어가는 단어들 중 받침이 "ㄹ"인 곳으로 이동한다.
5. "알" 중 다음 글자의 자음이 "ㄱ"인 곳으로 ....
6. 찾을 때까지 반복

컴퓨터의 알고리즘도 크게 다르지 않다.

하지만 알고리즘에서는 "효율"이라는 개념이 작용하는데 같은 단어를 찾는다고 하더라도 다음과 같은 알고리즘이 있을 수 있다.

1. 백과사전의 첫 페이지를 편다.
2. "알고리즘"이라는 단어가 있는지 확인한다.
3. 있다면 멈추고, 아니라면 다음 페이지로 넘긴다.
4. 반복

해당 알고리즘도 같은 단어를 찾을 수는 있겠지만, 많은 시간과 노력이 들 것이다.

또는 첫 번째처럼 가나다 목차를 표시하지는 않지만, 가나다 순으로 정렬이 되어있기는 한 백과사전이라면 어떻게 찾아야 빠를까?

1. 페이지의 절반을 편다.
2. 해당 페이지의 자음이 "ㅇ"의 앞이라면 해당 페이지부터 맨 끝까지, 뒤라면 해당 페이지부터 맨 앞까지 절반을 나누어 편다.
3. 찾는 단어가 나올 때까지 반복한다.

한 장씩 넘기는 것보다는 훨씬 빠르다.

만약 백과사전이 1024페이지라면 단 10번 만에 모든 단어를 찾는 것이 가능하며, 좋은 알고리즘이란

주어진 상황에서 가장 최적(빠르고, 자원을 덜 소비하는)의 방법을 사용하는 것이다.

이렇게 최적의 알고리즘을 판단하는 기준이 시간 복잡도(속도), 공간 복잡도(Memory)이다.

 

물론 빠르면 좋긴 하지만, 30센티 구덩이를 파는 데에는 3억 원짜리 포크레인이 아니라 2만 원짜리 삽 한 자루만 있으면 된다.

주어진 자원을 적게 사용하며, 빠른 속도를 내는 접점이 최적의 알고리즘이 될 것이며 위의 1. 2. 3.처럼 코드는 아니지만 생각을 간결하게 표현한 것이 의사 코드 (Psuedo code)로, 이런 식으로 문제의 해결 방식을 정리해보는 습관이 최적의 알고리즘을 찾는 데에 큰 도움이 될 것이다.