부스트코스 - 모두를 위한 컴퓨터 과학 (CS50 2019) - 컴퓨팅 사고

2진법

컴퓨터 과학이란 문제를 해결하는 과정이다.
어떠한 입력이 있을때 그로부터 어떠한 출력을 그 문제에 대한 해답을 찾는것이다.
컴퓨터 과학의 첫번째 개념은 정보자체의 표현 방법이다.

어떠한 기계를 사용하기 위해서 입력과 출력을 어떻게 표현할지에 대해서 처음부터 모두가 동의해야만 한다.
컴퓨터에서는 이 표현법을 이진법으로 정의했고 약속했다. 만약 숫자가 10까지 밖에 없고 컴퓨터가 소화할 수 있는 숫자도 10가지 처리할 수 있는 데이터도 10가지라고 한정되어있다면 그냥 10자리 숫자나 글자를 표현하는게 전부일 것이다.

그러나 우리가 아는 컴퓨터는 모니터에 많은 색상을 선명하게 표현하고 이미지를 저장하고 보여주며 한번에 여러가지 복잡한 연산이나 처리를 손쉽게 해낸다.

이러한 모든것을 컴퓨터는 단지 0과 1로 처리한다. 데이터 저장, 영상 재생 등 많은것들이 이 0과 1이라는 두가지 단위로 모두 처리한다.

123

이것을 우리는 일 이 삼 이 아니라 백이십삼 이라고 읽는다. 어떻게 이렇게 읽을 수 있을까?
이것은 우리가 숫자를 사용할때 10진법 체계를 사용하기로 약속했고 그렇게 학습해 왔기 때문이다.

100 * 1 + 10 * 2 + 1 * 3

숫자를 백이십삼 이라고 읽기 위해서는 위와같은 수식을 거쳐야만 한다. 적어도 컴퓨터에게는 저렇게 명령을 내려줘야한다. 하지만 우리는 저런 복잡한 수식을 생각하지않고 바로 백이심삼 이라고 읽을 수 있다.

우리가 숫자를 사용하기 시작한 때부터 정해진 규칙이고 숫자의 체계이기때문에 가능한것이다.

컴퓨터에도 이와같은 체계가 있는데 그것이 이진법인 0과 1이고 2진법의 표현은 아래와 같다.

011 => (4 * 0) + (2 * 1) + (1 * 2)

1의 자리부터 2의 배수만큼 곱을해주고 해당 자리수에 값이 존재 하는지 안하는지는 단지 0과 1로 구분한다.
위의 표현을 10진법 체계로 읽으면 3이된다.

000 => 0
001 => 1
010 => 2
011 => 3
100 => 4
101 => 5
110 => 6
111 => 7

2진법 세자릿수로 표현할 수 있는 숫자는 7까지가 한계이다.
숫자를 더 표현하고싶다면 자릿수를 늘리면 된다.

1010 => 8 // (6 * 1) + (4 * 0) + (2 * 1) + (1 * 0)

컴퓨터에서는 이 0 과 1을 bit 라고 표현한다.
이 bit 가 8개가 모이면 한개의 바이트가 된다.

00000000 => 0
11111111 => 255
// 128, 64, 32, 16, 8, 4, 2, 1 => 2의 제곱근

한개의 바이트는 8개의 비트를 갖고 1byte 가 표현할 수 있는 최대 숫자는 255이다.
0부터 255까지의 숫자를 8개의 비트를 나열해 단지 0과 1로 표현 할 수 있다.

우리가 사용하는 일반적인 숫자체계를 사용해서 0부터 255까지 나열한다 치면 단지 8개로 끝나지는 않을것이다.

정보의 표현

지금까지는 이진법을 이용해 숫자를 표현하는걸 배웠다. 그렇다면 이미지나 동영상 그리고 문자열 같은것들은 어떻게 컴퓨터에서 표현되어질 수 있을까?

A

아주 오래전에 정해진 규칙으로 알파벳 A 는 숫자 65 로 표현이 가능하다. 해당 알파벳의 숫자를 8비트 이진법으로 표현하면 아래와 같이 된다.

// 128, 64, 32, 16, 8, 4, 2, 1 
01000001 => 65

이러한 문자들을 숫자로 표현 할 수 있도록 약속한 규칙이 있는데 ASCII 아스키코드 라고 읽는다.
총 128개의 부호로 정의되어있다.

A, B, C, ...., Z
65, 67, 68, ...., 90

만약 아래와 같은 숫자의 조합을 받았다면

72 73 33

문자열로

HI!

를 전달 받은것과 동일하다.

문자와 10진법 2진법으로 함께 표현하면 아래와 같이 된다.

   H       I          ! 
   72      73        33
01001000 01001001 00100001

여기서 8bit = 1byte = 영어알파벳한개 와 동일하다

하지만 이 표준은 미국중심이었고 세상에는 알파벳말고도 여러 문자들이 존재한다. 심지어 현시점 기준으로는 문자가 아닌 다양한 형태의 아이콘도 있는데 ASCII 표준으로는 이 모든 문자와 아이콘이미지의 표현이 불가능하다.

알파벳뿐만아니라 여러 문자와 아이콘형태의 이미지같은것들도 표현하기위해서 정의된 표준이 유니코드이다.
ASCII 는 8비트까지만 사용했기에 표현에 한계가 있지만 유니코드는 더 많은 비트를 사용하기 때문에 다양한 표현이 가능하다.

컴퓨터가 이미지를 표현하는 방법은 여러개의 색상을 표현하는 비트가 모여서 하나의 아이콘을 이루게되기때문에 이미지나 아이콘을 컴퓨터에서 크게 확대하면 작은 사각형의 점들이 모여서 이미지를 이루고 있는것을 알 수 있다.

이러한 색상을 표현하기위한 방법으로 RGB(red, green, blue)라는 체계를 사용한다. 이 세가지 색상을 조합하면 어떤 색상도 만들어 표현이 가능하기때문에 저 세가지 색상이 표준이된 체계를 사용하게 되었다.

영상이나 gif 의 밈 같은것들도 우리가 움직인다 라고 볼 수 있는것은 아주 빠르게 픽셀로 이루어진 여러장의 사진이 바뀌기 때문이다.

0과 1로 이진법을 표현하고 이진법으로 10진법의 숫자를 나타내고 이 10진법의 숫자들로 문자나 색상 등 다양한 표현이 가능하다. 그리고 결국 이 모든것은 0과 1로 이루어져있고 0과 1로 이 모든것을 표현 할 수 있다.

알고리즘

알고리즘은 쉽게 말하자면 문제를 해결하는 단계적인 방법이다.

그렇다면 우리가 원하는 결과를 만들어내기 위해서는 어떤 알고리즘을 사용해야할까?

가장 기초적이고 단순 무식한 방법 (n)

전화번호부책에서 어떤 사람의 전화번호를 찾는다고 가정했을때 그리고 목차가 없다고 가정했을때 그냥 원하는 정보가 나올때까지 한장씩 넘기는것이다. 시간이 좀 오래 걸리겠지만 언젠간 원하는 정보를 찾아낼 수 있다.

조금은 빠른방법 (n/2)

한장씩은 너무 느리다. 때문엣 좀더 속도와 효율성을 올리기위해 두장씩 넘긴다. 만약 지나쳤다면 다시 뒤로 한장만 넘기면 된다. 첫번쨰 방법보다는 두배 빨라졌다. 그러나 아직도 느리다.

최적의 방법 (log n)

전화번호부는 이름순으로 정렬되어있다. 그렇다면 어느 시점을 기준으로 내가 찾으려는 정보가 오른쪽에 있을지 왼쪽에 있을지 판단이 가능하다. 그래서 사용할 수 있는 방법이 절반씩 나누는것이다.

절반을 나누고 오른쪽 왼쪽중 원하는 데이터가 있는 방향쪽으로 다시 절반씩 나눈다. (아마 재귀를 사용할 수 있을것같다.) 만약 1000 페이지가 존재하는 전화번호부라면 기존에는 최대 천번, 또는 오백번씩 수행해야 했었겠지만 처음으로 절반을 나눈시점에서 즉 한번만에 500 장만 뒤지면 되도록 만들었고 한번더 절반을 나누는 작업을 수행하면 두번만에 250장만 뒤지면 되는 상황을 만들 수 있다.

대부분의경우

문제해결은 이미 사람들이 갖고있는 직관이나 생각들을 컴퓨터나 다른 사람들이 이해 할 수 있는 방법으로 풀어서 설명해 주는것이라고 할 수 있다.

그렇다면 어떤 알고리즘이 더 좋은지 알 수 있나?

문제를 해결하는 데에는 다양한 방법이있다. 정렬되어있는 전화번호부에서 내가 찾는 정보가 뒤쪽에 있는걸 미리 알고 있다면 뒤에서 부터 찾는게 더 빠를 수도 있다. 하지만 항상 뒤에서부터 찾는게 빠르다고 보장받 을 수 는 없다.

내가 찾는 정보가 있을수도 최악의 경우는 없을수도 있다. 어떤 방법을 쓰던지 결국 원하는 정보를 얻어내긴 하겠지만 어떤 알고리즘이 더 좋은지는 두가지를 기준으로 판단 할 수 있겠다. 정보를 찾기위한 동작을 몇번 수행했는지와 그 수행하는 시간을 기준으로 잡을 수 있다.

의사코드 작성하기

실제 동작되는 코드는 아니지만 우리는 알고리즘의 형태를 의사코드 즉 컴퓨터가 이해 할 수 있을만한 설명으로 작성 할 수 있다. 사람이 가진 의식으로 한다면 전화번호부에서 특정 데이터를 찾아라 라고하면 모두가 알아듣고 해당 데이터를 찾기위해 움직일 것이다.

하지만 컴퓨터는 어떤 전화번호부에서, 어떤 정보를, 어떻게 어떤 방식으로 찾아서 어떻게 출력하면 되는지 등 모든 과정에 대해 직관적인 설명이 필요하다. 이걸 코드로 작성하기전에 미리 작성 할 수 있는것이 바로 의사코드이다.

1. 번화번호부를 집어든다.
2. 전화번호부 중간을 펼친다.
3. 펼친 부분을 살펴본다.
4. if 원하는 정보가 있다면
5.      전화를 건다.
6. else if 없으면 펼쳐진 양쪽중에 왼쪽에 데이터가 존재한다면 왼쪽절반만 남긴다.
7.      남긴정보에서 다시 절반만 펼쳐본다.
8       3번으로 돌아가 반복한다.
9. else if 없으면 펼쳐진 양쪽중에 오른쪽에 데이터가 존재한다면 오른쪽 절반만 남긴다.
10.     남긴정보에서 다시 절반만 펼쳐본다.
11.    3번으로 돌아가 반복한다.
12. else 모든경우에 다 해당하지 않는다면
13.     종료