피보나치와 황금비

기원전 250년 이전에 인도에서 아랍에 전래, 1200년경 유럽에 소개
⊙ 꽃잎의 잎차례, 주식시장의 파동, 피라미드, 유엔본부 등 다양한 곳에서 발견
⊙ 입술에서 코끝까지의 길이, 코끝에서 두 눈의 중점까지의 길이가 황금비인 1대 1.618에
    가까울수록 미인에 가까워

꽃잎이 5개인 무궁화와 8개인 코스모스. 꽃잎의 수는 대개 피보나치 수열에 있는 수를 가지고 있다.

  길을 가다가 꽃을 보고 ‘아름답다’고 느낀 적이 있을 것이다. 꽃에 아름다운 것 이외에 또 다른 특징이 있을까? 꽃잎을 자세히 보면 특징이 있음을 발견할 수 있다. 바로 대부분의 꽃잎은 3장, 5장, 8장, 13장으로 되어 있다는 것이다. 길을 걷다가 혹은 산에서 꽃을 본 기억을 다시 떠올려 보면 4장, 6장의 꽃잎을 가진 꽃이 거의 없음을 알 수 있다.
 
 
  11235
 
  1 1 2 3 5 8 13 21 43
 
  언뜻 보기에 어느 복권의 당첨번호처럼 나열된 수들. 이 수들은 무려 기원전 250년 이전에 인도에서 아랍으로, 더 널리 서양으로 퍼져 많은 사람의 관심을 끌어 왔다. 과연 이 수들에는 어떠한 매력이 담겨 있기에 이토록 오랜 세월에 걸쳐 많은 이의 관심을 끌어 왔을까?
 
  이탈리아의 한 수학자인 피보나치는 아랍에서 수학을 배운 후에 서양에 아라비아 수학을 알리기 위해서 1200년경 《Liber Abaci》라는 책을 썼다. 이 책에는 재미있는 토끼이야기가 있는데 이 책으로 피보나치 수열이 서양에 알려지게 되었다.
 
  이 책에 있는 토끼이야기는 토끼 수에 대한 문제로서 문제의 조건은 첫 달은 새로 태어난 한 쌍의 토끼만 존재하며, 두 달 이상이 된 토끼는 번식한다. 그리고 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳으며, 토끼는 죽지 않는다. 따라서 첫 달에는 토끼 한 쌍만이 존재한다. 두 번째 달에도 토끼는 한 쌍만이 있다. 세 번째 달부터는 이 토끼 한 쌍이 새끼를 낳기 때문에 토끼는 2쌍이 존재하게 된다. 네 번째 달에는 3쌍, 다섯 번째 달에는 5쌍이 된다. 그 다음에는 8쌍, 13쌍 21쌍으로 늘어나게 된다. 어떠한 규칙이 발견되는가? 바로 앞의 2개 숫자를 합하면, 그 다음의 숫자와 같아지게 된다.
 
  하지만 이 토끼 이야기는 실제로는 일어날 수 없는 이야기이다. 왜냐하면, 토끼는 절대 죽지 않으며, 매달 한 쌍의 토끼가 나온다는 조건 때문이다. 그럼에도 불구하고 이 수 규칙은 우리 주변에서 많이 발견되고 있다.
 
 
  식물에서 보는 피보나치의 수
 
  앞에서 본 꽃이 가지고 있는 잎의 수는 대부분 피보나치 수열에 있는 수를 가지고 있다. 이외에도 식물에서 또 찾을 수 있는 것이 있을까? 식물의 줄기에 붙어 있는 잎의 배열 방식인 ‘잎차례’에서도 피보나치 수를 찾을 수 있다. 식물의 잎은 아래쪽에서부터 줄기를 따라 위쪽으로 회전하면서 나선형으로 붙어 있다. 이때 처음의 잎과 같은 방향을 이루는 잎이 등장할 때까지 회전수(t)와 잎의 수(n)를 세어 t/n형태로 잎차례를 표현하는데, 예를 들어 3번의 회전을 하는 동안 5개의 잎이 만들어지면 3/5잎차례라 할 수 있다. 벚꽃과 사과는 2/5잎차례를 가진 식물이고, 갯버들은 5/13잎차례를 가진 식물이며, 전체 식물의 약 90%가 피보나치 수의 잎차례를 따르고 있다.
 
  그렇다면 식물이 피보나치 수를 따르는 이유는 무엇인지 알아보자. 예를 들어, 잎차례가 120°간격으로 배열되어 있다면 어떻게 될까? 아마 360° 회전할 때마다 잎이 같은 선상에 위치하게 되므로, 위에서 보았을 때 모양이 겹쳐서 보이게 된다. 그렇게 되면 위에 있는 잎만 햇빛을 많이 받게 되고, 아래에 있는 잎들은 햇빛을 잘 받지 못하게 된다. 하지만 피보나치 수 잎차례를 따르는 식물들은 잎이 바로 위의 잎에 가리지 않고 햇빛을 최대한 받을 수 있기 때문에 식물의 생장에 유리하다.
 
 
  주식시장에도 피보나치 수가 있다
 
  피보나치 수가 자연에만 있는 것은 아니다. 아침에 시작하는 전쟁터인 주식시장에서도 발견된다. 엘리엇(Elliot)은 주식시장의 변동을 월간, 주간, 일간, 시간, 심지어 30분 단위까지 세밀하게 나누어 연구하였다. 그가 발견한 것은 크게 8개의 파동을 한 주기로 움직이며, 이 8개의 파동은 상승하는 5개의 파동과 하락하는 3개의 파동으로 이루어진 것을 발견하였다. 그런데 상승하는 5개의 파동은 상승만 하는 것이 아닌 올라가는 3개의 파동과 내려가는 2개의 파동으로 되어 있으며, 하락하는 3개의 파동도 올라가는 1개의 파동과 내려가는 2개의 파동으로 되어 있는 것을 알게 되었다. 더 큰 흐름에서 보면 상승하는 21파와 하락하는 13파로 전체 34파의 파동을 볼 수 있다. 여기에서 볼 수 있는 수 모두 우연의 일치라고 하기에는 너무 딱 맞도록 피보나치 수로 되어 있다.
 
 
  피보나치 수에서 발견되는 아름다움
 
  위의 사각형들 중에서 가장 보기 좋은 사각형을 고르라면 몇 번을 고를까? 개인에 따라 차이가 있을 수 있지만 아마 대부분은 ④번 사각형을 골랐을 것이다.
 
  독일의 심리학자 구스타프 페히너는 여러 모양의 사각형을 가지고 사람들에게 아름다운 사각형을 고르게 하였다. 이 실험에서는 약 10개의 사각형을 가지고 조사를 하였는데, 30% 넘는 사람이 ④번과 같은 사각형을 선택하였다. ④번 사각형은 가로와 세로의 비가 21 대 34인 피보나치 수로 이루어진 사각형이다. 아름다움이 피보나치 수에서 발견되는 가장 큰 이유는 이웃하는 두 수 사이의 비에 있다. 피보나치 수열에서 연속하는 두 수의 비는 피보나치 수가 커질수록 1.618에 점점 가까워지는 것을 볼 수 있다. 이러한 비율을 가진 것들은 안정감이 있고 미적으로도 아름다워 보인다고 한다. 이러한 1 대 1.618의 비를 ‘황금비’라 부른다.
 
 
  의도하거나 본능이거나
 

피라미드에서 옆면을 이루는 삼각형의 높이와 밑면인 정사각형의 한 변의 길이의 절반의 비율이 황금비를 이루고 있다.

  다음 건축물들의 공통점은 무엇일까? 이미 눈치챘겠지만 두 건축물 모두 ‘황금비’와 연관이 있다. 프랑스의 건축가 르 코르뷔지에(Le Corbusier)는 현대 건축 디자인에 큰 영향을 끼친 인물로, 그의 작품인 유엔본부 건물을 보면 건물의 폭과 높이의 비가 약 1 대 1.618을 이루며, 다른 작품들에서도 의도적으로 황금비를 이용하여 안정감 있는 건축물을 디자인하였다. 이처럼 황금비를 미적 안정감으로 사용한 사례도 있지만 그 반대인 경우도 있다.
 
  이집트에 있는 피라미드는 엄청난 규모뿐만 아니라 매우 정교한 정사각뿔 모양을 하고 있기에 세계 7대 불가사의 중 하나로 꼽히고 있다. 피라미드에서 옆면을 이루는 삼각형의 높이와 밑면인 정사각형의 한 변의 길이의 절반의 비율이 황금비를 이루고 있다. 또한 B.C 400년경에 건축된 아테네의 파르테논 신전 외부 모양을 사각형으로 그리면 가로와 세로의 비가 황금비를 이루는 것을 볼 수 있다. 이러한 건축물들은 아름다운 건축물을 만들기 위해 노력하였고, 의도치 않게 황금비가 사용된 것이다.
 
  황금비는 건축뿐만 아니라 여러 분야에서 사용된다. 많은 사람이 아름다운 조각상으로 생각하는 밀로의 비너스상이 있다. 미술평론가들은 밀로의 조각상이 안정감이 있다고 말하는데 그 이유는 조각상이 황금비를 이루고 있기 때문이다. 배꼽에서 목과 목에서 머리끝의 비, 무릎과 무릎에서 배꼽의 비가 모두 황금비를 이루고 있다. 또한 황금비를 음악에서도 찾을 수 있다. 곡이 매끄럽게 전개되기 위해서 곡을 대표하는 클라이맥스를 적절한 위치에 배치한다. 베토벤의 교향곡 제5번 ‘운명’에서는 첫 악장을 시작하는 5마디는 이 곡을 대표하는 멜로디로서 앞의 377소절과 뒤의 233소절 사이에 다시 한 번 등장한다. 이 377과 233은 피보나치 수열에서 14번째, 13번째 수로, 이 멜로디에 의해 전체 악장이 황금비로 나뉘고 있다.
 
 
  우리 몸에서의 황금비
 
  중국의 양귀비, 미국의 마릴린 먼로의 공통점은 무엇일까? 두 여인 모두 그 시대에서 미녀로 손꼽히는 이들로 얼굴에서 더욱 특별한 공통점을 찾을 수 있다. 바로 얼굴에 황금비가 숨어 있기 때문이다. 입술에서 코끝까지의 길이, 코끝에서 두 눈의 중점까지의 길이가 황금비인 1 대 1.618에 가까울수록 미인에 가깝다고 한다. 사람의 외적인 모습뿐 아니라 우리 몸 안에서도 황금비는 나타난다. 우리 몸은 유전정보를 가지고 있는 DNA로 구성되어 있다. 이 DNA의 구조는 이중나선 구조로 되어 있는데, 이 DNA사슬의 폭은 21(angstrom, 1억분의 1cm)이며, 나선이 완전히 한 번 회전하였을 때의 길이가 34이다. 21과 34는 피보나치에 나오는 수로서 비율은 1.619로 황금비와 비슷하게 나타난다. 또한 건강한 사람의 최대 혈압과 최소 혈압의 비율이 1 대 1.618로 일정하게 나타나며 심근경색 위험이 적다는 연구결과도 있다.
 
 
  아름다운 나선
 

각 단계에서 생긴 정사각형에 내접하는 사분원을 그려 생긴 나선을 황금나선이라고 한다.

  직사각형에서 만들 수 있는 가장 큰 정사각형을 잘라내고 남은 직사각형이 처음 직사각형과 닮은 도형인 사각형을 황금직사각형이라고 한다. 이 황금직사각형은 이름에서 나타나듯이 황금비를 이루고 있다.
 
  가로를 χ 세로를 1이라고 하였을 때(χ〉1), 가장 큰 정사각형은 길이가 1인 정사각형이다. 이를 자르고 남은 직사각형의 긴 변은 1이 되고, 짧은 변은 χ-1이 된다. 이때 처음 직사각형과 닮은 모양이기 때문에 「χ : 1=1:χ -1」인 식이 나오게 되며 χ 2-χ -1=0이란 방정식에서 χ 값을 구하면 =1.618033…이 나오게 된다. 황금직사각형에서 정사각형을 잘라내어 생긴 것을 1단계 황금직사각형, 1단계 황금직사각형을 잘라내면 2단계 황금직사각형이 생기며 무한히 반복할 수 있다. 이렇게 각 단계에서 생긴 정사각형에 내접하는 사분원을 그려 생긴 나선을 황금나선이라고 한다. 이 황금나선은 자연환경에서 많이 볼 수 있는데, 앵무조개의 껍질, 솔방울의 나선모양, 초식동물의 뿔, 허리케인에서 발견할 수 있으며 크게는 나선은하에서 발견할 수 있다.
 
 
  우리나라의 아름다운 비
 

첨성대는 밑단의 지름과 곡면의 기둥 상단까지의 높이가 1 대 1.414의 금강비를 이루고 있다.

  건축물과 예술에서의 황금비는 대부분 서양에서 사용되어 왔다. 동양에서 많이 사용한 비는 1 대 √2로 황금비와는 다른 1 대 1.414인 금강비를 주로 사용하였다.
 
  우리나라에 있는 많은 건축물에서는 이 금강비를 사용하였다. 대표적으로 석굴암이 있다. 석굴암 불상의 높이와 불상이 있는 불주의 반지름의 비는 1 대 1.414로 금강비를 이루고 있다. 또한 별을 관측하는 데 사용된 첨성대는 밑단의 지름과 곡면의 기둥 상단까지의 높이가 1 대 1.414의 금강비를 이루고 있다. 이외에도 부석사 무량수전, 포석정이 있다.
 
  건축물 이외에도 금강비가 사용되는 예로는 A4용지가 있다. A4용지의 규격은 길이 297mm, 폭 210mm이다. 이는 금강비와 같이 1 대 1.414의 비를 이루고 있으며, 이러한 규격을 사용하는 이유가 있다. A4용지는 반을 잘라도 계속 1 대 1.414의 비를 이룬다. 잘랐을 때 같은 비를 이루기 때문에 낭비 없이 종이를 사용할 수 있다.
 
  서양의 황금비든, 동양의 금강비든 인간이 안정감과 아름다움을 동시에 느끼는 것들에 ‘수학’이 담겨 있다는 사실. 이제 낯익은 수들(1, 1, 2, 3, 5, 8, 13, 21, 34 …)을 일상에서 발견한다면 한번 뽐내 보자.
 
  이게 그 유명한 ‘피보나치 수’라고.⊙

 월간조선.

완벽한 암호는 있을까?

최초의 암호문은 스파르타 시대의 스키테일(scytale) 암호
⊙ 오늘날 널리 쓰이는 암호방식인 RSA 알고리즘은 소인수분해 방식 활용한 것
⊙ 패턴 암호, 홍채인식 암호 등 다양한 방식 등장

고대 스파르타인들이 사용했던 스키테일 암호.

  AM 7:00 아침에 눈을 뜨자마자 스마트폰에 지문을 올려 잠금을 풀고 알람을 끈다.
 
  AM 9:00 출근하여 PC의 암호를 입력하고 업무를 시작한다.
 
  AM 11:00 인터넷으로 사무용품을 주문하기 위해 공인인증서 비밀번호를 입력하여 결제한다.
 
  PM 1:00 점심값을 내기 위해 ATM기에 카드를 넣고 비밀번호 네 자리를 입력하여 현금을 찾는다.
 
  PM 3:00 메일로 업무 관련 파일을 전송하기 위해 메일 계정 아이디와 비밀번호를 입력한다.
 
  PM 7:00 퇴근하고 집에 들어가면서 현관문 비밀번호를 누른다.
 
  평범한 직장인이 단 하루 동안 사용한 암호(비밀번호)들이다. 단 하루라도 암호를 사용하지 않는 날이 있을까? 우리는 암호를 언제부터 사용했고, 암호를 사용하는 이유는 무엇일까?
 
  이번 연재에서는 이 단순한 궁금증에 대한 이야기를 하고자 한다.
 
 
  비밀 메시지를 전달하기 위해
 
  암호의 어원은 그리스어의 비밀이란 뜻을 가진 크립토스(kryptos)로 알려져 있다. 사전적 정의는 통신문의 내용을 제3자가 판독할 수 없도록 글자, 숫자, 부호 등으로 변경시킨 것이다. 이렇게 암호는 중요한 정보를 다른 사람이 보지 못하게 하기 위해 사용한다. 그렇다면 비밀스럽게 정보를 전달해야 할 때는 언제일까? 또한, 비밀 메시지를 전달하는 방법은 어떻게 발전되어 왔을까?
 
  아주 옛날에는 비밀을 유지하기 위해 기록을 하지 않고 직접 말로 전하는 방법을 사용했다. 또한 사자와 같은 동물의 털을 깎아 메시지를 쓰고, 털을 길러 보내면 받는 사람이 털을 깎아 메시지를 확인하는 방법도 이용했다.
 
  원시적인 방법을 벗어나 조금 더 과학적인 방법은 고대시대 전쟁을 배경으로 한 영화에서 찾아볼 수 있다. 아군에게 작전을 전달할 때 빈 종이처럼 보이지만 암호를 받은 사람이 종이를 불빛에 가져다 대면 메시지가 나타나는 장면을 본 적이 있을 것이다. 이는 불빛에 반응하는 약품으로 메시지를 적어 불빛과 반응할 때만 메시지를 볼 수 있도록 한 것이다. 이러한 암호 전달 방법을 스테가노그래피(Steganography)라고 하는데 이 암호 방식을 알고 있는 사람들에겐 비밀을 유지하기 어렵다는 한계가 있다.
 
  이렇게 작은 노력들을 시작으로 가장 안전한 암호를 만들기 위한 노력은 계속되어 왔다.
 
 
  본격적으로 시작된 암호화
 
  최초의 암호문은 스파르타 시대의 스키테일(scytale) 암호이다. 기원전 450년 경 당시 그리스 도시국가에서 전쟁터에 나가 있는 군대에 메시지를 보낼 때 사용한 암호로, 아래와 같은 방법으로 암호화했다.
 
  1. 암호를 공유하는 사람들끼리 같은 굵기의 원통형 막대를 가진다. 이 원통형 막대의 이름이 스키테일이다.
 
  2. 암호를 보내는 사람은 스키테일에 일정한 굵기의 종이를 나선으로 말아 가로로 전달할 메시지를 쓴다.
 
  3. 막대에 감았던 종이를 풀어 글자 순서가 섞인 상태로 전달한다.
 
  4. 암호를 받는 사람은 사전에 함께 나눠 가진 같은 굵기의 스키테일에 종이를 감아 원래 메시지가 무엇이었는지 확인한다.
 
  그러나 스키테일 암호는 원통의 굵기를 아는 모든 사람이 해독할 수 있기 때문에 보안에는 취약했다.
 
 
  다른 문자로 치환하라- 시저 암호
 

줄리어스 시저는 암살되기 전, 암살자를 주의하라는 암호 편지를 받았다. 그림은 칼 테오도르 폰 필로피의 ‘시저의 살해’.

  로마의 황제였던 줄리어스 시저(Julius Caesar)는 암살당하기 전 가족들로부터 긴급 메시지를 받았다. 메시지에는 ‘EH FDUHIXO IRU DVVDVVLQDWRU’라 쓰여 있었다. 이는 각 알파벳 순으로 세 자씩 뒤로 물려 읽는 방법으로 암호를 만든 것으로 암호문을 해독할 때는 알파벳 순서에서 3문자씩 당겨 읽으면 본래 메시지를 알 수 있었다.
 
  시저가 받은 메시지를 3글자씩 당겨서 읽어 보면 뜻은 ‘BE CAREFUL FOR ASSASSINATOR - 암살자를 주의하라’는 메시지였다. 이 시저 암호는 몇 문자씩 이동할지를 바꿔 가면서 사용할 수 있었기에 스키테일 암호보다는 보안이 조금 더 강화되었지만 이 또한 몇 번만 시도해 보면 금방 풀 수 있는 암호 방식이다.
 
 
  암호는 어떤 구조로 만들어지는가- 암호 알고리즘
 
  현대 사용되는 암호를 살펴보기 전에 암호의 기본적인 구조와 용어를 살펴보자.
 
  예를 들어 A가 ‘오늘밤 12시에 만나’라는 메시지를 암호화하여 B에게 보냈다고 하자. B는 ‘ㅇㄴㅂ 12ㅅㅇ ㅁㄴ’라는 메시지를 받았다. A와 B는 미리 자음을 활용하여 암호문을 만들 것이라는 약속을 한 상태였고, B는 받은 메시지를 해독해 냈다.
 
  이때, 암호를 보낸 사람 A를 ‘송신자’라 한다. 송신자가 보낸 ‘오늘밤 12시에 만나’와 같은 문장은 ‘평문’이라 한다. 또한 보안을 위해 다른 사람이 알아볼 수 없도록 가공하는 작업을 ‘암호화’라고 한다. 평문을 암호화하여 만든 문장 ‘ㅇㄴㅂ 12ㅅㅇ ㅁㄴ’은 ‘암호문’이 된다. 이 암호문을 받은 B는 ‘수신자’이고, ‘자음을 활용한다’는 약속은 ‘키(KEY)’가 된다. B가 암호화한 암호문을 키를 이용하여 평문을 알아내는 작업을 ‘복호화’라고 한다.
 
  이때 암호화 키와 복호화 키가 같은 암호를 대칭형 암호라 하고, 암호화 키와 복호화 키가 다른 암호를 비대칭형 암호라고 한다.
 
  우리가 앞서 살펴봤던 스키테일 암호와 시저 암호 모두 키가 동일한 대칭형 암호에 속한다. 대칭키 암호 방식에서는 암호화 키와 복호화 키가 동일한 비밀키를 사용하기 때문에 송신자와 수신자는 비밀 통신을 하기 전에 비밀키를 공유하고 있어야 한다. 반면 공개키 암호 방식에서는 하나의 쌍이 되는 공개키와 비밀키를 생성하여 암호화에 사용되는 공개키는 공개하고, 복호화에 사용되는 비밀키는 사용자가 안전하게 보관하도록 한다. 공개키 암호 방식에서는 송신자와 수신자가 사전에 키를 공유할 필요가 없기 때문에 불특정 다수 사용자 간에 사전 준비 없이도 암호 통신망을 구축하는 데 유용하게 사용할 수 있다.
 
 
  소인수분해와 RSA 암호
 
  오늘날 표준으로 사용되는 암호화 방법은 공개키 암호인 ‘RSA 알고리즘’이다. 이는 매사추세츠공대(MIT)의 로널드 리베스트(Ronald Rivest), 아디 샤미르(Adi Shamir), 레오나르도 애들먼(Leonard Adleman)이 고안해 낸 알고리즘으로, 그들 이름의 앞 글자를 따서 RSA 알고리즘이라 했다.
 
  RSA 알고리즘의 가장 큰 특징은 공개키 암호라는 점이다. 이전의 암호 방식에서는 사용하는 키뿐만 아니라 암호 알고리즘도 비밀로 하여 암호문의 비밀을 지키려 했지만, 현대 암호에서는 암호 알고리즘을 공개하도록 하고 있다. 1883년 아우구스테 케르크호프(Auguste Kerckhoff)는 암호 시스템의 안전성에 대해 ‘키 이외에 암호 시스템의 모든 것이 공개되어도 안전해야 한다’고 했는데 이것을 ‘케르크호프의 법칙(Kerckhoff’s principle)’이라고 한다. 이렇게 함으로써 암호 방식의 안전성을 공개적으로 검토하게 하여 안전성을 확인하는 것이다.
 
  그럼 이제 RSA 알고리즘이 무엇인지 알아보자. RSA 알고리즘의 기본적인 개념은 소수를 이용하는 것이다. 소수는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수를 말한다.
 
  중학교 수학시간에 배웠던 소인수분해를 기억하는가? 자연수를 소수의 곱으로 나타내는 것을 말하는데, 두 소수의 곱으로 이루어진 수가 어떤 수로 이루어지는가를 찾아내는 과정에서 RSA암호 만들기가 시작된다.
 
  예를 들어 143은 소수 13과 소수 11의 곱이라는 것을 구하는 것이다. 그리고 그 소수를 바로 암호로 이용하는 것이 아니라 복잡한 암호화 과정을 거쳐 암호문으로 만들기 때문에 암호를 분석해 내는 것은 더 오랜 시간이 걸린다.
 
  RSA 암호가 무엇인지 알아본 김에 RSA 알고리즘을 직접 만들어 보자. 다음은 암호학에서 소개하는 RSA 알고리즘의 간단한 방법이다.
 
  본래 RSA 암호를 만들 때는 최소 10자리가 넘는 두 개의 큰 소수를 사용하지만 독자들의 이해를 돕기 위해 가장 작은 소수인 2와 3을 이용하여 RSA의 암호화 작업을 하려고 한다.
 
  이 과정을 이해했다면 현재 당신이 사용하고 있는 대부분의 암호 알고리즘을 이해한 것이다. 우리가 사용한 소수는 아주 작은 소수라 복호화하는 과정이 수월했지만, 수의 자릿수가 커질수록 어떤 소수의 곱인지 찾아내는 것은 매우 힘들어진다. RSA 암호체계의 안전성은 큰 숫자를 소인수분해하는 것이 어렵다는 것에 기반을 두고 있다
 

RSA 알고리즘     1. A는 두 개의 소수를 골라 두수를 곱한 n=pq를 구한다.   두 소수 2와 3을 선택하여 두 수의 곱 n=6을 구한다.     2. A는 gcd(e, (p-1)(q-1))=1인 e를 선택한다.   gcd는 ‘Greatest Common Divisor’의 약자로 최대공약수를 의미한다. e는 암호화 지수 값이다. 따라서 e와 2(=(2-1)(3-1))의 최대공약수가 1인 e값을 찾는다. e=3이 가능하다.     3. A는 de≡1 (mod(p-1)(q-1))인 d를 계산한다.   수학기호 ‘≡’는 정수의 합동을 나타내는 기호로 a≡b(mod m)일 때 a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같다는 뜻이다. 따라서 d×3≡1 (mod2) 인 d를 구하면 된다. 1을 2로 나누면 나머지가 1이므로 d가 3이면 d×3=3×3=9가 되고, 9를 2로 나눠도 나머지가 1이 되므로 d=3이 가능하다. 여기서 d는 복호화 지수를 의미한다.     4. A는 n과 e를 공개하고, p, q, d를 비밀로 한다.   n=6, e=3을 공개하면 B는 이를 암호화하는 데 사용하게 된다. 이것이 바로 ‘공개키’다.     5. B는 메시지 m을 c≡me(mod n)로 암호화하여 A에게 보낸다.   B는 10이라는 메시지를 암호화하려고 한다. 10이 m값인 것이다. 따라서 c≡103(mod 6)이 되고, 1000은 6으로 나누면 나머지가 4가 된다. 따라서 c값으로 가능한 수는 16이 된다. B가 원래 전하려고 한 10은 암호화되어 16이 되었고 이 값을 A에게 보내게 된다.     6. A는 m≡cd(mod n)를 계산하여 복호화한다.   A는 m≡163(mod 6)을 계산하여 나머지가 4인 정수 중 하나가 원래 B가 보내려고 한 평문(10)임을 알아낼 수 있다.

 
  당신의 비밀번호는 안전한가?
 
  뉴스에서 해킹에 따른 금융 피해, 개인정보 유출 사례에 관한 사건들이 비일비재하게 보도된다. 따라서 사람들은 비밀번호의 안전을 위해 많은 노력을 하고 있다. 이러한 현상에 따라 ‘패스워드 증후군’이라는 용어도 생겼다. 이는 현대인들이 인터넷과 스마트폰을 쓰면서 보안을 위해 비밀번호를 계속 변경하면서 비밀번호를 기억하지 못해 혼란에 빠지는 것을 말한다.
 
  현대인들이 가장 많이 사용하는 암호는 아마도 스마트폰의 암호일 것이다. 스마트폰의 대표적인 암호 방식은 네 자리 숫자를 누르는 비밀번호 설정 방법과 점 9개의 일부를 연결하여 패턴을 그리는 패턴방호 방식이 있다.
 
  4자리의 비밀번호는 0000에서 9999까지의 숫자 중 하나를 설정하면 되므로 사용할 수 있는 비밀번호의 경우의 수는 1만 개가 있다. 그렇다면 패턴 암호을 설정할 수 있는 경우의 수는 몇 가지나 있을까? 패턴 암호는 9개의 점 중 4개 이상의 점을 연결하여 만들어야 한다는 조건이 있다. 현재 가능한 패턴 암호의 가짓수는 연구진마다 주장이 다르다.
 
  하지만 우리는 적어도 0001과 1000의 암호가 다른 패턴으로 인식되는 것만으로도 숫자 비밀번호보다 패턴 암호가 더 안전하다는 것을 알 수 있다.
 
 
  누구도 풀지 못하는 암호 - 생채인식 암호
 

홍채인식은 현존하는 생체인식 중 보안성이 가장 뛰어나다.

  스마트폰이 출시될 때마다 지문, 안면인식, 홍채인식 등의 잠금 방법이 큰 이슈가 되곤 한다. 생체인식 암호 중 일찍부터 널리 사용돼 왔던 것은 지문인식이다. 지문은 태아 3개월 때 만들어져 그 모양이 변하지 않고, 사람마다 지문이 모두 다르기 때문에 유일한 암호로 사용 가능하다.
 
  안면인식도 흔히 쓰이는데, 눈썹 간 거리, 얼굴뼈의 돌출 정도와 같은 특징을 활용하여 인식한다. 또한 얼굴 혈관에서 발생하는 열을 적외선 카메라로 촬영해 디지털정보로 변환하여 인식하기도 한다. 그러나 사람의 표정변화에 따라 인식을 못하는 경우도 있고, 조명에도 민감해서 변장 및 노화에 따른 얼굴 인식에는 현재 취약한 상태이다.
 
  얼마 전 출시된 스마트폰에는 최초로 홍채인식을 도입해 큰 화제가 되었다. 홍채인식은 인식기에 사람 눈을 맞추면 적외선 카메라가 사용자의 홍채를 이미지화하는데, 이를 개인 고유의 홍채코드를 생성하고 등록한 후 비교하는 방식으로 이뤄진다. 쌍둥이는 물론 사람의 양쪽 눈 홍채도 달라 현존하는 생체인식 방식 중 보안성이 가장 뛰어나다고 할 수 있다.
 
  생체정보는 자신만 가진 유일한 고유정보다. 따라서 아주 강력한 암호가 될 수 있다. 하지만 한번 유출되면 자신을 입증할 새로운 방법을 찾아야 한다는 맹점이 있다.⊙

 월간조선

집회 군중 수, 어떻게 추정하나

페르미 추정, 어떠한 문제에 대해 기초적인 지식과 논리적 추론만으로 짧은 시간 안에
    대략적인 근사치 추정
⊙ 서울시청광장~광화문까지 면적은 약 9만4000㎡, 1평(3.3)당 8~10명 정도로 계산해
    약 23만~28만명이 집회에 참여했다고 추산

  2016년 11월 12일 광화문에서 대규모 촛불집회가 열렸습니다. 그런데 촛불집회를 주관하는 단체에서 추산한 수도 기준 촛불집회 참석인원은 약 100만명, 집회의 안전 및 치안을 담당하는 경찰 측에서 추산한 수도 기준 촛불집회 참석인원은 약 26만명이었습니다. 똑같은 집회에 참석한 인원을 추산한 결과가 4배나 차이 난다는 사실에 한 국회의원은 국회 안전행정위원회 전체회의에서 경찰청장에게 어떻게 해서 이런 차이가 발생하였는가 질문을 합니다. 같은 인원에 대해 추산한 결과에서 이렇게 많은 차이가 발생한 까닭은 무엇 때문일까요?
 
 
  일일이 셀 수 없는 인원수, 어떻게 측정할 수 있을까?
 
  ‘2002 한일 월드컵 700만명의 국민이 거리로 나와 열띤 응원을 펼쳤습니다.’
 
  ‘2016년 7~8월 해운대 바닷가에는 일(日)평균 40만명의 피서객이 방문한 것으로 조사되었습니다.’
 
  언론을 통해 위와 같은 문구들을 접하다 보면 가끔 의문이 생기곤 할 것입니다. 대체 응원을 위해 거리로 나온 사람의 수 700만명, 해운대 바닷가에 일평균 40만명의 피서객이 방문한 것을 어떻게 아는 것일까 말입니다. 물론 인원이 적은 경우나 콘서트장처럼 입구가 제한적인 곳은 카운터기를 사용해서 어느 정도의 인원이 왔는지 정확하게 측정할 수 있을 것입니다. 하지만 천 단위, 만 단위, 10만 단위로 넘어가면 사람이 직접 그 수를 일일이 다 셀 수는 없는 노릇입니다. 그렇다면 이와 같은 거대한 인원수는 어떻게 측정하는 걸까요?
 
 
  이항복의 재치
 
  다음은 권율의 사위이자, 정유재란이 벌어졌던 당시 명나라에 사신으로 가 외교적 수완을 발휘해 7년의 전쟁을 끝내는 데 일조한 이항복의 어릴 적 일입니다.
 
  어린 시절 이항복은 유명한 말썽꾸러기였습니다. 이웃집 호박에 못을 박고, 옆집 참외밭의 참외 꽃을 몽땅 따놓거나 앞집 아이를 때려 울리는 등 하루라도 말썽을 피우지 않고, 어머니의 꾸중을 듣지 않는 날이 없었습니다. 하루는 항복의 어머니가 친정에 급한 일이 생겨 가봐야 할 일이 생겼습니다. 그런데 자신이 없는 동안 항복이 또 어떤 말썽을 피울지 걱정이 되었습니다. 어떻게 하면 항복이 나가서 말썽을 피우지 않게 집에 잡아둘 수 있을지 한참을 고민하다 좋은 생각이 떠올랐고 즉시 항복을 불러 이렇게 얘기했습니다.
 
  “항복아 내가 급한 일이 생겨서 외가를 다녀와야 하는데, 네가 나를 좀 도와주겠니?”
 
  “네, 어머니, 말씀만 하세요.”
 
  “저기 광 속에 콩이 한 섬 있는데, 한 섬에 있는 콩이 몇 개나 되는지 좀 헤아려 놓아라.”
 
  “네, 알겠어요.”
 
  항복은 아무런 의심도 없이 그러겠다고 말했고, 하인은 어머니가 시키는 대로 마당에 멍석을 깔고 그 위에 콩을 쏟아 놓았습니다. 어머니가 대문을 나가자 항복은 멍석에 주저앉아서 곰곰이 생각을 하였습니다. 그러다 이내 항복은 무릎을 탁 치면서 외쳤습니다.
 
  “옳지, 됐다.”
 
  그러고는 하인에게 되를 가지고 오라고 말했습니다. 하인이 되를 가져오자 항복은 콩을 되에 가득 담은 후 막대로 위를 평평하게 만들고 그 되 속에 있는 콩들을 세기 시작했습니다. 한참 후에 세기를 마친 항복은 하인에게 “콩을 다시 담아서 광에 가져다 놓아라” 하고선 쏜살같이 집 밖으로 나가버렸습니다.
 
  집 밖으로 나간 항복은 친구들과 시간 가는 줄 모르고 놀다 저녁 늦게 집으로 들어왔습니다. 항복이 집에 들어서니 화난 표정의 어머니가 항복을 기다리고 있었습니다. 어머니는 하인들로부터 자신이 외가로 나가자마자 항복이 밖으로 나갔다는 이야기를 듣고는 화가 난 것이었습니다. 집으로 들어온 항복을 본 어머니는 화를 가라앉히고 차분한 목소리로 물었습니다.
 
  “아침에 한 약속대로 콩은 다 세어 놓았느냐?”
 
  항복은 거침없는 목소리로 자신만만하게 대답했습니다.
 
  “네, 어머니.”
 
  어머니가 다시 한 번 물었습니다.
 
  “정말 다 세었느냐?”
 
  “네, 거짓말이 아닙니다.”
 
  “거짓이 아니라고? 내가 나간 뒤에 금세 나갔다는 말을 들었는데 거짓말이 아니라고?”
 
  “네, 정말 아닙니다. 저는 분명 콩을 다 세었습니다.”
 
  “그렇다면 콩의 개수가 몇 개더냐?”
 
  “어머니, 콩을 세는 일은 아주 쉬웠습니다. 콩 한 섬은 열 말이 아닙니까? 한 말은 열 되고요. 따라서 콩 한 섬은 콩 백 되가 됩니다. 저는 그래서 콩 한 되에 있는 콩의 개수를 정확하게 세어 거기에 백 배를 하였습니다.”
 
  이 말을 들은 항복의 어머니와 하인들은 이항복의 재치에 감탄했다고 합니다.
 
 
  페르미 추정
 
  이항복은 콩 한 섬에 들어 있는 콩을 하나하나 센 것이 아니라 부분의 개수를 통해 전체의 개수가 어떻게 될지 논리적으로 헤아려보았던 것입니다. 이런 것을 ‘추정’이라고 합니다.
 
  대상의 수가 너무 많아 일일이 조사하기 힘든 경우, 불가피하게 소수의 대상을 통하여 전체를 헤아리는 추정을 사용하곤 합니다.
 
  가장 유명한 것 중 하나가 이탈리아의 물리학자 엔리코 페르미의 이름을 딴 페르미 추정입니다. 페르미 추정은 어떠한 문제에 대해 기초적인 지식과 논리적 추론만으로 짧은 시간 안에 대략적인 근사치를 추정하는 방법입니다.
 
  페르미 추정에서 가장 유명한 예(例) 중 하나는 당시 페르미가 시카고대학 학생들에게 출제한 시카고의 피아노 조율사 수를 구하는 추정입니다.
 
  우리는 몇 가지 단계를 거쳐 시카고의 피아노 조율사 수를 추정할 수 있습니다.
 
  그중 첫 번째 단계는 전제를 인식하는 것입니다. 전제를 인식하는 단계에서는 기본 개념들을 정의하고 범위를 설정합니다.
 
  먼저 시카고의 피아노 조율사는 ‘어떤 피아노를 조율하는 사람인가?’로 범위를 한정해야 합니다. 여기서 페르미는 학교·카페·학원 등의 피아노가 아닌 ‘시카고 가정집의 피아노’를 조율하는 사람으로 피아노 조율사의 수를 한정합니다. 즉 피아노 조율사의 수는 ‘시카고 가정집의 피아노 수’ 다시 말해 시카고에 있는 가정집의 수와 관련 있다는 전제를 가지고 있습니다.
 
  두 번째 단계는 접근법을 설정하는 단계입니다. 접근법을 설정하는 단계에서는 최종 결과 값을 구하기 위한 식을 세웁니다.
 
  여기서 중요한 것은 ‘무엇을 기준으로 할 것인가’입니다. 결론 도출을 위한 식을 어떻게 설정하고 그 식을 설정하기 위해서는 어떤 수치들이 필요한지 생각해야 합니다.
 
  위의 문제에서는 ‘피아노 조율사의 수 = 연간 피아노 조율 건수/1명의 피아노 조율사가 1년 동안 조율하는 건수’의 식을 통해 찾을 수 있습니다.
 
  세 번째 단계는 세부 가설을 수립(모델화)하는 단계입니다. 이 단계에서는 필요한 수치에 들어가는 요소들을 세분화하여 가설을 세우고 구체적인 수치들을 추정합니다.
 
 
  시카고의 피아노 조율사 수는?
 
  위의 문제에서는 다음과 같은 요소들의 수치를 추정할 수 있습니다.
 
  - 시카고의 인구수는 약 300만명으로 가정한다.
  - 가구당 구성원은 대략 3명이다.
  - 피아노 보유율을 10% 정도라 하면, 10만 가구가 피아노를 갖고 있다.
  - 피아노 조율은 1년에 한 번 한다고 가정한다.
 
  이 가설을 통해 연간 피아노 조율 건수는 10만 건이라고 추정할 수 있습니다.
 
  - 조율사의 작업시간은 이동시간을 포함해 약 2시간이라고 가정한다.
  - 조율사는 하루 8시간, 주 5일, 1년에 50주가량 일한다.
  - 하루에 4건, 한 주에 20건, 1년에는 1000건을 조율한다.
 
  이 가설을 통해 연간 1명의 피아노 조율사가 피아노를 조율하는 건수를 1000건이라고 추정할 수 있습니다.
 
  가설 수립을 통해 얻은 요소들의 수치를 최종 결과 값을 구하기 위한 식에 대입해 주면 피아노 조율사의 수가 약 100명 정도일 것이라고 추정할 수 있습니다. 이런 페르미 추정은 기업의 입사시험, 영재성 평가 등에서도 사용되고 있습니다.
 
 
  4개 특정 구역 내 피서객 하루 4번 측정
 
  앞서 나왔던 촛불집회 참가 인원수, 거리응원에 참가한 인원수, 해운대 바닷가의 피서객 수를 페르미 추정을 통해 산출해 보겠습니다.
 
  해수욕장에 있는 피서객의 수를 집계할 때의 페르미 추정법은 다음과 같습니다. 먼저 해수욕장 내 특정 지역(가로 30m × 세로 20m) 내에서 피서를 즐기는 사람 수를 세고, 전체 면적만큼 곱하면 피서객 수를 추정할 수 있습니다.
 
  실제로, 부산시에서는 해운대 해수욕장에 특정 구역 4개를 설정해 오전 10시부터 오후 4시까지 하루 4번가량 조사한 평균값으로, 해수욕장 전체 면적(12만)에 해당하는 당일 피서객 수를 집계하고 있습니다.
 
  따라서 하루에 해운대 바닷가에 40만명의 피서객이 방문했다는 말은 오전 10시부터 오후 4시까지 해운대 해수욕장에 설정된 면적이 600인 4개의 특정 구역에 평균적으로 2000명 정도의 피서객이 있었다는 이야기입니다.
 
  집회나 월드컵 응원의 경우에는 행사가 벌어지는 동안 그 장소에 있을 수 있는 인원을 추산한 후 전체 인원을 추정하고 있습니다.
 
 
  경찰 측 집회 인원 추산 방법
 

집회 인원은 광화문광장~서울시청광장의 넓이에 한 평당 인원수를 곱하면 추산할 수 있다.

  경찰 측에서 2016년 11월 12일의 촛불집회 인원을 추산한 방법을 생각해 보면 다음과 같습니다.
 
  집회가 벌어진 서울시청광장부터 광화문까지 면적은 약 9만4000㎡입니다.
 
  여기에 1평(3.3㎡)에 서 있을 수 있는 사람을 대략 8~10명 정도로 계산하면 약 23만~28만명이 집회에 참여했다고 추산할 수 있습니다. 따라서 경찰 측의 주장이 잘못된 것이 아니라는 것을 알 수 있습니다.
 
  그렇다면 주최 측과의 추산 인원 차이는 어떻게 해서 발생한 것일까요?
 
  경찰이 추산하는 인원은 경찰에 공시된 집회시간을 기준으로 추산이 됩니다. 다시 말해 경찰 측은 한순간에 최대 몇 명의 인원이 집회에 참석하는가를 추산합니다. 따라서 이른 시간에 참석한 인원, 늦은 시간에 참석한 인원, 소규모 인원은 경찰이 추산하는 인원에 들어가지 않는 것입니다.
 
  반면에 주최 측에서 추산하는 인원은 하루 동안 집회에 참석한 총인원을 조사하는 것이기 때문에 경찰 측과 주최 측이 추산하는 인원의 차이가 크게 벌어질 수 있는 것입니다.
 
 
  빅데이터를 이용한 집회 인원 추정
 
  페르미 추정은 말 그대로 추정입니다. 당연히 어느 정도의 오차가 생길 수 있습니다. 따라서 최근에는 이러한 오차를 줄이기 위해 빅데이터를 이용해 참여 인원을 확인하는 방법도 사용되고 있습니다. 이번 촛불집회의 경우 광화문역·시청역 등 광화문광장 일대 지하철역을 이용한 시민의 수가 평소에 비해 얼마나 증가했는지를 구하고, 지하철의 수송분담률을 적용하여 전체 인원을 산정하는 방법과 집회장소 곳곳에 휴대전화의 무선 신호를 감지할 수 있는 센서를 설치해 집계된 신호를 바탕으로 광화문 부근을 방문한 시민의 수를 구하는 방법이 사용되고 있습니다.
 
  수학적 추정 방법과 빅데이터 기술의 융합은 앞으로 우리가 수집한 자료를 이용해 미래를 예측하는 데 있어서 중요한 주춧돌이 될 것입니다.⊙

 월간조선

유아들의 숫자 세기는 이상하다

만 5세가 채 되지 않은 아이들은 크기와 개수를 혼동하여 멀리 떨어뜨려 놓은 동전 2개가 더 많다고 대답한다.

  유명한 유아~초등학생 수학교육서에 이런 대목이 있다. 그림과 같이 작은 동전 6개를 촘촘히 놓고, 큰 동전 2개를 멀리 놓은 뒤, 동전의 개수가 어느 쪽이 더 많냐고 묻는 장면이다.
 
  만 5세가 채 되지 않은 아이들은 크기와 개수를 혼동하여 멀리 떨어뜨려 놓은 동전 2개가 더 많다고 대답한다. 성인이 된 우리는 크기에 혼동되지 않고, 개수에 집중하여 동전 6개와 동전 2개 중 6개가 더 많다는 것을 자연스럽고도 당연하게 알 수 있다.
 
 
  우리가 사용하는 길이는 이상하다
 
  수학 수업을 떠올려보면 수직선을 0부터 10까지 그은 뒤, 양 끝점을 모두 포함하는 것을 ‘닫힌 구간 [0, 10]’이라 하고, 양 끝점을 뺀 것을 ‘열린 구간 (0, 10)’이라고 배운 것을 기억할 것이다. 그렇다면 [0, 10]과 (0, 10)의 길이는 각각 몇이라고 하면 좋을까?
 
  약간은 고민하겠지만 대부분 ‘10’이라고 대답할 것이다. 예전 기억을 떠올려보면 9.9999…=10이라고 했으니 (0, 10)과 [0, 10]의 길이는 같을 수도 있을 것 같다. 그런데 이렇게 생각하고 보니 [0, 10]은 [0, 1), [1, 2), … , [9, 10]이 모인 것이니 같은 방식으로 하면 0, 1, 2, … , 9, 10의 점들은 모두 빠져도 상관이 없어야 한다.
 
  내친김에 더 작게 [0, ), [, ), … 으로 생각해 보면 [0, 10]까지의 숫자 중 , , … , ,까지 빠져도 되고, 숫자만 조절하면 어마어마한 개수의 점들이 빠질 수 있다는 것까지 생각이 이르게 된다. 이쯤 되니 우리가 길이를 제대로 재고 있긴 하나 라는 생각마저 들기도 한다.
 
 
  길이는 어떻게 측정하는 것인가?
 
  우리가 현재 사용하고 있는 길이, 무게, 크기 등에서 모두 위와 같은 현상이 나타난다. 그렇다면 우리가 무엇인가를 잘못하고 있는 것일까? 아님 무엇인가를 빼놓고 생각하는 것일까? 수학에서는 이런 것들을 엄밀하게 하기 위해서 ‘측도(measure)’라는 것을 정의하여 사용하고 있다. ‘측도’라는 것이 무엇인지 핵심적인 것만을 말하면 다음과 같다.
 
  (1) 측도 함수 μ는 항상 0보다 크거나 같다.
 
  (2) 아무것도 없는 집합의 측도 함숫값은 0이다.
 
  (3) 어떤 집합 A를 측도 함수 μ로 측정한 값은 A를 서로 겹치지 않게 나눈 뒤, 각각을 잰 측정값을 더한 것과 같다.
 
  이를 받아들이기 쉽게 길이에 빗대어 다시 말해보면 다음과 같다.
 
  (1) 길이는 항상 0보다 크거나 같다.
 
  (2) 아무것도 없는 것의 길이는 0이다.
 
  (3) 어떤 물체 A의 길이는 그 물체를 겹치는 부분이 없게 길이를 나누어 잰 뒤 합한 것과 길이가 같다.
 
  우리가 일반적으로 사용하는 ‘길이’와 같은 측도 함수는 르베그 측도 함수로, 이는 측도 이론에 큰 공헌을 한 앙리 르베그(Henri Lebesgue)에서 따온 것이다. 이제, 이를 가지고 [0, 10]의 길이를 측정해 보자.
 
  그럼 대체 [0, 10]과 (0, 10)의 길이는 몇이라고 해야 할까?
 
  결론부터 말을 하자면 당연히 10이다. 물론 ‘어떤’ 측도 함수를 사용했는지에 따라 다르지만 르베그 측도 함수로는 10이 나온다. 다음은 우리가 길이를 재기 위해 사용할 르베그 측도 함수의 정의이다.
 
  어려운 공식처럼 보이는 이것을 말로 풀어서 쓰면 ‘A를 모두 덮을 수 있도록 (겹치든 겹치지 않든) 열린 구간들을 모은 것들의 길이를 합한 것 중 최대 하계(하한)’가 된다. 하계란 어떤 수가 가질 수 있는 범위보다 작은 수로서, 만약 ‘x 〉 3’이라면 0과 3 모두 x가 될 수 있는 어떤 수보다도 작은 수이기에 하계이다. 하지만 3보다 큰 수들은 x가 될 수 있기에 3을 x의 최대 하계 또는 하한이라 부른다. 이제, 우리는 [0, 10]과 (0, 10)의 길이를 잴 준비가 되었다. 열린 구간 (0, 10)의 길이는 처음부터 열린 구간 그 자체이므로 하한 값은 자기 자신인 10이다. (열린 구간 (a, b)의 길이는 b-a로 정의한다.) 여기에 또한, [0, 10]의 닫힌 구간은 (-,)와 (0, 10), (,)로 덮을 수 있는데 이때의 각각의 길이 합은 1+10+1=12이지만 0과 10을 덮기 위해 추가한 (-,)와 (,)를 (-,)와 (,)로 바꿔도 모두 덮을 수 있으므로 0.2+10+0.2=10.4로 길이가 줄게 된다. 같은 방식으로 계속 길이를 줄여나갈 수 있지만 아무리 줄어들어도 10 이하로는 내려가지 않는다는 것을 알 수 있는데, 이렇게 더 이상 내려갈 수 없는 값들 중 가장 큰 값(여기서는 10)을 하한이라고 한다.
 
  그런데 아직 의문은 풀리지 않았다. (0, 10)과 [0, 10]의 길이가 같다는 것은 알게 되었지만 그럼 ‘점을 몇 개나 빼도 길이가 같은 걸까?’라는 의문은 아직 풀리지 않은 것이다. 이에 대해서 이야기하려면 다분한 수학용어들이 등장하기에 간략히 하자면 ‘셀 수 있을 만큼 많이’ 점을 빼도 길이는 똑같다.
 
  수학에서는 무한히 많은 것들에 대해서도 ‘셀 수 있을 만큼 많은’과 ‘셀 수 없을 만큼 많은’으로 경우를 나누는데, 분수 형태로 표시할 수 있는 유리수는 셀 수 있을 만큼 많은 경우며, 무리수의 개수는 셀 수 없을 만큼 많은 경우다. 따라서 [0, 10] 사이에 존재하는 모든 유리수를 모아서 르베그 측도로 길이를 재면 그 값은 0이 나오고, 무리수만 모아서 재도 0이 나온다. 이는 이해를 돕기 위해 예를 든 것으로, 셀 수 없이 많은 점을 모아 르베그 측도 값을 재도 0이 나오는 경우가 있음을 알아야 한다.
 
 
  대체 무엇을 측정할 수 있을까?
 
  수학이라는 것은 일반인이 보기에 살아가는 데 별 필요 없는 학문일지도 모른다. 지금까지 이야기한 측도에 관한 것도 쓰임새가 없다면 그렇게 보일지 모른다. 하지만 이러한 측도 이론은 현대를 살아가는 우리에게 너무나도 익숙한 확률과 큰 연관성이 있다. 러시아 수학자인 안드레이 니콜라에비치 콜모고로프(Andrey Nikolaevich Kolmogorov)는 독립적으로 연구되어 오던 측도 이론과 확률론을 결합하여 현대 확률론의 바탕을 마련했다. 확률에는 주사위의 1, 2, 3, 4, 5, 6처럼 값이 딱딱 떨어지는 표본이 있는 반면, 한 공장에서 만들어진 전구의 수명처럼 값이 떨어지는 것이 아닌 연속적으로 이어질 수 있는 경우가 있다. 예를 들어 전구의 수명이 5년 이상이라고 하는 것은 만들어지는 모든 전구의 수명이 5년 이상이라는 것이 아니라 수명이 5년 미만인 전구가 나올 확률이 0이라는 것이다. 콜모고로프 이전의 확률론은 주사위의 경우와 전구의 수명 같은 경우를 따로 계산했지만, 콜모고로프 이후의 확률론은 각 확률을 계산하는 변수의 ‘측도’를 달리하여 계산한다. 주사위의 경우 모든 경우를 ‘각각 세는 측도’이지만 전구 수명의 경우 ‘측도 함숫값이 0인 변수 부분은 제외’하고 계산하는 것이다. 콜모고로프 이후 많은 발전을 이룬 확률론은 경제, 통계학에 사용됨은 물론 현대물리의 정수라 불리는 양자역학 또한 ‘확률론적 결정론’이 적용된다.
 
 
  ‘확률이 0’≠‘불가능’?
 
  소위 ‘확률이 0이다’라는 것을 ‘불가능하다’라는 것과 똑같다고 생각하지만 확률론에서는 두 가지를 서로 다르다고 정의한다. 다트 게임을 생각해 보자.
 
  구역마다 정해진 점수가 있지만 구역을 나누는 경계선은 항상 논쟁거리인데, 일반적으로 경계선에 맞았을 경우 두 구역 중 높은 점수를 얻는 것으로 되어 있다. 만약 다트의 끝이 선과 같이 매우 가늘다면 다트가 경계선에 맞을 확률은 몇이나 될까? 르베그 측도에서 다시금 생각해 보면 다트 게임판에서 얇은 선이 차지하는 면적은 0이 되는데, 이를 바꾸어 말하면 다트로 선을 정확히 맞힐 확률은 0을 뜻하게 된다. 하지만 우리는 다트 게임 혹은 양궁에서 보듯이 불가능하지는 않다는 것을 몸으로 체감하고 있다.
 
  손에서 떠나 표적 바로 앞까지 진행한 다트가 순간 사라진다거나 이미 맞은 위치가 바뀐다거나 하는 일은 ‘불가능’한 일이다.
 
  어쩌면 이것이 의미하는 바가 리우올림픽에서 펜싱의 박상영 선수가 10-14로 몰린 상황에서 역전해 금메달을 차지한 것처럼 눈앞에 분명히 있지만 성공 확률이 매우 낮은 것도 노력하면 이룰 수 있다는 희망적인 메시지가 아닌가 하고 생각해 본다.⊙

 월간조선

패리티 비트는 왜 그 위치에 있어야 할까?

빌헬름 라이프니츠가 발명한 이진법, 모스부호, 컴퓨터 등에 응용
⊙ 사용하지 않는 한 개의 비트 공간을 활용해 오류 여부를 확인하는 데 사용하는 게 ‘패리티 비트’

  마법의 카드. 그 비밀은?
 
  1부터 31까지의 수가 적힌 5장의 카드가 있다. 이 카드는 당신이 생각하는 수를 맞힐 수 있는 마법의 카드이다.
 
  1부터 31까지 수 중에서 하나의 수를 생각해 보자. A, B, C, D, E의 카드 중에서 선택한 수가 포함되어 있는 카드를 고르고, 그 카드의 첫 번째 칸의 수를 서로 더해 보자. 당신이 선택한 수가 맞는가? 만약 틀렸다면 계산에 실수가 있었을 것이다. 다시 한 번 해 보자. 방법은 동일하다. 1부터 31까지 수 중에서 처음 선택한 수와 다른 수를 선택하고, 선택한 수의 카드에서 색칠된 칸의 수를 더해 보자. 이번에도 당신이 선택한 수가 나왔을 것이다. 어떤 원리로 당신이 생각한 수를 모두 맞힐 수 있는 것일까? 눈치챈 사람도 있을 것이다. 정답은 진법이다. 그중에서도 이진법을 사용한 트릭이다. 아래 표를 기준으로 카드 안의 수들을 이진수로 바꿔 보자.
 
  이 표를 기준으로 각 카드에 있는 수들의 공통점을 찾아보면 다음과 같다.
 
  27을 예로 들어 보자. 27은 A, B, D, E 카드에 들어 있다. 27을 이진법으로 고치면 11011(₂)로 이것은 다음과 같이 풀이할 수 있다. 11011(₂) = 10000(₂) + 1000(₂) + 10(₂) + 1(₂)이며, 이것은 2⁴+2³+2+1 = 16+8+2+1과 같다. 즉 A, B, D, E 카드의 첫 번째 수의 합인 것이다.
 
 
  컴퓨터가 이진법을 선택한 이유
 

전신기와 모스부호를 발명한 사무엘 모스.

〈그림1〉 모스부호로 표시한 SOS.

  ‘삐삐삐 삐-삐-삐- 삐삐삐(짧은 신호 3번, 긴 신호 3번, 짧은 신호 3번)’ 영화 속에서 나오는 특이한 신호음을 들어 본 적이 있는가? 이 소리는 배가 난파되었을 때나 전쟁에서 적군에게 포위당했을 때와 같이 긴박한 상황에서 모스코드를 사용하여 보내는 SOS 신호이다. 모스코드는 미국인 사무엘 모스(Samuel Morse, 1791~1872)의 이름을 딴 것이다. 단음(·)과 장음(-)의 두 가지 기호만을 사용하여 문자 또는 수를 표현한 통신수단으로 0과 1만을 사용하는 이진법과 흡사하다. 그렇다면 이진법은 누구에 의해 언제부터 사용되었을까? 이진법을 처음 발명한 사람은 독일의 수학자 고트프리트 빌헬름 라이프니츠(Gottfried Wilhelm von Leibniz : 1646~1716)이다. 십진법에 익숙한 당시 사람들에게 이진법은 생소하고 불편하여 널리 사용되지 않았지만 십진법보다 논리 조립이 간단하고 전자, 전기 신호로 나타내기 편리하여 컴퓨터에서 사용하게 되었다. 이후 컴퓨터와 데이터 통신이 널리 쓰이는 현대에 와서는 그 중요성이 더욱 커졌다.
 

이진법을 창안한 고트프리트 라이프니츠.

 
  정확한 데이터가 맞을까?
 
  정보화 사회에 있어서 데이터의 신뢰성은 굉장히 중요한 부분을 차지한다. 내가 받은 데이터에 오류가 있는 것인지 그렇지 않은 것인지를 매번 의심해야 한다면 어떨지 상상해 보자. 지금처럼 데이터 통신이 발달된 사회는 오지 않았을 수도 있다.
 
  디지털 신호는 기본적으로 신호가 ‘있다’, ‘없다’ 이 두 가지 상태로 구분하며, 신호가 있을 때를 1, 없을 때를 0으로 표시한다. 사용자가 전송하고자 하는 데이터는 모두 0 또는 1의 디지털 신호로 변환되는 인코딩 과정을 거쳐 전송된다. 디지털 신호로 정보가 전송되는 동안 노이즈나 다른 장애가 생기면 신호가 있다, 없다를 반복하여 제대로 된 신호가 가지 못하는 경우가 발생한다. 예를 들어 설명해 보자. ‘100’이란 수 정보를 전달하려고 한다. 컴퓨터는 이 정보를 디지털 신호인 ‘1100100’으로 변환하고 전송하였다. 전송 과정 중에 순간적 오류가 생겨 신호를 줘야 하는 부분에서 신호를 주지 않고, 신호를 주지 않아야 하는 부분에서 신호를 주었다면 전송받은 데이터는 ‘0011011’이 된다. 즉, 수신된 정보는 ‘27’이 되는 것이다.
 
  이렇듯 신뢰성 있는 통신을 위해서 데이터에 오류가 있는지 없는지를 확인하는 작업은 꼭 필요하다.
 
 
  패리티 비트로 오류 발견하기
 
  디지털 데이터에서 정보를 저장하는 최소 단위를 비트(binary digit=bit)라고 하고, 문자를 저장하는 최소의 단위는 8개의 비트가 모인 바이트(byte)라고 한다. 하나의 비트는 0 또는 1이란 두 개의 정보를 가질 수 있기 때문에 비트가 한 개씩 늘어날 때마다 표현 가능한 정보는 2의 거듭제곱 꼴로 늘어나게 된다. 바이트의 경우 8개의 비트가 모여 총 256개의 정보 표현이 가능하다. 한편, 미국에서 데이터 통신으로 사용하는 문자로는 영문 알파벳 대문자 26개, 소문자 26개, 숫자 10개, 특수문자 32개, 공백문자 1개가 있고, 출력이 불가능한 제어문자로는 33개가 있다. 이 문자들을 모두 표시하기 위해서는 총 128개의 정보를 구분할 수 있어야 하므로 최소 7개의 비트(개)가 필요하다. 문자를 저장하는 최소 단위로 바이트를 사용하는 컴퓨터에서 미국에서 사용하는 모든 문자를 사용하면 한 개의 비트 공간이 남아 있게 된다. 즉 버려지는 정보공간이 생긴다는 의미이다. 사람들은 이 공간을 버리지 않고, 오류 여부를 확인하는 데 사용하였다. 이를 ‘패리티 비트’라고 부른다.
 
  패리티 비트는 다음과 같이 짝수 패리티나 홀수 패리티 중 하나로 결정한다.
 
  ● 짝수 패리티 : 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트 값을 0 또는 1로 결정
 
  ● 홀수 패리티 : 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트 값을 0 또는 1로 결정
 
  〈그림 3〉의 경우 전송하려는 데이터 비트의 1의 개수가 3개이므로 짝수 패리티는 마지막 패리티 비트 자리에 1을 넣어 준다. 이때, 데이터 중 하나의 비트가 변경되었다고 가정해 보자. 짝수였던 1의 개수가 홀수 개로 바뀌게 된다. 즉, 홀짝성이 바뀜으로 오류가 있음을 알게 된다.
 
  홀수 패리티를 준 경우는 어떨지 문제를 풀어 보면서 살펴보자. 위의 5개의 데이터 중에서 단 하나의 데이터에서 비트 하나가 변경되었다. 오류가 발생한 데이터는 몇 번일까?
 
  정답을 찾는 건 아주 간단하다. 해당 데이터의 패리티 비트는 홀수 패리티이다. 즉, 전체 데이터의 1의 개수가 홀수여야 한다. ①번의 경우 1의 개수는 8개이므로 오류가 발생한 데이터라고 할 수 있다. 이렇게 홀짝성으로 오류를 검출하는 패리티 비트 검사는 매우 간단하고 쉬운 방법이지만 큰 약점이 존재한다. 오류가 난 위치를 알 수 없어 정정할 수 없고, 하나의 비트가 아닌 여러 개의 비트에서 한꺼번에 에러가 발생하면 단순 홀짝성으로 오류를 검출할 수 없다는 것이다.
 
 
  해밍코드와 마법의 카드
 

해밍코드를 창안한 리처드 해밍.

  패리티 비트의 약점을 보완한 방법이 해밍코드(Hamming code)이다. 해밍코드는 수학자 리처드 웨슬리 해밍(Richard Wesley Hamming)의 이름에서 유래되었다. 이 방법을 사용하면 오류를 검출할 뿐만 아니라 오류의 위치를 발견하고 정정까지 가능하다. 방법은 다음과 같다.
 
  2의 거듭제곱번째 위치에 있는 비트들을 패리티로 사용한다. 즉, 1, 2, 4, 8, 16, 32, … 번째는 패리티 비트가 들어가고, 나머지 공간에 데이터 비트가 들어간다.
 
  데이터 비트 사이에 들어가 있는 패리티 비트들은 아래와 같이 각각의 자리에 있는 비트들이 전송 중 오류가 발생했는지 여부를 확인한다.
 
  ● P1의 패리티 값 : 1, 3, 5, 7, 9, 11, … 의 값들의 패리티 검사를 통해 정함
 
  ● P2의 패리티 값 : 2, 3, 6, 7, 10, 11, … 의 값들의 패리티 검사를 통해 정함
 
  ● P3의 패리티 값 : 4, 5, 6, 7, 12, 13, 14, 15, … 의 값들의 패리티 검사를 통해 정함
 
  ● P4의 패리티 값 : 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, … 의 값들의 패리티 검사를 통해 정함
 
  각각의 패리티 비트가 검사하는 자릿수를 자세히 살펴보자. 마법의 카드에 적힌 수 패턴과 동일한 패턴이라는 것을 발견할 수 있을 것이다. 각 카드에서 첫 번째 칸의 수가 패리티 비트 자릿수이고, 그 밖에 카드에 적힌 수는 패리티 비트가 오류 검사하는 비트들의 자릿수와 같다. 단순한 우연이라고 생각하는가? 그렇지 않다. 해밍코드는 마법의 카드와 동일한 원리를 갖는다. 데이터를 디지털 신호로 고쳤을 때, 끝자리가 1인 자릿수, 끝에서 두 번째 자리가 1인 자릿수, 끝에서 세 번째 자리가 1인 자릿수끼리 모아서 오류를 검증한다. 백문이 불여일견. 오류를 발견하고, 이를 정정하는 과정까지 예제를 통해 살펴보도록 하자. 우선 〈그림 4〉를 해밍코드로 수정해 보자. (해밍코드 수정 과정 참조)
 
  해밍코드가 완성되었다면 임의로 오류를 발생시켜 보자. 예를 들어 〈그림 4〉처럼 오류가 발생한 데이터 비트를 자리라고 하면 9번째 자리가 0에서 1로 바뀐다. 이제 이 코드를 전달받은 컴퓨터의 입장이 되어 보자. 먼저 짝수 패리티가 맞는지 확인해야 한다. 각 패리티 비트마다 짝수가 맞으면 ‘0’, 홀수이면 ‘1’을 적는다.
 
  〈그림 6〉과 같이 짝수 패리티를 맞추면 1001 값이 나온다. 이 값을 십진수로 고치면 2³+1=9가 나온다. 전달받은 컴퓨터는 9라는 값을 통해 9번째 자리에서 오류가 발생했다는 것으로 판단한다. 어떤 자리에 오류가 발생한 것인 줄 안다면 정정도 가능하다. 9번째 자리의 값을 1에서 0으로 바꾸어 값을 출력하게 된다.
 
  데이터에서 오류를 찾아 정정까지 할 수 있는 해밍코드의 기법이 이진법을 사용한 트릭 마법과 같을 것이라고 예상할 수 있었을까? 지금 접한 해밍코드에도 약점은 있다. 여러 개의 비트에서 오류가 한꺼번에 발생할 때는 오류를 정정할 수 없다. 이러한 경우에는 또 다른 기법으로 오류를 발견하고, 정정할 수 있을 것이다. 생각만 해도 복잡하고 어려울 것 같다. 하지만, 어쩌면 우리가 모르는 다양한 기법과 기술력 안에도 해밍코드의 원리처럼 쉽게 접할 수 있는 간단한 수학적 원리가 숨겨져 있을 수 있다.⊙

월간조선

‘총알배송’은 어떻게 가능할까? - 최적계획 찾기

반드시 순서를 지켜야 하는 일을 정리한 후 동시에 할 수 있는 일들을 찾는 것이 관건
⊙ 출발점과 종착점이 같은 경우는 ‘해밀턴 순환로’ 이론을 적용하면 세계여행 경로 계획할 수 있어
⊙ ‘빠른 길 찾기’ 앱 등에 적용

  한국은 유난히 빠른 것에 열광한다. 어떠한 상품을 예정보다 빨리 갖기 위해 더 비싼 가격을 주고 구입하기도 하고, 빠른 길을 찾아 가기 위해 실시간 교통정보가 반영된 내비게이션을 항상 켜고 운전하는 운전자도 많다. 또한 “최대한 빨리하겠습니다”라는 말은 회사에서 업무 할 때도 가게에서 상품을 준비할 때도 아주 빈번하게 사용한다. 여기서 ‘빠름’은 단순히 정말 어떤 것을 하는 데 걸리는 시간이 짧은 것을 의미하기도 하지만, 후자의 경우는 어떠한 일이 효율적으로 진행되는 것을 의미하기도 한다. 이번 글에서는 빠른 일 처리와 효율적인 시간 활용을 위해 사용하는 수학적 사고에 대해 살펴보려 한다.
 
 
  효율적 생산을 위해서 - 최적 계획법
 
  약 2년 전 한 감자칩이 품귀현상을 불러일으키며 폭발적인 인기를 누렸다. 시중에서 구하기가 매우 어려웠는데 ‘제조업체가 일부러 생산량을 조절하는 것이 아닌가’ 하는 소문까지 돌았다. 실제로 감자칩 제조 회사는 공장을 24시간 풀가동했을 뿐만 아니라 분명 가장 효율적인 방법으로 감자칩을 만들었을 것이다.
 
  여기서 효율적인 방법이란 무엇일까? 하루 24시간 안에 보다 더 많은 과자를 만들어 내는 방법이 효율적인 방법일 것이다. 이처럼 짧은 시간 등과 같이 주어진 제약 조건하에서 효율을 극대화할 수 있게 하는 계획법을 ‘최적 계획법’이라고 한다.
 
  다음 예를 보면서 최적 계획법에 대해 알아보자.
 
[예] 이해하기 쉽게 감자칩 한 봉지를 만드는 방법을 예로 살펴보자.
 
  작업 방법을 참고하여 감자칩을 만들 때, A부터 F까지 순서대로 한다면 과자를 만드는 데 걸리는 시간은 총 3+2+3+5+7+10=30분이 걸린다. 이보다 짧은 시간에 감자칩을 만들 수는 없을까? 최적 계획을 세우기 위해서는 많은 것을 고려해야 하지만 가장 중요하게 고려되는 조건은 바로 시간이다. 그렇다면 시간을 단축하기 위해서는 어떻게 해야 할까? 우선, 반드시 순서를 지켜야 하는 일을 정리한다. 그런 후에 동시에 할 수 있는 일들을 찾는다. 이를 기억한 채로 다시 감자칩 만드는 작업으로 돌아가 보자.
 
  A~F의 작업 중 일의 순서에 따라 그림으로 나타내면 다음과 같다.
 
  그림 ( )의 숫자는 걸리는 시간을 의미한다.
 
  즉 작업 C, D, F는 동시에 해도 된다. 따라서 작업하는 데 걸리는 최소 시간은 동시에 해도 되는 작업 중 가장 많은 시간을 소요하는 작업을 지나는 경로의 시간을 합하면 되므로 3+2+7+10=22분이 된다.
 
  우리는 사실 위와 같은 최적 계획법을 빈번하게 사용하고 있다. 매일 저녁 아내가 최대한 빨리 따끈하고 맛있는 저녁상을 차려낼 때도 최적 계획법이 사용될 수 있으며, 업무를 할 때도 알게 모르게 최적 계획법에 맞게 효율적인 업무를 하고 있을 것이다.
 
 
  총알배송을 위한 경로 - 해밀턴 순환로
 
  ‘주문이 완료되었습니다. 주문하신 상품은 내일 바로 받아보실 수 있습니다.’
 
  평일의 경우 밤 10시 전에 주문한 상품은 다음날 바로 받아볼 수 있다. 배송의 속도 경쟁이 치열한 요즘 총알배송, 로켓배송, 스마트배송 등 이른바 빠른 배송 시스템은 온라인 상품 판매 업체들에 빠져서는 안 될 마케팅 서비스 중 하나로 자리 잡았다. 적은 인력으로 최대한 빨리 배송을 하기 위해서 갔던 길을 다시 돌지 않는 최적 경로를 찾아 배송을 해야 한다. 다음의 경우를 생각해 보자.
 
[예] 택배회사를 출발하여 A, B, C 세 곳을 모두 들러 상품을 배달하고 다시 택배회사로 돌아올 때 가장 효율적인 경로는 어떤 경로인지 생각해 보자. [택배회사 → B → A → C → 택배회사] 이 경로가 왔던 길을 다시 되돌아가지 않는 가장 효율적인 경로가 될 것이다. 단순한 예를 살펴봤지만 이는 그래프 이론 중 최적화 이론의 대표적인 예이다. 이러한 경로를 ‘해밀턴 경로’라고 하는데, 연결된 그래프로 나타낸 경로 중 모든 꼭짓점을 오직 한 번씩만 지나는 경로를 말한다. 해밀턴 경로 중에 출발점과 종착점이 같은 경우는 ‘해밀턴 순환로’라고 한다. 이 해밀턴 경로 이론을 적용할 수 있는 적절한 상황은 세계여행 경로를 계획할 때이다.
 
 
  효율적인 세계일주 경로
 
  세계일주 하는 사람들은 대개 저렴한 비용으로 가장 효율적으로 이동할 수 있는 경로를 찾아 여행 계획을 세운다. 이때 반드시 지켜야 하는 조건은 아래 두 가지이다.
 
  1) 서울을 출발하여 서울로 다시 돌아올 것 2) 모든 나라를 방문하되 동일 나라는 한 번만 방문할 것. 이번에도 역시 예를 들어 생각해 보자.
 
[예] 서울을 출발하여, 홍콩, 뉴욕, LA, 파리, 런던, 두바이를 방문하고 다시 서울로 돌아오는 여행을 계획 중이다. 이용할 수 있는 항공 노선표를 고려했을 때 어떤 경로로 여행을 해야 가장 효율적일까?
 
  위의 모든 노선을 그래프로 그리면 다음과 같다. 이 그래프에서 서울을 출발하여 다시 서울로 돌아오는 최단 경로를 찾아보자. 출발점과 종착점이 같은 경우이므로 앞서 언급한 해밀턴 순환로를 찾으면 된다.
 
  해밀턴 순환로를 찾을 때 반드시 지나야 하는 경로를 먼저 찾으면 훨씬 수월하게 경로를 찾을 수 있다. 이 그래프에서는 홍콩, 런던, LA가 연결된 노선이 2개밖에 없으므로 이 노선들은 입국과 출국으로 모두 이용해야 하는 노선들이다. 따라서 서울-홍콩, 홍콩-두바이, 서울-LA, LA-뉴욕, 뉴욕-런던, 런던-파리 노선은 반드시 이용해야 한다. 그럼 결국 ‘서울-홍콩-두바이-파리-런던-뉴욕-LA-서울’로 순환하는 한 가지 경로(방향만 반대인 경우는 같은 경로로 여긴다)밖에 없다. 즉 이 경로가 해밀턴 순환로가 된다. 이 경로를 따라 여행을 계획한다면, 적어도 갔던 경로를 다시 가게 되는 비효율적인 일정은 피할 수 있게 된다.
 
 
  해밀턴 순환로가 여러 개라면? - 가중치 그래프
 
  해밀턴 순환로만 찾는다고 해서 가장 효율적인 경로를 찾을 수 있을까? 아니다. 예시로 든 세계일주 경로는 해밀턴 순환로가 하나만 존재하기 때문에 효율적인 경로라고 할 수 있겠지만, LA-런던 노선이 새로 추가된 경우로 다시 살펴보자.
 
  위의 그래프에 LA와 런던 사이에 선을 추가로 긋고 해밀턴 순환로를 다시 찾아보자.
 
  위에서 살펴봤듯이 서울-홍콩-두바이까지는 반드시 이용해야 하는 단일 경로지만, 두바이 다음의 경로가 뉴욕으로 가는 경우와 파리로 가는 경우로 나뉜다.
 
  1) 뉴욕으로 가는 경우는 반드시 파리를 거쳐 런던으로 가야 하므로 서울-홍콩-두바이-뉴욕-파리-런던-LA-서울 경로가 해밀턴 순환로가 된다.
 
  2) 두바이에서 파리로 가는 경우는 파리 이후 다음 세 가지 경로가 가능하다.
 
  파리-뉴욕-런던-LA-서울, 파리-런던-뉴욕-LA-서울, 파리-런던-LA-뉴욕-서울
 
  따라서 이 그래프에서 가능한 해밀턴 순환로는 다음 네 가지이다.
 
  경로① 서울-홍콩-두바이-뉴욕-파리-런던-LA-서울
 
  경로② 서울-홍콩-두바이-파리-뉴욕-런던-LA-서울
 
  경로③ 서울-홍콩-두바이-파리-런던-뉴욕-LA-서울
 
  경로④ 서울-홍콩-두바이-파리-런던-LA-뉴욕-서울
 
  그렇다면 이 여러 개의 해밀턴 순환로 중 가장 효율적인 경로는 무엇일까? 우리가 효율성을 따질 때 고려하는 요소는 크게 시간, 거리, 돈 등이 있다. 여기서 거리와 이동 시간은 거의 동일하기 때문에 항공 노선에 따른 항공료를 함께 생각해서 최저비용으로 여행하는 경로를 찾아야 한다. 그래프 위에 노선별 항공료를 적어 네 가지 경우의 비용을 구해보면 다음과 같다.
 
  경로① 1250, 경로② 1450, 경로③ 1450, 경로④ 1330
 
  따라서 경로①로 여행계획을 짜는 것이 가장 효율적인 계획이 된다. 위와 같이 그래프 위에 같은 기준으로 환산한 중요도를 숫자로 적어놓은 그래프를 ‘가중치 그래프’라고 하는데 이는 최단 경로 알고리즘의 바탕이 된다.
 
 
  빠른 길 찾기 - 최단 경로 알고리즘
 
  우리가 빈번하게 사용하고 있는 빠른 길 찾기 애플리케이션의 원리가 바로 최단 경로 알고리즘이다. 최단 경로 알고리즘은 그래프상의 두 정점 사이를 연결하는 경로 중 가장 짧은 경로를 찾는 것을 말한다.
 
  여기서 ‘짧다’는 것은 물리적인 거리 외에도 시간, 거리 혹은 비용, 거리 등 다양한 기준이 적용될 수 있다. 앞서 세계일주 경로를 찾을 때 사용했던 가중치 그래프에서는 거리의 기준을 비용, 거리로 나타냈었다. 이렇게 가중치 그래프로 나타낸 그래프 중 선 위의 값의 합이 최소 또는 최대가 되는 경로를 ‘최적의 경로’ 혹은 ‘최단 경로’라고 말한다. 사실 최적 경로를 찾는 알고리즘은 어떤 거리를 기준으로 가중치 그래프를 그릴 것이며, 또한 어떤 방법으로 최단 경로를 구해나갈 것인지에 따라 여러 가지 접근 방법이 있다.
 
  앞서 우리가 살펴봤던 세계일주의 경우에는 네 가지의 경로를 모두 따져 값을 비교하는 방법을 택했지만, 우리가 사용하는 빠른 길 찾기 앱만 하더라도 해밀턴 순환로가 셀 수 없을 만큼 많을 것이며, 그때마다 모든 경로를 찾아 최단 거리를 계산하여 비교하며 구할 수는 없다. 따라서 최적 경로를 결정하는 효과적인 알고리즘을 찾기 위한 연구가 계속 진행 중인데, 가장 대표적인 최단 경로 알고리즘은 데이크스트라(Dijkstra) 알고리즘이다. 간단히 설명하면, 하나의 출발점에서 다른 모든 지점까지의 최단 경로를 구하는 방법이다. 데이크스트라 알고리즘의 과정은 다음과 같다.
 
  ① 가중치 그래프를 최단 거리를 나타내는 그래프로 만든다.
 
  ② 하나의 출발점을 정하여 직접 이어진 점까지의 최단 거리를 표에 정리하고, 그렇지 않은 점들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다.
 
  ③ 출발점과 거리가 가장 짧은 점부터 경로를 선택하여 다음 점까지의 거리를 또 구한다. 이때 지나간 경로는 색으로 칠한다.
 
  ④ 새로운 경로를 선택하면 그 점과 이어진 점까지의 거리를 구하고 이전에 이미 구한 거리와 비교해 작은 것을 택한다.
 
  ⑤ 그래프의 모든 경로가 색칠될 때까지 ③, ④의 과정을 반복한다.
 
  이 방법이 우리가 사용하는 빠른 길 찾기 앱, 지하철 노선도 앱에 활용되는 알고리즘이다. 또한 도시계획을 할 때 지하철역의 위치와 백화점 위치 등을 정할 때도 이러한 그래프 알고리즘을 이용하여 가장 효율적인 지점을 찾곤 한다.
 
  분명 동일한 시간 조건과 비용 조건 안에서 최적 계획법을 활용하여 조금 더 빨리 일을 끝내고, 가중치 그래프를 그려 최단 경로를 찾아 조금 더 빠른 길로 가는 것은 효율적이다. 그러나 항상 효율적인 것이 좋은 것일까? 라는 의문이 든다.
 
  효율적인 삶도 중요하지만 너무 바쁘게만 달려가는 현대사회에서 때론 자연과 더불어 조금 더 여유롭게 지내는 것도 필요할 것이다.⊙

 월간조선.

수선화(Daffodils)

수선화의 계절이 왔다.
사진은 일본 후쿠오카에서 본 수선화다. 방긋 얼굴을 내미는 듯하다.

  산골짜기 언덕 위 높은 하늘에
  떠도는 구름처럼 이내 혼자서
  지향 없이 떠돌다 보았어라,
  한 무리 모여 있는 황금 수선화.
  호숫가 수목이 우거진 그늘
  미풍에 나부끼며 춤을 추었소.
 
  은하수가 물가 저 멀리
  반짝이며 비치는 별들과 같이
  굽이진 포구의 언덕을 따라
  끊임없이 줄지어 피어 있는 수선화.
  천만 송이 꽃들이
  머리를 흔들면서 춤을 추었소.
 
  주위의 물결도 춤을 추건만
  반짝이는 그 물결 어찌 따르리.
  그처럼 즐거운 친구 속에서
  어찌 시인인들 즐겁지 않으리
  나는 하염없이 바라보았소.
  그 정경(情景)의 보배로움은 생각도 않고.
 
  헛된 생각에 깊이 잠기어
  내 침상 위에 외로이 누웠을 때
  고독의 축복인 마음의 눈에
  홀연 번뜩이는 수선화.
  그때 내 가슴은 즐거움에 넘치고
  마음은 황금 수선화와 함께 춤추었어라.
 
  I wander'd lonely as a cloud
  That floats on high o'er vales and hills,
  When all at once I saw a crowd,
  A host, of golden daffodils;
  Beside the lake, beneath the trees,
  Fluttering and dancing in the breeze.
 
  Continuous as stars that shine
  And twinkle on the Milky Way,
  They stretch'd in never-ending line
  Along the margin of a bay
  Ten thousand saw I at a glance,
  Tossing their heads in sprightly dance.
 
  The waves beside them danced, but they
  Out-did the sparkling waves in glee:
  A poet could not but be gay,
  In such a jocund company:
  I gazed-and gazed- but little thought
  What wealth the show to me had brought :
 
  For oft, when on my couch I lie
  In vacant or in pensive mood,
  They flash upon that inward eye
  Which is the bliss of solitude ;
  And then my heart with pleasure fills,
  and dances with the daffodils.
 
  최창호 역 윌리엄 워즈워스 〈수선화〉
 
 

워즈워스의 대표적인 시가 〈수선화〉다.

  워즈워스의 대표적인 시 〈수선화(Daffodils)〉다.
 
  수선화는 ‘Narcissus’라 하는데 그리스신화에도 나온다. 수선화는 초봄인 2~3월에 꽃이 핀다.
 

사진은 워즈워스가 살던 집이다.

  어디서나 볼 수 있지만 영국 워즈워스 기념관 주변은 수선화가 방긋 얼굴 내미는 호수가 끝없이 이어지는 더 레이크(The Lake), 이름하여 호수의 마을이다.⊙
 

윈즈미어의 초봄, 눈 덮인 대지를 뚫고 수선화가 자취를 보였다.

월간조선