미래를 바꾼 아홉 가지 알고리즘: 컴퓨터는 어떤 식으로 문제를 푸는가?

by SL

이런 말이 있다.

Computer science is no more about computers than astronomy is about telescopes.

Computer Science를 컴퓨터 과학이라고 옮겨야 할지 전산학이라고 해야 할지 모르겠지만, 아무튼 이 학문이 컴퓨터라는 기계 자체에 대한 것이라는 생각은 오해라는 얘기다. 비교하자면 천문학이 망원경에 대한 학문이 아닌 것과 마찬가지라는 것. 물론, 현대적인 컴퓨터의 동작 원리를 이해하고, 보다 빠르고 강력한 머신을 만드는 일도 중요하지만 그게 전부는 아니다. 또, 소프트웨어 개발을 빼놓고 얘기할 수 없지만 그렇다고 프로그래밍이 곧 컴퓨터 사이언스인 것은 아니다. 그럼 대체 뭔가?

이럴 때는 엄밀한 정의보다 실제로 컴퓨터 사이언스를 하는 사람들이 어떤 문제와 씨름하고 어떤 식으로 해결해왔는지를 살펴보는 게 더 도움이 된다. 『미래를 바꾼 아홉 가지 알고리즘: 컴퓨터 세상을 만든 기발한 아이디어들 (원제 Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today’s Computers)』 책에 나오는 예를 하나 살펴보자.

작은 방 안에 3명이 있다. 각자는 다른 누군가에게 귓속말을 하거나 쪽지를 보낼 수 없고, 반드시 모두가 들을 수 있게 큰 소리로만 말해야 한다. 이런 상황에서 두 명이 비밀 대화를 나누려면 어떻게 해야 할까?

비현실적인 설정에 답이 없는 문제처럼 보인다. 하지만 이건 우리가 매일 인터넷에서 맞닥뜨리는 현실이다. 내가 다른 컴퓨터로 보내는 메시지는 누구나 열어볼 수 있다. 그런데 나는 종종 신용카드번호처럼 민감한 개인정보를 인터넷을 통해 보내야 한다. 암호화를 하면 되지 않냐고? 내가 처음 방문한 쇼핑몰에서 주문할 때, 메시지를 암호화해서 보내면 그 사이트가 어떻게 메시지를 해석할 수 있을까?

얼핏 평범해 보이는 문제도 컴퓨터 세상에서 만나면 인간 세상에서와는 다른 제약과 가능성을 가지게 된다. 귓속말도 못 하는 답답한 컴퓨터지만 알고보면 암기와 계산에는 이골이 난 천재다. 이런 특성을 이용하면 위의 문제는 공개키(Public Key)를 통해서 두 사람이 공유하는 비밀(Shared Secret)을 만드는 방식으로 해결할 수 있다.

컴퓨터 사이언스 박사학위를 가지고 있는 저자는 이 책에서 나름의 기준으로 선정한 8가지 알고리즘과, 그 잘난 컴퓨터도 (또한 사람도) 계산할 수 없는 문제를 소개한다. 목차에도 나오지만, 검색엔진이 문서를 색인하는 방법, 웹의 링크 구조를 이용해서 사이트의 인기도/품질/권위를 정량화하는 방법, 데이터가 유실/변경될 수 있는 통로에서도 오류없이 통신하는 방법 등이다.

이 책에서 인상적인 부분은 독자가 각각의 아이디어를 실제로 “이해”하는 것을 목표로 설명한다는 점이다. 문제의 배경과 필요성, 해결 아이디어까지는 쉬운 말로 설명하다가 구체적인 방법은 건너뛰는 경우도 많은데, 여기서는 전문적인 내용은 최대한 빼고 복잡한 과정은 단순하게 만들어서, 컴퓨터 전공자가 아니더라도 알고리즘의 핵심인 실제 동작 과정을 맛볼 수 있도록 했다.

바로 여기서 저자 특유의 직관적이면서도 핵심을 찌르는 비유가 빛을 발한다. 압권은 역시 공개키 알고리즘의 페인트 은유라고 생각하지만, 군데군데서 크고작은 비유가 독자의 이해를 돕는다. 이를 따라가다 보면 추상적으로만 보였던 알고리즘이 사실은 실제 세상의 직관과 통찰에 착안한 점도 많다는 것을 알게될 것이다.

알고리즘이 지배하는 세상에서 살아가는 사람이라면 컴퓨터 전공 여부와 상관없이 누구나 읽어볼 만한 책이다. 장담하는데 진짜로 어렵지 않다.

노란 형광펜

  • 수학과 물리학 같은 일반 과학 분야에서 중요한 결과는 대개 하나의 공식으로 포착된다. 이와는 대조적으로 컴퓨터과학에서 위대한 아이디어는 일반적으로 (물론 알고리즘을 이용해) 문제를 푸는 방법을 기술한다., 22p
  • 패턴 인식 알고리즘이 실패한 사례를 검토하는 일은 늘 매력적이며 이 신경망도 예외는 아니다., 163p (확실히 그렇다. 그리고 실패한 케이스를 보면서 더 많이 배운다.)
  • 좋은 압축 알고리즘은 비효율적 유형의 리던던시를 제거하고 오류 정정 인코딩은 이와 다른 더 효율적 유형의 리던던시를 더한다. (중략) 파노는 MIT에서 정보이론 대학원 강의를 시작했고 학기말 논문 주제 중 하나로 ‘최적의 압축을 달성하는 법’이라는 문제를 제기했다. 놀랍게도 그의 학생 중 하나가 이 문제를 풀었고 개별 심벌에 대한 최적의 압축을 산출하는 방법을 만들었다. 이 학생이 데이비드 허프만이고 그의 기법은 더 짧은 심벌 트릭의 또 다른 예다., 189p
  • RSA가 정말로 안전한지에 관한 사안은 컴퓨터과학 전체에서 가장 흥미로운(그리고 성가신) 질문 중 하나다. 이런 이유 중 하나는 이 질문이 고대의 풀리지 않은 수학 문제인 소인수분해와, 최근의 물리학과 컴퓨터과학 연구 간 교차점에 있는 관심 주제인 양자 컴퓨팅에 모두 의존한다는 점이다., 252p