[북리뷰] 미래를 바꾼 아홉가지 알고리즘
세상을 바꾼 핵심 기술의 근원을 찾아
스마트폰은 어떻게 우리 얼굴을 인식할까? 인터넷 뱅킹을 이용해 자금이 이체될 때 어떤 과정을 거칠까? 검색엔진은 어떤 기준으로 검색어를 처리해 결과를 출력할까? 아마 누구나 한 번 쯤 이런 궁금증이 있었을 겁니다. 이 책의 저자 맥코믹은 이런 질문들에 대한 답을 찾는 여행으로 우리를 안내해줍니다. 총 9가지의 알고리즘으로 주요 기술들에 대한 해설을 합니다. 알고리즘은 컴퓨터가 문제를 푸는 방법을 말합니다. 같은 수학 문제를 풀더라도 무작정 예제들을 통해 풀이법만 익힌 사람과 풀이법 이면의 이론을 이해한 사람은 전혀 다릅니다. 다양한 응용 문제를 풀거나 새로운 문제 제기를 하려면 이론을 이해해야하죠. 9가지의 알고리즘이 바로 그런 컴퓨터, 인터넷 기술의 작동원리를 소개해 우리가 보다 컴퓨터 기술을 잘 응용할 수 있도록 만들어줄 것입니다.
▣ 디지털 서명 알고리즘
여러분은 컴퓨터를 사용하던 도중에 특정 소프트웨어를 설치하려고 할 때 보안 경고 창이 나타나면서 이 파일을 실행하시겠습니까 라고 묻는 경고를 본적이 있을 겁니다. 이는 컴퓨터가 해당 프로그램를 개발한 회사를 믿을만한 곳인지 사용자에게 신뢰하는지 묻는 절차입니다. 여기에 사용된 것이 디지털 서명입니다. 또한, 웹브라우저에서 https로 시작하는 홈페이지는 디지털 서명을 한 인증서를 우리 컴퓨터에 보내서 안전하다는 것을 상호 검증을 합니다. 우리가 그런 과정을 잘 몰라서 그렇지 이렇게 디지털 서명은 여러 곳에서 사용되고 있습니다.
종이 서명에서는 여러분이 상대방에게 보낼 내용에 서명을 합니다. 반면 디지털 서명은 상대방이 우리에게 내용을 보내기 전에 서명을 하죠. 우리도 모르는 사이에 컴퓨터는 디지털 서명을 자동으로 확인을 합니다. 그렇게 컴퓨터와 인터넷이 동작되는 과정에 자주 사용되는 알고리즘이 디지털 서명입니다.
컴퓨터가 없던 시절을 생각해보죠. 문서를 인증하는 유일한 방법은 종이에 손으로 직접 쓴 서명밖에 없죠. 일례로, 나는 프랑수아즈에게 100달러를 지급하기로 약속한다. 서명, 라비 라고 쓴 종이를 찾았다고 생각해보죠. 이 문서에 라비가 실제로 서명했음을 증명할 수 있을까요? 라비의 서명이 진짜임을 확인할 수 있는 신뢰할만한 저장소가 필요하죠. 실 세계에서는 은행이나 관공서같은 기관이 그 역할을 하죠. 인감도장이나 싸인이 바로 그런 것이죠. 이 기관은 실제 우리의 서명이 저장된 파일을 갖고 있고 필요한 경우 이를 물리적으로 확인해줍니다. 프랑수아즈에게 돈을 주기로 약속한 라비의 서명을 검증하려면 종이 서명 은행에 가서 라비의 서명을 열람하겠다고 요청해야 합니다. 이때 은행을 믿어야 하고, 사기꾼은 라비의 서명을 위조할 수 없어야 한다는 것이 기본 요건입니다. 하지만 현실은 이 요건 중 두번째 서명 위조가 빈번하게 발생하기에 종이 서명이 무용지물이 되는 경우가 많습니다. 반면 디지털 서명은 그렇지 않습니다.
디지털 서명은 자물쇠, 키, 금고라는 3가지 요소가 필요합니다. 라비는 프랑수아즈에게 100달러를 지급하기로 약속한다라는 문서를 만들어 이 문서의 사본을 만들어 금고에 넣습니다. 라비는 상자를 그의 자물쇠로 잠그고 금고를 프랑수아즈에게 줍니다. 바로 금고가 이 문서에 대한 서명인 셈이죠. 만일 금고에 저장된 문서의 내용에 대해 누군가가 거짓이라고 부정하면 프랑수아즈가 이렇게 말할 수 있습니다. “라비, 네 키 하나만 빌려줘, 네 키로 이 금고를 열께” 그 키는 금고의 열쇠이기에 금고를 열고 그 안에 보관된 문서 내용을 보여줄 수 있습니다. 그렇게 문서의 진위 여부를 신뢰하게 되는 것이죠. 그런데 이것이 제대로 작동되려면 금고를 열 수 있는 키를 믿을만한 제 3자 즉 은행에 보관해야 합니다. 문서 인증과 달리 디지털 인증은 문서가 아닌 키를 은행에 보관합니다. 라비가 차용증을 썼다는 사실을 프랑수아즈가 증멸할 필요가 있을 경우 은행에 보관된 키로 금고를 열어보면 되죠.
이같은 간단한 알고리즘이 디지털 서명에 적용되어 컴퓨터, 인터넷의 신원 인증에 이용되고 있는 것입니다. 이 서명이 없었다면 우리가 아는 인터넷 조차 존재할 수 없었을 것입니다. 전 세계의 네트워크에 연결된 컴퓨터들이 상호 데이터를 주고 받는데 있어 인증은 중요하기 때문입니다. 상대의 컴퓨터를 신뢰할 수 있어야 데이터의 전송이 가능하기에 디지털 서명은 인터넷 세상을 만드는데 중요한 역할을 수행해왔습니다. 저자는 컴퓨터 과학에서 가장 훌륭한 성취 중 하나를 이 디지털 서명 알고리즘으로 꼽습니다.
▣ 구글을 일으킨 페이지랭크 알고리즘
검색엔진은 우리 삶에 엄청난 영화를 미쳤죠. 하루에도 몇 번씩 검색어를 입력하면 전 세계의 컴퓨터에서 우리가 찾고자 하는 단어가 들어간 페이지가 수초 아니 1초만에 뚝딱 나옵니다. 이것이 어떻게 가능한 걸까요?
검색은 크게 매칭과 랭킹이라는 2가지 과정으로 운영됩니다. 우리가 런던 버스 시간표라는 검색어를 입력하면 검색엔진이 전 세계의 웹 사이트에서 이 단어가 포함되는 페이지를 찾습니다. 이것을 매칭이라고 하죠. 그렇게 찾은 수 천개의 페이지들 중에서 서열을 매겨 첫 번째부터 마지막까지 적합도에 따라 나열을 합니다. 이걸 랭킹이라고 하죠. 전 세계 최고의 검색엔진은 구글입니다. 구글은 페이지랭크라고 하는 랭킹 알고리즘을 기반으로 성장할 수 있었습니다. 그렇다면 매칭 알고리즘은 누가 선발주자 일까요? 바로 인포시크, 라이코스, 알타비스타입니다. 그중 알타비스타는 구글 이전 1990년대 검색엔진의 왕이었죠. 알타비스타는 웹의 모든 페이지에 있는 텍스트를 인덱싱해서 이를 기초로 매칭을 해주는 알고리즘을 개발한 회사입니다.
그런데, 인덱싱이란 사실 글쓰기만큼 오래된 발상입니다. 5000년 전에 지어진 바빌론 신전 도서관에서도 주제에 따라 설형 문자판을 분류해 놓았던 것을 볼 수 있습니다. 오늘날 인덱스라는 단어는 주로 책 끝에 있는 찾아보기 페이지를 뜻합니다. 동물에 관한 책에 ‘치타 124, 156’ 같은 인덱스는 치타란 단어가 124쪽과 156쪽에 나온다는 뜻이죠. 웹 검색엔진의 인덱스도 이와 같은 방식으로 작동합니다. 다른 점은 그 범주가 전 세계의 웹 사이트로 방대하고, 인덱싱을 통해 결과물을 찾는 속도가 엄청 빠르다는 것이죠.
그런데 이것이 생각보다 복잡합니다. 우리가 검색어를 고양이나 강아지 이렇게 한 단어만 넣는 것이 아니라 두 개 이상의 단어를 넣는 경우도 있기 때문이죠. 예를 들어 볼까요. cat the sat 이라는 3개 단어로 검색을 한다고 해보죠. 그러면 검색엔진은 인덱싱된 내용 기반으로 매칭을 해서 cat이 들어간 1, 3 페이지와 the가 들어간 1, 2, 3 페이지 그리고 sat이 포함된 1, 3 페이지 중에 이 3가지 단어가 모두 포함된 1페이지와 3페이지를 결과로 보여줍니다. 여기까지는 간단해 보이죠. 만일 “cat sat”이라고 두 단어를 인용문구 따옴표로 묶어서 검색하면 어떻게 될까요. 그러면, 두 단어의 순서를 그대로 적용해 cat 다음에 sat이 뒤따르는 페이지만 검색해야 하죠. 이걸 구문 쿼리라고 합니다. 이렇게 연이어서 2개 이상의 단어가 포함된 페이지를 인덱싱하는 것은 기존과 달리 복잡합니다. 그것도 수 천억개의 웹 페이지를 대상으로 해야 하니 더욱더 어려운 것이 사실이죠.
그런데, 더 중요한 것이 남았죠. 바로 랭킹입니다. 사실 검색결과의 정확도는 매칭된 모든 결과물을 보여주는 것이 아니라 실제 내가 필요로 하는 양질의 결과물을 보여줘야 합니다. 즉, 첫 번째 검색 결과 페이지에 소수의 상위 검색결과를 선별하는 랭킹이 중요하다는 것이죠. 검색결과 중 어떤 페이지를 최상위로 올릴 것인가 하는 것은 검색엔진의 품질을 결정합니다. 그런만큼 검색엔진별로 고유한 랭킹 알고리즘을 가지고 있죠. 최강의 검색엔진인 구글은 어떤 랭킹 알고리즘을 가지고 있을까요?
구글의 알고리즘은 페이지 랭크 알고리즘입니다. 스크램블 에그를 만드는데 관심이 많아 이 주제에 관해 검색을 한다고 해보죠. 만일 이 검색어로 검색을 하면 수 백만개의 검색결과가 나타납니다. 이중 어떤 페이지를 최상위로 올려야 할까요. 구글은 검색 결과 중에 하이퍼링크가 가장 많이 걸린 페이지를 상단에 올립니다. 즉, A와 B 결과 중에 A를 2 곳의 웹 페이지들이 하이퍼 링크로 참조하고, B는 7개의 페이지들에서 참조로 링크가 걸렸다면 B를 더 상단에 올리는 것이죠. 그 이유는 더 많은 링크가 걸린 페이지가 일반적으로 더 나은 내용을 담고 있을 확률이 높기 때문이겠죠. 이러한 원리를 기초로 해서 구글의 검색 알고리즘이 만들어졌고 덕분에 검색 품질이 높아 사람들을 만족시켜 지금의 위치에 오른 것이죠. 물론 이것은 페이지 랭크의 기초적 원리이고 권위트릭, 무작위 서퍼 트릭 등 더 복잡한 이론을 접목해 알고리즘을 고도화해서 검색 품질을 높일 수 있었습니다.
▣ 책 한권을 종이 한장에 담기 알고리즘
많은 옷을 작은 여행 가방에 넣으려 할 때 옷의 정상 크기로는 가방에 넣을 수 없으므로 꾹꾹 눌러 담아야 합니다. 그렇게 가방에 압축되어 들어간 옷은 가방을 풀어 헤치면 원래 크기와 모양으로 복원할 수 있죠. 컴퓨터의 파일도 이와 마찬가지로 작은 크기로 압축해서 용량을 줄인 후에 인터넷 망을 통해 전송 후 다시 압축을 풀어 원래의 형태로 이용할 수 있습니다. 실제 전화 통화 중에도 우리의 목소리는 압축된 채 상대방에게 전달됩니다. 목소리 데이터를 압축하면 전화 회사가 자원을 엄청나게 줄일 수 있어 비용을 줄일 수 있죠.
컴퓨터가 이렇게 파일을 압축하기 위해서는 2가지 방식을 이용합니다. 하나는 무손실 압축 다른 하나는 손실 압축입니다. 무손실 압축 알고리즘은 데이터 파일을 압축 이전과 이후가 동일한 파일인데 반해 손실 압축 알고리즘은 압축 해제 후 원본 파일에 약간의 변화가 생깁니다. 두 가지 압축 알고리즘의 방식은 다르지만, 전자의 압축 알고리즘이 어떻게 작동하는지 살펴보겠습니다. 만일 여러분이 주간 일정을 상대방에게 전달한다고 생각해보죠. 주 5일 일 8시간씩 일정이 나뉜 일정표를 가정해보면 총 40개의 칸이 있는 셈이죠. 이 일정을 전달하려면 40개의 칸을 전달하게 됩니다. 그런데, 만일 상대와 스케줄을 정하고자 할 때 40개 전부를 전달하지 않고 비어 있는 일부 칸만 전달해서 어떤 일정에 만날지를 정합니다. 즉, 40개 칸 중에 비어 있는 3개의 칸을 전달해서 날짜를 정하겠죠. 바로 이게 무손실 데이터 압축 알고리즘입니다. 이 간단한 원리로 파일의 압축이 이루어지죠.
좀 더 자세하게 컴퓨터의 압축 알고리즘을 설명하면 이렇습니다. AAAAABBBCCCC 이런 정보가 컴퓨터에서 압축이 된다고 하면 A5B3C4 이렇게 저장되는 것이죠. 원본은 12개의 단어이지만 압축된 것은 6개입니다. 단어수가 길고 반복되는 단어가 많으면 그만큼 압축도 잘 되는 것이죠. 이 간단한 알고리즘에 의해 우리의 컴퓨터 저장 장소와 인터넷 전송에 있어 획기적인 자원 절약이 가능해진 셈입니다.
이렇게 책에서는 아홉가지의 주요 알고리즘들을 소개하고 있습니다. 이들 알고리즘 덕분에 컴퓨터, 인터넷 기술이 진화될 수 있었고 우리 삶이 더 나아질 수 있었습니다. 이들 알고리즘을 보면 그 기초 원리가 우리의 삶과 역사에서 참고한 것이 대부분입니다. 또, 앞으로 새로운 알고리즘이 새로운 기술을 탄생시키고 우리 사회를 변화시키겠죠. 그런 알고리즘은 다양하게 응용되어 우리 기업의 비즈니스에도 적용될 수 있을 것입니다. 알고리즘의 시작은 작은 아이디어에서 비롯됩니다. 또한, 알고리즘의 이용은 그 원리를 이해하는데서 시작됩니다. 아홉 가지의 알고리즘에 대한 이해를 기반으로 우리 사업에 어떻게 응용할 수 있을지 고민해보면 어떨까요.
위 북리뷰는, 고전5미닛(약 5분으로 정리된 책의 시사점을 정리하는 책리뷰 전문 사이트)를 위해 제작된 초본으로 보다 정돈되고 통찰력있게 내용을 정리한 내용은 고전5미닛을 참고하세요.
