속도 < 방향

합병 정렬은 버블 정렬, 선택 정렬, 삽입 정렬보다 훨씬 빠르고 간결하고 깔끔하게 표현할 수 있다.

합병정렬의 시간복잡도 상한선은 $nlogn$이다. 다른 정렬의 최소 상한선은 $n^2$이고, 이는 $nlogn$보다 크다. 합병정렬은 시간적으로 빠르지만 단점도 존재한다.

합병 정렬은 더 많은 공간(메모리)을 사용한다. 

8개의 자료가 있다고 하면, 세 번을 나눈다. $log28$은 3이다. 그리고 그 한번을 실행할 때마다 자료를 n번씩 봐야했기 때문에 $nlogn$으로 표현할 수 있다. 합병 정렬은 병합하는 알고리즘을 포함한다.

실행시간으로 표현을 한다면, $T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + O(n) $ 이 될 수 있다. 각 $ T(\frac{n}{2}) $는 왼쪽과 오른쪽 절반에 해당하고, $O(n)$ 은 자료를 비교하는 n 단계를 나타낸다.

이진탐색

전화번호부 예시처럼 봐야하는 데이터의 목록이 점점 작아지도록 계속해서 절반으로 나누는 알고리즘의 시간복잡도는 $logn$이다. $logn$에서 실행하는 알고리즘의 세부 조건은 알고리즘 입력 목록이 정렬되는 것을 가정해야 한다.

이진 탐색을 일반적으로 선형 탐색보다 속도가 빠르지만, 배열을 정리하는 시간이 추가되기도 한다.

보고정렬: 무작위하게 섞고 정렬되었나 확인하는 것인데 이러한 정렬의 경우엔 최악의 경우 무한대가 될 수도 있다.

각 정렬을 big-O 시간복잡도와 big-Ω 시간복잡도로 나타내면 위와 같다.

컴퓨터는 우리가 컴퓨터에 입력한 자료를 컴퓨터의 처리과정을 통해 출력 형태로 만든다. 즉 명령어들의 순서상 처리가 필요한데 이를 알고리즘이라고 한다. 마치 우리가 아침에 일어나서 양치하고, 밥을 먹고 옷을 입고 외출하는 과정처럼 순서대로 행동이 이루어지는 것과 비슷하다. 어떤 문제를 단계적으로 풀어가는 명령어의 집합이다.

하지만 순서를 잘못 놓는다든가, 비효율적으로 한다면 준비하는 데 시간이 오래 걸릴 것이다. 그래서 효율적으로 움직이기 위해 외출 경로를 바꾼다든가 하는 선택을 하는데, 알고리즘도 마찬가지이다. 알고리즘이 효율적으로 작동하도록 배열한다면 시간과 공간적으로 훨씬 여유있게 명령어가 작동될 수 있을 것이다.

좋은 알고리즘은 효율성이 좋은 알고리즘이다. 

Pseudo Code 수도코드는 알고리즘이나 컴퓨터 프로그램을 C, C++, Java 등의 프로그래밍 언어를 사용하지 않고 표현하는 방법이다. 사람이 쓰는 데 익숙한 언어(영어)를 사용하는데, 이를 통해 알고리즘을 짤 수도 있다. 중요한 것은 알고리즘을 설계할 때, 모든 경우의 수를 고려해야한다는 것이다. 

전화번호부에서 Mike Smith를 찾을 때의 알고리즘을 수도 코드로 표현한다면 위와 같은 알고리즘으로 진행될 것이다.

우리는 소프트웨어를 작동하거나 컴퓨터 언어(프로그래밍 언어) 를 통해 컴퓨터와 상호작용을 하지만, 인간은 일상에서 컴퓨터 언어가 아닌 언어를 사용한다. 이것을 자연어 라고 부르는데, 컴퓨터가 이를 이해하도록 만들려면 자연어를 이해할 수 있도록 처리해야 한다.

가장 최초의 자연어 처리 프로그램은 1966년 조셉이 만든 ELIZA 라는 소프트웨어이다. ELIZA에서 사용하는 시스템을 패턴 매칭 (pattern matching) 이라고 하는데, 입력 받은 문자의 일부를 활용해 다시 사용자에게 반환해주는 시스템을 의미한다. 요즘은 이러한 시스템을 활용하여 구현된 챗봇을 쉽게 만날 수 있다.

사람의 언어를 기계적으로 분석하여 컴퓨터가 이해할 수 있는 형태로 바꿔 처리하는 것을 자연어 처리라고 한다. 또, 단어들의 순서나 한 단어 뒤에 다른 단어가 나올 확률 등을 확률적으로 계산하여 시스템에 반영할 수 있다.

요즘 대부분의 운영체제에는 음성인식 소프트웨어가 탑재되어 있다. 예시로는 iOS의 Siri, 삼성의 빅스비 등이 있다. 이러한 소프트웨어들은 가장 아래에 음성모델, 중간에 발음모델, 그 위에 언어모델을 넣어 이루어진다. 이렇게 여러 층으로 이루어진 소프트웨어로 음성을 인식하고, 인식된 문자를 또 다시 몇 개의 층으로(단계로) 분석한다. 

Syntactic Processing, Semantic Processing, Pragmatic Processing

문장을 인식했다면, 처음엔 그 문장의 구조를 분석하고 각 단어의 의미처리를 한다. 하지만 이 단계는 인간의 말을 그대로 이해하는 것이 아닌, 상징적인 것으로 앞에서와 마찬가지로 단어와 단어의 구조를 패턴화하고 확률적으로 구하는 것이다. 문장이 실제로 어떤 의미를 뜻하는지 인식하기 위해서는 더 복잡한 인지 모델이 필요하다. 

우리가 소통하는 요소 중 많은 부분을 차지하는 것이 비언어적 소통이다. 단순히 텍스트만으로 소통하기보다는 물리적 거리, 바라보는 시선, 목소리 톤, 억양, 제스처 등이 함께한다. 위에서 언급한 음성인식 시스템은 이러한 부분까지 고려할 수 없지만 비 언어적 행동까지 커버하는 카메라가 달린 로봇(지보)도 있고, 세상은 조금씩 발전하고 있다.

인공 지능을 구현하기 위한 하나의 분야로, 컴퓨터가 많은 데이터를 스스로 학습하고 그 데이터의 패턴을 파악할 수 있도록 하는 것이다. 일상에서 쉽게 사용할 수 있는 머신 러닝 시스템으로는 스팸 메일 분류기가 있다. 이러한 패턴을 잘 파악하기 위해서는 많은 양의 데이터가 필요하다.

우리는 일상에서 쉽게 가상 현실(VR, Virtual Reality) 과 증강 현실(AR, Augmented Reality)을 접한다.
VR은 가상의 환경이나 상황을 컴퓨터로 만들어서 사람들이 실제로 그 상황에 들어와있는 것 처럼 느끼고 상호 작용할 수 있도록 만들어 주는 인터페이스를 뜻한다. AR은 가상현실과 기본적으로 비슷한데, 사용자에게 기존의 주변환경과 분리된 전혀 다른 환경을 경험하게 하지 않고 현재의 환경 위에 영상, 게임 등의 효과를 입히는 기술이다. 

간단한 형태로는 휴대폰을 통해 유튜브나 페이스북으로 3차원 공간을 둘러볼 수 있는데, 네모난 액정 안에 3차원 공간이 다 담긴다. 혹은 구글 카드보드나 삼성 기어, 오큘러스의 리프트, HTC의 바이브 등의 헤드셋을 통해 가상 세계로 갈 수도 있다. (논외지만 가상 현실 세계는 무궁무진하게 커질 것이라 생각해서 나는 카메라 기업들의 산업을 긍정적으로 투자해놨다.)

이러한 기술의 실질적인 목표는 강의실 혹은 해당 공연장에 하나의 창을 만들어서 공간에 없는 사람이라도 멀리서도 그 창을 통해 수업 혹은 공연을 들을 수 있게 하는 것이다.

원리

인간이 눈으로 보이는 것들을 입체적으로 느낄 수 있는 이유는 양쪽 눈의 시차가 있기 때문이다.  우리의 양 눈은 서로 떨어져있기 때문에 각각 보는 각도가 달라, 양안시차가 발생하기 때문에 원근감을 느끼고 물체를 입체적으로 인식할 수 있다.

이 원리를 이용하여 VR기기의 양 렌즈에는 사람의 양안 시차만큼 다른 각도로 촬영된 영상이 재생되기 때문에 일반 디스플레이에서 영상을 보는 것과 달리 입체감이 느껴지는 것이다.

또한 사람이 바라보는 방향에 따라 영상을 바꾸기 위해서 모션 트래킹 센서라는 것이 사용된다. 머리에 씌워진 기기 안에 가로, 세로, 높이를 모두 측정하는 센서가 있어 고개를 돌릴 때 마다 영상 화면도 같이 움직일 수 있다.

이 각각의 센서와 이미지를 활용하여 소프트웨어를 활용해 통합, 사용자가 보는 화면에 제공하여 입체감을 함께 느낄 수 있도록 하는 것이다. 보통 이러한 것을 체험하기 위해서는 AR 혹은 VR 기기를 사용하는데, 우리가 세상을 바라보는 눈으로 보면 마치 볼록렌즈처럼 왜곡되어 보이기 때문이다. 해당 기기를 사용해야만 소프트웨어와 연동이 되어 마치 가상현실을 진짜처럼 바라볼 수 있는 것이다.

가상 현실(VR)과 함께 가상의 정보를 이용한 기술이 증강 현실(AR)이다. 가상 현실과 증강 현실을 혼동하는 경우가 많은데, 가상현실은 가상의 환경에서 가상의 물체와 상호작용 하는 반면에, 증강현실은 현실의 환경에서 가상의 이미지가 겹쳐서 보여지는 것 이다.

AR은 스마트폰과 같이 카메라와 디스플레이가 함께 있는 기기가 필요하다. 카메라를 통해 사람의 시선이 닿는(카메라 렌즈를 통해 들어오는 화면) 장면이 기기에 들어오고 디스플레이에서 출력될 때 가상의 이미지가 덧붙여서 보이게 된다. AR 역시 VR과 마찬가지로 사람의 시선(카메라의 위치)를 계산하기 위하여 위치와 기울기를 측정하는 센서가 필요하다.

실제로, 이집트의 피라미드에서는 이 기술을 활용하여 그 곳까지 가지 못하는 사람들에게 가상 환경을 통해 경험할 수 있는 서비스를 제공한다고 한다. 이제는 우리가 접할 수 있는 구글맵의 거리뷰(로드뷰) 또한 3D 기술을 통해 구현된 것이다.

추리물을 좋아하는 사람이라면, 혹은 소싯적 TV 프로그램을 많이 봤다면 누구나 아는 프로그램이 있다.

바로 CSI 프로그램이다. 해당 프로그램에서 자주 나오는 화면이 영상을 멈춰서 확대하는 장면이다.

위의 이미지를 확대하면,,?

현실은 다르다. 한정된 비트들로 이루어진 이미지를 확대하면 이렇게 이미지가 번지거나 깨지는 현상을 볼 수 있다. 이런 현상이 발생하는 이유는 무엇일까?

우리가 컴퓨터와 해온 상호작용들은 대체로 모니터, 키보드, 마우스 등으로 이루어졌다. (물론 사람마다 다르겠지만) 하드디스크나 파일과 상호작용을 하는 빈도는 비교적 적다. 

'파일'은 무엇일까? 위의 사진은 'JPEG'의 확장명을 가지고 있는데, 이러한 파일들은 특정 비트 패턴으로 식별된다.  JPEG, GIF, PNG, WORD, EXCEL 파일 간에 구분되는 점은 무엇일까? 서로 다른 비트 패턴을 사용한다는 것이다. 그러한 비트 패턴들은 보통 파일 초반부에 있다. 

우리가 컴퓨터에서 JPEG 파일이나 워드 문서를 열면 대체로 파일의 첫 비트들을 본다 만약 그 패턴을 인식하여 이미지라는 것을 알면 사용자에게 그래픽으로 보여준다. 만약 그 패턴이 doc 형식이라면 문서형식을 보여줄 것이다.

이미지

우리가 사진을 찍어 이미지에 저장하면 보통 JPEG라는 확장자를 가지며 이미지를 압축하여 저장한다. 이미지 파일 형식으로는 비트맵(.bmp), JPG(.jpg), PNG(.png), GIF(.gif) 등이 있다. 각 유형에는 장단점이 있으며 유형에 따라 파일의 크기도 달라진다. 즉, 파일의 비트 데이터들의 구조가 다르다.

예를 들어 JPEG 확장자를 가진 파일의 첫 부분에는 256 216 255 의 숫자로 시작한다. 

비트맵 (BMP) 파일 형식의 경우 압축을 하지 않고 저장을 하며 이미지를 가장 단순하게 저장한다.

JPEG 파일은 이미지를 압축하는 장점을 갖고 있으며, GIF 파일이 256색을 표시할 수 있는데 비해 JPEG는 1600만 색상을 나타낼 수 있어 고해상도를 나타내기에 적합합니다. GIF는 이미지의 전송을 빠르게 하기 위한 압축저장 방식을 사용합니다. JPEG보다 압축률은 낮지만 압축 시 이미지의 손상이 적다.

PNG는 GIF와 JPEG의 장점만을 합쳐 놓은 압축방식이다. GIF보다 압축률이 좋고 JPEG보다 원본에 손상이 적어 효과적이다.

사진 파일의 확장명인 jpg(jpeg)를 아는가? 모든 JPEG 파일의 첫 3byte는 이렇게 시작한다. 하지만 이렇게 10진수, 2진수만 사용하지는 않고 대체로 16진수 (hexadecimal) 를 사용한다. 0~9 다음부터 10~15의 숫자는 a,b,c,...f 등 알파벳으로 표현한다.

 

위의 숫자들을 2진수, 16진수로 나타내면 8bit 였던 걸 2bit로 구현할 수 있다.

하지만 ff, d8, ff 등으로 표현하지는 않고 16진수를 사용할 때는 관례적으로 빈 공간에 0x라는 것을 앞에 넣어서 위와 같은 표현으로 나타낸다.

16진수가 유용한 이유는 4bit 패턴과 완벽한 대응을 하기 때문이다. (2의 4제곱). 이를 활용하여 8bit나 1byte 등을 표현하기 용이하다. 실용적이다 ^ㅡ^

---

● ASCII 코드

컴퓨터가 숫자가 아니라 문자나 다른 것들을 나타내기 위해 하는 것이 있을까? 컴퓨터 업계에서는 숫자를 알파벳 문자에 대응시키는 표준 방법을 채택하였다. ASCII 는 아스키라고 읽으며 글자를 10진수로 대응하는 것이다.

우리가 '문자'를 표현하고 싶지만 컴퓨터는 '숫자'로만 언어를 처리하기 때문에 숫자를 글자로 변환하려면 비트 패턴으로 변환이 필요하다. 그럴 때 사용하는 것이 ASCII 코드이다. 알파벳 'A'는 65로 시작하는데, 2의 6제곱인 64까지 표기를 하고 그 이후에 시작하는 순서이다. 

예를 들어 HI 라고 쓰고 싶다면, ASCII 코드로 숫자 72와 73을 나타내는 비트 패턴으로 전기신호를 보내 저장한다. 비단 문자뿐만 아니라 그래픽, 영상, 음악 등 다양한 것을 저장할 수 있다.

일상생활에서는 일반적으로 10진수(decimal)를 사용한다. '10'이라고 하는 이유는 0에서 9까지의 숫자 10개를 사용하기 때문이다. 2진수(binary)는 0과 1까지의 숫자 2개만을 사용한다. 컴퓨터는 0과 1만으로도 어떤 데이터든 충분히 표현할 수 있다. 숫자, 문자, 그래픽, 영상 등 모든 정보가 가능하다. 

우리가 위의 그림을 본다면 본능적으로 1,2,3 숫자 3개로 인식할 것이다. 왜냐하면 우리가 어릴 때 숫자를 배울 때 10 단위로 생각하도록 배웠기 때문이다.

하지만 사실은 이렇게 각 자리수에 스케일을 곱해서 나온 결과 값을 모두 더한 것이다. 컴퓨터도 2진수를 사용할 때 우리와 같은 언어를 사용한다. 다만 우리보다 숫자 갯수가 적을 뿐이다. 우리는 10진수로 계산하기 때문에 10개의 숫자를 사용하지만 컴퓨터는 2개만 사용한다, 우리가 각 자리수에 10의 제곱을 하듯 컴퓨터는 2의 제곱을 통해 계산한다.

이처럼 각자 사용하는 진수에 따라 표현방식이 다르지만, 모두 같은 숫자를 나타냄을 알 수 있다. 

우리는 방의 불을 끄거나 켤 수 있다. 이것을 어떻게 표현할까? API라는 것을 통해 표현할 수 있다. API는 Application Programming Interface의 약자다. 우리가 웹 서버로 메시지를 보내듯 API를 통해 메시지를 보낼 수 있다.