이 글은 부스트코스의 모두를 위한 컴퓨터 과학 (CS50 2019) 강의를 참고하여 포스팅하였습니다.
컴퓨터 과학이란 무엇인가?
컴퓨터 과학이란 문제를 해결하는 과정을 공부하는 학문이다.
문제를 해결한다는 것은 입력(input)을 전달받아 출력(output)을 만들어내는 과정이다.
그리고 그 중간에 있는 과정이 컴퓨터 과학이다.
앞으로 컴퓨터 과학을 배움에 있어 입력과 출력을 표현하기 위한 약속(표준)이 필요하다.
2진법
컴퓨터는 입력과 출력을 표현하는 방법으로 2진법을 사용한다.
우리는 일상에서 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 이루어진 10진법을 사용하는 반면,
컴퓨터는 오직 0과 1로 이루어진 2진법을 사용한다. 컴퓨터는 0과 1만으로 다양한 글자나 사진, 영상, 소리 등을 저장할 수 있다.
먼저 10진법으로 표현된 숫자를 예시로 살펴보자.
우리는 123이라는 숫자를 당연히 백이십삼이라고 읽을 것이다.
이것을 자세히 표현해 보면 1x100 + 2x10 + 3x1 = 123으로 표현되어 백이십삼이라고 읽는 것이다.
10진법에서는 각 자리의 숫자들에 10의 거듭제곱을 곱해 표현하였다.
비슷하게 2진법에서는 각 자리에 2의 거듭제곱을 곱해 수를 표현한다.
예를 들어 10진수 5를 표현하기 위해서는 1x4 + 0x2 + 1x1 = 5이므로 2진수로 101이라 표현한다.
비트
컴퓨터는 비트라는 측정 단위를 이용해 정보를 연산하고 저장한다.
비트는 binary digit의 줄임말로 0과 1 두가지 값만 갖는 측정 단위이다.
컴퓨터는 디지털 데이터를 여러 개의 비트들을 조합함으로써 0과 1 두가지 값만으로도 많은 양의 정보를 저장할 수 있다.
비트열
하나의 비트는 0과 1, 두 가지 값만 저장하기 때문에 많은 양의 데이터를 저장하기엔 턱없이 부족하다. 때문에 다양한 데이터를 저장하기 위해 여러 개의 비트들을 조합하여 사용하고 바이트(byte)는 8개의 비트가 모여 만들어진 것이다.
비트 하나는 0과 1을 표현할 수 있으므로 1바이트는 2^8 = 256개의 수를 표현할 수 있다.
문자의 표현
컴퓨터는 오직 0과 1로 이루어진 2진법을 사용한다고 했다. 그렇다면 문자도 0과 1로 이루어진 숫자로 표현해야할 것이다.
문자를 숫자로 표현하는 방식에는 다양한 표준이 존재하는데 그 중 하나로 ASCII(아스키코드)와 Unicode가 존재한다.
ASCII
아스키코드는 총 128개의 부호로 정의되어 있다. 아래는 아스키 코드 중 알파벳 대문자 부분만 발췌한 것이다.
몇 개를 살펴보면 A는 65, C는 67로 표현된다. 이는 10진법 기준이므로 2진법 수로 변환하면 1x64 + 0x32 + 0x16 + 0x8 + 0x4 + 0x2 + 0x1 (64+1)이므로 1000001이다.
몇 가지 더 예를 들어보자.
- HELLO =
7269767679
아스키 코드는 128개의 부호들로 정의되어 있기 때문에 알파벳 대문자/소문자와 몇가지 특수기호, 명령어들로 이루어져 있다.
그렇기 때문에 다양한 언어의 문자와 이모티콘, 특수 문자 등을 표현하기 위해 Unicode라는 표준이 등장한다.
Unicode
Unicode는 적게는 8비트, 많게는 32비트까지 이용해 문자를 표현가능 하도록 지원한다.
😂 ← 이런 이모티콘 까지 표현이 가능한데, 이 이모티콘은 10진법으로 128,514이며 2진법으로는 무려 11111011000000010로 표현해야 한다.
알고리즘
앞서 컴퓨터가 숫자, 글자, 색깔 등을 컴퓨터가 이해할 수 있는 2진법으로 표현하는 것을 배웠다. 이것은 입력(input)에 해당하는 것이다.
그렇다면 이 입력(input)에서 어떻게 출력(output)을 얻을수 있을까?
알고리즘은 입력(input)에서 받은 자료를 출력(output) 형태로 만드는 처리 과정을 뜻한다.
즉, 알고리즘은 입력값을 출력값의 형태로 바꾸기 위해 명령들이 어떻게 수행되어야 하는지에 대한 규칙들의 순서적 나열이다.
같은 출력값이 나오더라도 알고리즘에 따라 출력을 하기까지의 시간이 다를 수 있다.
전화번호부에서 Mike Smith를 찾는 예제
- 첫 번째 알고리즘
- 전화번호부를 집어 들고 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾는다.
- 없으면 그 다음 페이지에서 찾는다.
- Mike Smith를 찾을 때까지 또는 전화번호부가 끝날 때까지 이것을 반복한다.
이 알고리즘의 정확도를 따져보면 확실히 Mike Smith를 찾는 데에는 문제가 없을 것이다. 하지만 알고리즘을 평가할 때는 정확도도 중요하지만, 효율성도 중요하다.
효율성은 작업을 완료하기 까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것이다.
이렇게 한 페이지씩 찾아보는 알고리즘은 정확하지만 매우 시간이 오래걸리고 비효율적이다.
- 두 번째 알고리즘
- 전화번호부를 집어 들고 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾는다.
- 없으면 두 페이지 뒤에서 찾는다.
- Mike Smith를 찾을 때까지 또는 전화번호부가 끝날 때까지 이것을 반복한다.
두 번째 알고리즘은 확실히 첫 번째 알고리즘보다 시간이 절반밖에 걸리지 않으므로 효율성은 개선되었을 것이다. 하지만 Mike Smith가 있는 페이지를 그냥 넘어갈 수도 있으니 정확성면에서 떨어진다.
- 세 번째 알고리즘
- 전화번호부 가운데를 펼치고 Mike Smith가 있는지 찾아본다.
- 없다면, 전화번호부가 이름순으로 정렬되어 있으므로 Mike Smith가 앞부분에 있는지 뒷부분에 있는지 보고 책의 절반을 버린다.
- 책의 나머지 절반 부분에서 똑같은 과정을 수행한다.
- 이 과정은 한 페이지가 남을 때까지 계속 수행한다.
세 번째 알고리즘은 앞서 살펴본 두 알고리즘보다 확실히 효율적이다.
만약 1000페이지에 달하는 전화번호부가 있다고 가정해보자.
첫 번째 알고리즘은 1000개의 페이지를 모두 찾아보아야 하고, 두 번째 알고리즘은 500개의 페이지를 찾아보아야 한다.
세 번째 알고리즘은 최악의 경우에도 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 10개의 페이지만 살펴보면 Mike Smith가 있는 위치를 찾을 수 있다.
이렇게 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이다.
의사코드(pseudo code)
위와 같은 세 번째 알고리즘을 우리는 의사코드라는 방식으로 명료하게 정리할 수 있다.
- 전화번호부를 집어든다.
- 전화번호부의 중간을 편다.
- 페이지를 본다.
- 만약에 Mike Smith가 페이지에 있으면
- Mike Smith에게 전화한다.
- 그렇지 않고 만약 Mike Smith가 앞 페이지에 있으면
- 앞 페이지의 절반을 편다.
- 3번째 줄부터 다시 실행한다
- 그렇지 않고 만약 Mike Smith가 뒷 페이지에 있으면
- 뒷 페이지의 절반을 편다.
- 3번째 줄부터 다시 실행한다.
- 그러지 않으면
- 그만둔다.
