김 용묵의 절대공간 - 블로그

1990년대 초에 바다 건너 미국에서는 바둑, 오목, 체스, 스크래블 같은 보드 게임의 AI 위주로 ‘컴퓨터 올림피아드’라는 대회가 잠깐 개최된 적이 있었다. 기억을 정말 오랜만에 다시 떠올린다. ㅠㅠㅠㅠ
IOI라고 불리는 '국제 정보 올림피아드'와 헷갈리지 마시길. 요즘은 저걸 검색하면 구글도 자꾸 IOI 쪽으로 안내하는 것 같은데 그거랑은 다르다. 컴올은 공식 명칭에 '국제 I'라는 말이 없다. ㄲㄲㄲㄲ

IOI는 대학에 진학하지 않은 중등 수준의 10대 청소년들이 문제 푸는 프로그램을 '즉석에서 작성'해서 그 코드의 성능과 정확도를 평가 받는 대회이다. 그 반면, 저건 현업에 종사하는 소프트웨어 개발자/개발사들이 오랫동안 미리 연구 개발해 놓은 자기 자기 제품의 AI 성능을 현장에서 겨루는 대회이다. 즉, 로봇 쥐 미로 찾기와 비슷하며, 저런 보드 게임을 사람이 아니라 컴퓨터끼리 대국한다는 차이가 있다.

근데 컴터 올림피아드도 첫 대회가 1989년부터 시작됐다니.. 그건 IOI와 동일하다. 그리고 가끔은 IOI에서도 간단한 게임을 진행하는 프로그램을 작성해서 주최측 AI와 대국하고 채점되는 형태의 문제가 나오기는 한다. 그러니 둘이 완전히 다른 별개 분야의 대회까지는 아니긴 하다.

본인이 저 대회에 대해 들어 본 건.. 한때 왕년에 영단어 보드 게임인 스크래블의 AI를 연구하느라 관련 자료를 많이 찾아봤었기 때문이다.
무려 1988년에는 World's fastest Scrabble program (by 앤드루 아펠, 가이 제이콥슨)이라는 논문이 CACM에 게재돼서 후대의 스크래블 AI 개발자에게 아주 큰 영향을 줬다. 모든 가능한 수를 찾는 기본 작업은 이 논문에서 소개된 알고리즘으로 해치우고, 그 뒤에 단순히 당장 점수가 가장 높은 수를 넘어 장기적인 이익을 따지는 건 전략과 휴리스틱의 영역으로..

오래된 생각이긴 하다만, 스크래블 게임의 컴퓨터 구현은 대학교 수준의 자료구조와 알고리즘 코딩 주제로 아주 적합하다. 만약 내가 학원이나 학교에서 저런 전공 과목을 가르칠 기회가 있다면 실습이나 과제로 저걸 꼭 넣었지 싶다. =_=;;
하긴, 석사 논문으로 두벌식 한글 연속입력 오토마타를 연구했던 모 교수님은 자기가 강의하는 형식언어와 오토마타 수업 시간에 한글 입력 오토마타를 구현하는 과제를 고정 편성으로 넣었더구만.. 그런 것처럼 말이다.

아무튼 그건 그렇고..
저 논문을 투고했던 연구진은 딱 이듬해인 1989년, 제1회 컴퓨터 올림피아드의 스크래블 부문에 참가해서 우승했다고 한다. 타이밍 절묘하군..

그 뒤 2회와 3회에서는 Jim Homan이라고 MIT 출신의 다른 엄친아 공돌이가 개발한 스크래블 AI가 2년 연속 우승을 차지했다. 정황상, 아마 저 논문 내용을 바탕으로 AI를 더 발전시킨 것 같다.
그리고 그 사람은 저 AI 엔진을 토대로 CrossWise라는 굉장히 깔끔한 크로스워드 게임(설정을 맞춰서 스크래블 게임도 가능한!!) 프로그램을 개발해서 판매했다.

그것 말고 브라이언 셰퍼드라는 사람이 개발한 Maven이라는 스크래블 AI도 유명했다. 얘도 개발 역사가 1980년대로 거슬러 올라갈 정도로 오래됐고, 스크래블 보드 게임의 총판사에서는 Maven을 공식적으로 밀었다고 하는데.. 얘에 대해서는 나도 더 아는 바가 없다. 이쪽은 딱히 컴올에 참가한 이력도 없는 것 같다.

뭐, 이것도 다 지난 얘기이다. 지금은 스크래블 게임쯤이야 폰이나 웹에서도 돌릴 수 있을 텐데.. 유행이 지난 것 같다.
하다못해 바둑조차도 세계를 석권해 버린 알파고 개발진이 "이젠 바둑은 더 연구할 게 없다~~" 명목으로 발을 뺐을 정도이니 말이다. -_-;;

저 컴퓨터 올림피아드는 스폰서 내지 운영진을 섭외할 수 없어서 1991년 이후부터 1990년대 내내 맥이 끊겼다. 그러다가 2000년대 이후부터 다시 개최는 되고 있지만.. 다들 아시다시피 인지도가 별로 없고 마이너하다는 냄새가 풍긴다. 고전적인 최적화나 휴리스틱 위주의 AI는 유행이 끝나고 닥치고 인공신경망이 대세가 돼서 그런지..??

우리나라에서 보드 게임 AI 외길을 가고 있는 제품은 '장기도사'가 유일하지 싶다. 의미 있는 연구이긴 하다만, 보드 게임이라는 장르 자체도 마이너해지고, AI 패러다임도 마이너해져서 수요가 무척 적을 것 같다. 뭐, 그런 식으로 염세적으로만 따지자면 본인의 주특기인 세벌식 자판도 마이너 중의 초 마이너이긴 하다만 말이다. -_-;;

고전적인 AI 대신 2010년대를 풍미했던 건 인공신경망들이었다. 2012년, 사물 인식을 기가 막히게 잘한다는 AlexNet부터 시작해서 VGG, ResNet, YOLO가 뒤를 잇고 chatGPT, transformer 등등이 쏟아져 나왔으니까.
컴퓨팅 패러다임이 싹 달라졌다. 이 과정에서 파이썬은 머신러닝 학계와 업계의 공용 언어가 되었고, 교육과 실무를 다 장악해 버렸다. ㄷㄷㄷㄷ 파이썬과 루아(Lua)가 처지가 극과 극으로 달라지게 될 줄은 20년 전엔 정말 예상할 수 없었다. 이것도 생각할 점이라 하겠다.

글을 맺기 전에 잠깐.. 그러고 보니 World Cyber games도 생각난다. 얘는 컴퓨터 AI가 아니라 사람이 겨루는 대회이지만, 그래도 E-스포츠 전문이니 뭔가 컴퓨터스럽고 사이버틱한 느낌이 나기 때문이다.
얘도 2001년에 처음으로 시작됐다가 2010년대엔 스폰서를 못 구해서 한동안 중단됐던 적이 있다. 그 뒤 지금은 재개되기는 했지만 권위나 인지도가 예전만 하지는 않다는 게 컴퓨터 올림피아드와 비슷해 보인다.

Posted by 사무엘

1. 행렬의 기본연산

우리는 학교에서 방정식을 푸는 방법에 대해 배울 때, 등식에 대해 너무 당연해 보이는 원리를 배운다.
등식의 양변에 같은 수를 더하거나 빼거나 곱하거나, 나누더라도(비영) 등식은 성립한다는 거.

이건 사실 너무 당연한 얘기이다. 이미 값이 같은 두 수에다가 동일한 수로 동일한 연산을 하면 그 결과도 서로 일치할 수밖에 없다. 그런데 그 당연한 이치만 이용해서 복잡한 방정식을 푸는 게 수학의 묘미이다.
등식의 좌변과 우변을 마법 같이 변형하고 복잡한 항을 옮기거나 없애고, 궁극적으로 좌변에 x 하나만 남기니까 말이다.

그런데 행렬을 다루는 선형대수학으로 가면 이와 비슷한 방법론이 또 등장한다. 이른바 행렬을 줄 단위로 변형하는 기본 연산 말이다.
저 줄이라는 게 가로줄(row 행)인지 세로줄(col 열)인지는 중요하지 않다. 행렬에서 임의의 두 줄을 뽑아서 한 줄의 숫자를 그대로 또는 스칼라(상수)배 한 뒤, 다른 줄에다가 그대로 더해 준다. 두 벡터 A, B에 대해서 A = A + n*B 같은 셈이다.

행렬이라는 건 그냥 방정식이 아니라 변수도 여러 개, 식도 여러 개인 연립방정식을 풀기 위해 도입된 물건이다.
연립방정식을 풀기 위해서 우리가 하는 일은 식에서 변수를 하나씩 소거하는 것이다.
어떤 식은 x y z 변수가 모두 등장하지만 다음 식은 x를 소거하여 y z만 남기고, 마지막 식은 z만 남기고..
그러면 그 z를 y-z 식에다가 대입해서 y를 구하고, 이걸 x-y-z 식에다가 대입해서 x까지 모두 구하면 된다.

이 과정이 행렬로 치면 '삼각화'이다. 행렬이 나타내는 방정식의 특성(= 근)을 변형하지 않으면서 0이 아닌 숫자를 행렬의 반쪽에다가만 남기는 것이다.
그리고 그렇게 삼각화하는 수단이 바로 저 줄 단위 기본연산이다. 없애고 싶은 칸의 숫자를 스칼라배를 통해 동기화시키고 나서 빼 주면 그 칸은 0이 되어 소거된다.

행렬의 기본연산의 묘미는 바로..
한 줄 내용의 상수 배를 딴 줄에다가 아무리 더해 주더라도 행렬 내지 방정식의 전체 특성이 전혀 바뀌지 않는다는 것이다. 특히 그 행렬의 행렬식의 값이 변하지 않는다. 오로지 자기 자신을 상수 배 했을 때만 행렬식 값에도 그 배율이 반영된다.

왜? xyz축을 각각 가리키는 단위 벡터들을 생각해 보자. z축을 1만치 향하는 벡터에다가 완전히 다른 방향인 x, y축을 가리키는 벡터를 제아무리 더해 줘도 z축 방향은 영향을 받지 않는다.
커버하는 벡터 공간이 정육면체이던 것이 찌그러진 평행육면체가 될지언정, 그 육면체의 부피가 바뀌지는 않는다는 걸 생각하면 이해에 도움이 될 것이다. 오로지 z축 자체의 크기를 키워야만 육면체의 부피가 바뀔 것이다.

이 기본연산으로부터 유도 가능한 재미있는 특성이 또 있다.
행렬에서 서로 다른 임의의 두 줄을 맞바꾸는, 다시 말해 교환하는 것을 저 기본연산들의 조합으로 구현할 수 있다. 그리고 이렇게 교환을 하면 행렬식 값이 부호가 바뀐다.

• 임의의 두 줄 (A,B)가 있는데 먼저 A줄에다가 B줄 내용을 빼서 (A-B,B)를 만든다.
• 그 뒤 B에다가 지금 A줄의 값이 돼 있는 A-B를 더해 주면 B가 소거되어 (A-B,A)가 되고..
• A-B가 돼 있는 A줄에다가 지금 B줄의 값인 A를 빼면 (-B,A)가 된다.
• 이제 -B에다가 -1을 곱하면 (A,B)가 (B,A)로 교환이 완료되고.. 이때 행렬식의 부호도 -1이 곱해지면서 바뀐다. 이런 원리 때문이다. =_=;;

이 바닥에서는 피연산자의 순서가 바뀌면 결과의 부호가 달라지는 연산을 심심찮게 보는 것 같다. 벡터곱(외적)이라든가, 사원수 i,j,k끼리의 곱 같은 거 말이다. 행렬의 줄 교환 기본연산도 그런 축에 드는 셈이다.

2. 두 변수 교환

그리고 위의 저 로직은 컴퓨터 코딩깨나 하는 분들에게는 꽤 낯익을 것이다.
임시 변수를 사용하지 않고 두 변수 값을 맞바꾸는 swap 알고리즘과 개념적으로 일맥상통하기 때문이다. 즉, C 코드로 치면 아래 식을 적용한 거나 마찬가지이다. ㄲㄲㄲㄲㄲㄲㄲ

a -= b, b += a, a -= b; a=-a;

물론, 코딩을 할 때는 꼭 합성 대입 연산자에만 집착할 필요는 없으니, 피연산자의 배치 순서를 바꿔서 부호 전환을 축약시키곤 한다.

a += b, b = a-b, a = a-b;

덧셈과 뺄셈 대신, 곱셈과 나눗셈을 써도 되기는 한다. 그러나 이건 실용성이 최악이다.
그렇잖아도 임시 변수 안 쓰는 swap 자체가 실무에서는 딱히 쓰이지는 않고 "이런 테크닉도 있다" 수준으로 짚고 넘어가는 잉여이다. 근데 하물며 swap을 위해서 덧셈-뺄셈보다도 더 무거운 곱셈과 나눗셈이라고??
오버플로 가능성, 피연산자에 0이 있을 때의 문제, 부동소수점인 경우에는 오차 문제.. 정말 할 짓이 못 된다.

사실, 컴퓨터의 입장에서 이런 맞교환 용도로 덧셈· 뺄셈보다도 더 낫고 최고 적합한 연산자는 바로 비트 xor이다. 얘는 같은 피연산자를 두 번 적용하면 도로 원래 숫자로 돌아온다는 마법 같은 특성이 있기 때문이다. (A ^ B)^B = A 다시 말해 xor은 항등원이 0이고 역원은 걍 자기 자신.. 그래서 프로그래머라면 잘 아시다시피

a ^= b, b ^= a, a ^= b;

정말 매끄럽고 단순한 합성 대입 연산자 3방으로 swap이 바로 구현된다. 컴퓨터의 입장에서 xor은 산술 연산보다 속도도 더 빠르며, overflow 문제도 전무하니.. 가히 최적이다.

다만, 다시 얘기하지만 임시 변수 안 쓰는 swap은 실용성이 별로 없다.
연산이 병렬화 이념과 맞지 않으며, 실수로 a와 b에다 같거나 겹치는 메모리 주소를 줘서는 절대로 안 된다.
"하이고, swap 때 변수 하나 줄여 갖고 메모리 얼마나 절약했고 얼마나 팔짜 폈나? ㅋㅋㅋ" 이런 비아냥이 나올 만도 하다.

임시 변수 안 쓰는 swap의 자매품으로는..
O(1)을 초과하는 추가 메모리를 쓰지 않는 n log n 정렬 알고리즘(heap 정렬)이라든가 parent node가 없는 트리 자료구조를 생각할 수 있을 것 같다.
하지만 현실에서는 안정성 있는(stable) n log n인 merge sort라든가, 아예 n^2이지만 아주 가벼운 insert sort가 소규모 한정으로 선호된다. heap sort가 막 메리트가 있다고 여겨지지는 않고 있다.

그리고 parent node 없이 스스로 균형잡는 tree 자료구조의 삽입· 삭제를 구현하는 것 자체는 당연히 가능하다.
그러나 C++에서 제공하는 set, map 부류의 컨테이너들은 가벼운 포인터 기반의 iterator로 원소 순회 기능을 제공하다 보니.. 어차피 다들 node에다가 parent 포인터를 갖추고 있다.

이게 없으면 iterator가 자체적으로 스택을 가진(= 현 순회 상태를 저장) 복잡한 클래스가 돼야만 트리 내부를 순회할 수 있기 때문이다.
뭐, 노드 하나당 8바이트짜리 포인터 오버헤드가 추가됐다고 해서 요즘 세상에 컴퓨터가 메모리가 부족하다고 징징대지는 않는다. ^^

3. 여담

(1) 행렬 얘기를 하다가 프로그래밍 얘기가 너무 길어졌군..;;
아무튼 선형대수학에서 행렬을 다루는 기법을 보면 원소들을 쭉쭉 옮겨서 행렬을 ＼ 모양의 삼각형 형태로 가공하는 게 많다. 삼각형 모양이 된 행렬은 그 대각선상에 있는 원소만 쭈룩 곱하면 행렬식을 구할 수 있고 여러 모로 취급이 편하기 때문이다.

행렬식이나 역행렬을 구할 때는 행렬에다가 앞서 언급했던 기본연산을 적용하면서 행렬을 삼각화하게 된다. 그런데 이 과정을 기록으로 남겨서 원본 행렬을 아예 하삼각행렬과 상삼각행렬의 곱으로 일종의 분해를 할 수 있다. 단, 앞서 등장하는 하삼각행렬은 주대각 성분이 모두 1... 이걸 LU 분해라고 부른다.

(2) LU 분해 말고 PD(P^-1)이라는 세 형태로 행렬을 분해하는 더 어려운 기법도 나중에 다뤄진다. 이건 행렬의 고유값/고유벡터와 관계 있는 더 어려운 개념이어서 나중에 다뤄지는데.. 행렬식이 아니라 행렬의 거듭제곱을 단순한 형태로 표현하게 해 주는 아주 강력한 도구이다.

(a+b) 기호의 다항식을 n승 하면 항이 더덕더덕 늘어나는데, 이는 행렬도 마찬가지이다. 그런데 주대각성분에만 값이 붙어 있는 대각행렬은 n승 해도 항이 늘어나지 않고 마치 스칼라값처럼 자기 자신의 지수만 늘어난다.
PD(P^-1)은 행렬을 대각행렬 D를 포함한 형태로 분해하는 기법이다. 이에 대해서는 나중에 추가로 글로 정리하도록 하겠다.

(3) 임의의 a,b,c...꼴의 원소에 대해서 행렬의 곱셈뿐만 아니라 행렬식이나 역행렬을 구하는 일반적인 공식도 유도할 수는 있다. 그러나 행렬식 하나만 생각해 보면, n 크기 정사각행렬의 행렬식은 계수가 n인 항이 2n이나 n^2, 심지어 2^n개도 아니고 n!개씩 달라붙는다.;; 아시다시피 그 행렬식은 이전 n-1크기 행렬식들을 n개만치 더하고 쪼개는 걸 반복하는 형태로 재귀적으로 정의되기 때문이다.

그렇기 때문에 큰 행렬을 다룰 때 실무에서는 일반적인 공식은 사실상 의미를 갖지 않는다. 그냥 행렬에다 기본연산을 열나 적용한 뒤에 주대각 성분을 곱하고 말지. 이러면 O(n^3) 정도의 복잡도가 나온다. 얘들은 중간 계산 결과들이 저 복잡한 항의 개수를 줄여 주는 거나 마찬가지이다.

FM대로 재귀적으로 행렬식을 구하더라도 다이나믹 기법으로 이전 계산 결과를 적절히 저장하면 시간 복잡도를 팩토리얼에서 다항함수로 바꿀 수는 있을 것이다.
하지만 이건 쪼개진 sub행렬을 기술하는 게 생각보다 빡세고 쉽지 않다.;;; (직접 생각해 보면 이게 무슨 말인지 알 거임. ㄲㄲㄲㄲㄲ) 크기가 다양한 행렬들의 곱셈 횟수를 최소화하는 문제와는 상황이 좀 다르다. 그러니 이러나 저러나 FM은 실용성이 떨어진다는 건 어쩔 수 없어 보인다.

Posted by 사무엘

컴퓨터 알고리즘 문제 중에는.. "N개의 원소로 구성된 목록에서 majority.. 과반/다수파라는 게 존재하는가? 존재한다면 무엇인가?"를 구하는 문제가 있다.
목록에서 과반의 원소가 다 같은 값이면 그게 바로 majority라고 정의된다. 원소들은 꼭 대소 관계가 성립할 필요가 없고 그냥 동등성 판단만 가능하면 된다. 그러니 꼭 정수가 아니어도 된다.

또한, 반반이 아니라 과반이라는 특성상, majority는 존재하지 않거나, 유일하게 존재.. 언제나 둘 중 하나이다. 공동 1위 같은 것도 고려할 필요가 없다.

이 문제는 뭐랄까.. 단순하면서도 참 므흣하다.
일단, "목록에서 가장 자주 등장하는 원소--등장 빈도수가 가장 큰 원소를 구하시오"라고 접근하지 않는 게 핵심이다.
각 원소들의 빈도수를 일일이 관리하자면 알고리즘의 시간 복잡도가 기본이 O(n^2)에서 시작할 것이고, 균형 잡는 tree 기반의 컨테이너를 사용한다 하더라도 O(n log n)이 한계이다.

그러나 이 문제를 풀기 위해서는 일을 그렇게 크게 벌일 필요가 없다.
각 원소의 빈도수가 아니라.. "이 목록은 과반의 원소가 그냥 동일한 값인가?"라고 접근하는 게 좋다.

수학인지 논리학인지 거기에는 "비둘기집의 원리"라는 게 있다. N+1개의 물건을 N개의 상자에다 다 집어넣는다면, 적어도 한 상자에는 그 물건이 2개 이상 들어가 있다. 뭔가 미적분에서 말하는 중간값 정리처럼.. 너무 당연한 말 같은데 말이다.
그것처럼 어떤 목록에 같은 원소가 "과반"이라면 그 목록은 다음 둘 중 한 특성을 반드시 갖게 된다.

• 과반의 원소가 아무리 고르게 분산되어 분포한다 하더라도, 그 원소가 연달아 두 번 이상 등장하는 구간이 반드시 하나 이상 존재한다~! 1 1 2 1 특히 원소의 전체 개수가 짝수라면 이건 뭐.. 무조건 빼박이다.
• 만약 그게 아니라면.. 그냥 맨 마지막 원소가 다수파이다.

어, 정말 저렇게 단정할 수 있나 의아할 텐데.. 이런 과감한 주장은 다수파의 정의가 절반의 '초과', '과반'이기 때문에 성립 가능하다.
절반을 포함하는 '이상'이기만 해도 위의 조건들은 당연히 성립하지 못하게 된다. "1 2 1 2" 같은 것만 생각해 봐도 알 수 있다.

이렇듯, 다수파가 존재할 때 가질 수밖에 없는 목록 전체의 특성을 생각하면.. 다수파를 굉장히 단순한 절차만으로도 정확하게 구할 수 있다.

• 최초엔 맨 첫째 원소가 다수파라고 가정하고 후보로 지정한다. 연속 등장 횟수(이하 점수)도 1을 부여한다.
• 그 다음 원소가 후보 원소와 동일하면 점수를 1 증가시킨다. 그렇지 않으면 점수를 1 감소시킨다.
• 단, 이미 현재 점수가 0이 된 상태여서 더 감소시킬 것이 없으면 후보 자체를 지금의 새 원소로 교체한다. 그리고 점수를 1로 다시 부여한다.
• 이 과정을 모든 원소들에 대해 수행한 뒤, 현재 지정되어 있는 후보를 결과값으로 되돌린다.

위키백과에는 이 과정을 다음과 같이 시각적으로 잘 묘사한 그림이 있더라.
정말 허무할 정도로 단순하다. 이 알고리즘은 고안자의 이름을 따서 Boyer-Moore majority vote algorithm이라고 명명되어 있다. 1981년에 학계에 처음으로 발표됐다고 하는데.. 동작하는 방식을 보니 후보, vote 이란 워딩이 적절해 보인다.

Boyer-Moore 이거 혹시 "문자열 검색 알고리즘에도 나오는 이름이 아닌가?"라는 생각이 들 텐데.. 정확하다. 동일한 명칭이다. ㄲㄲㄲㄲ

단, 위의 알고리즘은 목록에 다수파라는 게 실제로 존재하지 않더라도 언제나 후보를 갖고 있다가 되돌린다. 그러니 목록에 다수파가 존재한다면 정확한 답을 되돌리지만, 애초에 다수파가 존재하지 않는다면 뭔가 임의의 엉뚱한 후보를 되돌린다.

그렇기 때문에 이 알고리즘에는 2nd-pass, 즉 후처리라는 게 필요하다. 앞의 1st-pass를 통해 구해진 후보가 진짜로 다수파가 맞는지, 얘만 개수를 처음부터 다시 세어 보는 것이다.
1st-pass 때 쓰였던 점수 변수는 증가했다가 감소하기를 반복했기 때문에 정확한 개수가 담겨 있지 않다.
이거 무슨 분수· 무리방정식을 풀고 나서 검산을 해서 무연근을 제거하는 것과 비슷한 느낌이다.

자, 두 pass 모두 시간 복잡도는 O(n)이고, 공간 복잡도는 지역변수 꼴랑 한두 개.. O(1)에 지나지 않는다. 정말 놀랍지 않은가?
얘는 알고리즘 자체는 쉽게 이해할 수 있지만, 정말 이렇게만 해도 언제나 문제에 대한 정확한 답이 구해지는지 correctness를 이해하는 게 좀 빡셀 수 있는 문제이다.

알고리즘이라 하면 복잡한 기법을 동원해서 무식하게 풀었을 때 O(n^2)짜리인 것을 O(n log n)으로 낮춘다거나, 팩토리얼/지수함수 급인 것을 O(n^2)나 O(n^3)으로 낮추는 형태인 게 많다.
그러나 최적화를 통해서 이렇게 O(n)을 만들 수 있는 문제는 흔치 않아 보인다.

이 다수파 구하기와 성격이 아주 비슷한 문제는 N개의 숫자 목록 내부에서 "합이 가장 큰 연속된 구간을 찾기"인 것 같다. 당연히 양수와 음수가 뒤죽박죽 섞여 있는 목록에서 말이다.

정답이 (x~y) 구간은 그야말로 1<=x<=y<=N 아무렇게나 가능하기 때문에 이것도 언뜻 보기에는 시간 복잡도가 O(n^2)이나 최하 O(n log n)이 될 것 같다. 그러나 얘도 아주 간단한 검사만 하면서 시간 복잡도 O(n)과 공간 복잡도 O(1) 만으로 아주 빠르게 풀 수 있다.

• 정답 구간이 맨 첫 원소에서 시작된다고 가정하고 각 원소들을 쭉쭉 더해 본다. 그 합이 지금까지 구한 max보다 더 크면 최대값을 갱신하고 정답 구간도 업데이트 한다.
• 그런데 그러다가 합이 음수가 돼 버리면... 그러면 지금까지 살펴봤던 구간은 "더 살펴볼 필요가 없고" 그냥 통째로, 아무 미련 없이 버리면 된다. 그 다음에 양수가 나오는 구간부터 시작점을 새로 설정하고 동일한 과정을 반복한다.

더 살펴볼 필요가 없기 때문에 시간 복잡도 O(n)이 가능한 것이다. 이게 아까 다수파 문제에서 점수가 음수가 돼 버린 시점에서 후보를 깔끔하게 바꿔 버리는 것과 비슷하다. 왜 이렇게 해도 되는지를 생각하는 게 이 문제의 관건이다.

Posted by 사무엘

컴퓨터 소프트웨어계에는 이미 작성되어 있는 프로그램을 실제로 돌려 보지 않고(샌드박스 가상 머신 안에서..) 형태만 들여다보고는 버퍼 오버런이나 메모리 누출 같은 잠재적 위험성 및 논리 결함을 어느 정도 찾아 주는 '정적 분석'이라는 기술이 존재한다. 그 프로그램이 기계어 바이너리 형태이건, 고급 언어 소스 코드이건 형태는 무엇이건 상관없다.

그런데 정적 분석 툴은 그 누가 만든 것이라도 원천적으로 이론적으로 근본적으로 100% 정확하게 작동하지는 못한다.
이에 대해서 "아니 소스 코드가 무슨 자유 의지를 지닌 생명체도 아닌데 그 뻔한 로직을 분석해서 결과를 사전 예측하는 게 그렇게 어려운가? 단순히 소모하는 메모리와 계산량만 많아서 어려운 거라면 컴퓨터의 성능빨로 극복 가능하지 않은가? AI 기술을 접목하면 되지 않는가?" 처럼 생각하기 쉽다.

하지만 그렇지 않다. 그 말은 저런 차원이 아니다.
그런 함수는 단순히 현실적으로 구현하기가 어려운 정도가 아니라 논리 차원에서 모순에 빠지며 존재 불가능하기 때문이다. "모든 창을 막는 방패와 모든 방패를 뚫는 창 세트"와 동급으로 존재 불가능하다~! 창이나 방패의 제조 기술과는 무관하게 말이다.

가장~~ 원초적인 정적 분석 프로그램을 생각해 보기로 한다.
분석할 대상인 프로그램 코드, 그리고 그 프로그램에다가 넘겨줄 입력 데이터.
이 둘을 인자로 받아서 이 프로그램의 시시콜콜한 무슨 메모리 문제 따위를 진단하는 게 아니라..
이 프로그램이 무한 루프에 빠지지 않고 실행이 종료되기는 할지를 정확하게 판단해 주는 bool DoesThisProgramReturn(func, argument) 라는 가상의 함수 프로그램을 생각해 보자.

argument는 현실의 프로그램으로 치자면 명령 인자뿐만 아니라 프로그램이 파일이나 네트워크 형태로 읽어들이는 방대한 입력 데이터까지 모두 포함하는 개념이다. "일괄 처리 형태가 아니라 입출력이 실시간으로 들어오는 프로그램은요?" 이건 이 시점에서 그리 중요한 문제가 아니니 논외로 한다.
func는 뭐.. C/C++로 치면 기계어 코드를 가리키는 함수 포인터 정도로 생각하면 이해하기 편하겠다.

당연한 말이지만 저 함수 자체는 절대로 무한 루프에 빠지지 않고 언제나 유한 시간 안에 답이 나오는 게 보장된다. 무한 루프에 빠지는 프로그램을 의뢰했더라도 말이다. 그러므로 DoesThisProgramReturn(DoesThisProgramReturn, xxx)는 xxx로 무엇을 넘겨주건 그 정의상 리턴값이 언제나 true가 된다.

그럼.. 저 가상의 함수는 어떤 식으로 동작할지를 생각해 보자.
func가 가리키는 코드를 읽으면서 while(true); 같은 패턴을 발견한다거나,
더 구체적으로는 예전에 한번 거쳤던 state와 동일한 state로 이미 지났던 지점을 또 지나는 게 감지되면.. 이 프로그램은 실행이 끝나지 않는다는 결론을 내릴 수 있을 것이다.

이거 만델브로트(망델브로) 집합을 그릴 때 주어진 복소수의 발산 여부를 판별하는 것과 비슷하게 느껴진다.
배배 꼬인 복잡한 프로그램에서는 좀 어렵겠지만 그래도 도저히 불가능한 문제는 아니어 보이는데..??

하지만 튜링 기계는 우리가 흔히 생각하는 것보다 자유도가 더 높은 계산 모델이다.
메모리에 저장된 주소값에 해당하는 다른 메모리의 값을 마음대로 읽고 쓸 수 있을 뿐만 아니라(= 포인터) 거기 저장된 데이터를 코드로 간주해서 실행할 수도 있다(= 함수 포인터).

재귀 호출도 되고.. 또 앞서 살펴보았듯이 DoesThisProgramReturn 자신조차도 튜링 기계에서 실행되는 함수이기 때문에 DoesThisProgramReturn의 인자로 전달할 수 있다. 그리고 분석 대상인 타 함수가 얘를 또 호출할 수도 있다.
이런 상황까지 다 허용 가능해야 한다면 DoesThisProgramReturn의 존재 가능성은 굉장히 난감해진다.

아래와 같이.. DoesThisProgramReturn가 true라고 판정한(= 실행이 끝난다) func에 대해서는 "반대로" 자신이 무한 루프로 가 버리고, 실행이 끝나지 않는 함수에 대해서는 실행을 끝내는 HangIfReturns이라는 함수를 정의해 보자.

bool HangIfReturns(func) {
    if (DoesThisProgramReturn(func, func)) while(true);
    return true;
}

그러니 HangIfReturns(DoesThisProgramReturn)을 하면.. 얘는 무한 루프에 빠지게 된다.
DoesThisProgramReturn은 자기 자신에 대해서는 앞서 정의한 바와 같이 언제나 true를 되돌리고(= 늘 깔끔하게 실행 종료) if문을 만족하기 때문이다. 여기까지는 쉽다.

하지만 반대로 HangIfReturns가 DoesThisProgramReturn의 인자로 들어가면 어떤 일이 벌어질까? DoesThisProgramReturn(HangIfReturns, HangIfReturns)는 리턴값이 무엇이 되는 게 이치에 맞을까? 이제 좀 머리가 복잡해질 것이다.

DoesThisProgramReturn(HangIfReturns, HangIfReturns)가 true라면.. HangIfReturns 안의 if문은 true가 되므로 HangIfReturns은 무한 루프에 빠진다. 그러면 저 함수의 리턴값은 원래 false가 되어야 하게 된다.
반대로 저 리턴값이 false라면.. 역시 이제 HangIfReturns는 실행이 깔끔하게 종료되므로 저 함수의 리턴값을 정면으로 부정하는 결과가 나온다.

요컨대 HangIfReturns가 무한 루프에 빠지는지의 여부는 DoesThisProgramReturn의 리턴값에 따라 달라지는데, 이 과정에서 서로 물고 무는 구조적인 모순이 발생하는 셈이다.
이 모순은 DoesThisProgramReturn라는 함수가 존재한다는 가정으로부터 비롯되었다. 그러니 튜링 기계 하에서 다른 코드의 실행 종료 여부를 완벽하게 판단하는 코드를 똑같은 튜링 기계 기반으로 구현하는 것은 불가능하다는 것이 입증된다.

이 논리는 "정지 문제"(halting problem)이라고 불리며, 컴퓨터라는 기계의 계산 가능 범위를 고민하게 하는 매우 탁월한 통찰이다. 이걸 처음으로 생각해서 논문으로 발표한 사람이 바로 그 이름도 유명한 앨런 튜링이다.

과학 철학에서 "반증 가능한가", 천문학에서 "관측 가능한가"처럼.. 전산학에서는 "계산 가능한가, 튜링 기계를 돌려서 답을 구할 수 있는 문제인가"가 중요한 고민거리가 된다. 계산 자체가 이론적으로 가능해야 그 다음 관심사는 "실용적으로 유의미한 시간 만에 빨리 해결할 수 있는가?", 더 구체적으로는 "입력 크기 N에 관한 다항식 급의 시간 안에 해결 가능한가 (팩토리얼이나 지수 함수 급이 아니라)"라는 시간 복잡도가 될 것이다.

TSP(순회하는 세일즈맨) 문제 같은 NP-완전 문제는 이론적으로 알려진 시간 복잡도가 너무 높기 때문에 실생활에서는 적당히 성능이 좋은 다항 시간 근사 알고리즘이 쓰인다.
그래도 정지 문제는 3-SAT 문제라든가 NP-완전처럼 시간 복잡도를 따지는 증명보다는 덜 난해하고 직관적인 설명도 가능하기 때문에 수식 없이 블로그에다 증명 방식을 소개도 할 수 있다. 현실에서는 논리적으로 100% 완벽하고 헛점이 없고 100% 정확하게 동작하지는 못하지만 그래도 현실적으로 충분히 정확하고 속도도 적절한 각종 소스 코드 정적 분석 기능이 개발되어 쓰이고 있다.

Posted by 사무엘

원소가 0 아니면 1 두 종류밖에 없는 N*N 크기의 어느 정사각행렬 M(N)이 있다. N은 2의 거듭제곱 형태로만 가능하며, M(N)의 생성 규칙은 이러하다.

일단, 크기가 1인 M(1)은 그냥 {0} 하나뿐이다.
그 뒤, M(2*n)은 M(n)의 각 원소들에서 0과 1을 뒤바꾼 놈을 M(n)의 왼쪽과 위쪽, 그리고 좌측 상단에 총 3개 카피를 씌우는 형태로 생성된다. 그러므로 M(2)는

(1 1)
(1 0)

이 되며, 다음 M(4)는 쟤를 뒤바꾼 놈을 또 덧붙여서

(0 0 0 0)
(0 1 0 1)
(0 0 1 1)
(0 1 1 0)

이 된다. 생성 규칙이 이런 식이다.
이런 식으로 M(16), 더 나아가 M(256)을 그림으로 나타내면 이런 모양이 된다.

흐음. 무슨 프랙탈 같기도 하고..
이런 행렬은 고안자의 이름을 따서 Walsh 행렬이라고 부른다.
그런데, 모노크롬이나 16색을 어렵지 않게 접할 수 있던 옛날에 이런 무늬를 화면에다 깔아 놓으면 꽤 근사해 보였을 것 같다~!

이걸 갖고 더 재미있는 장난을 칠 수도 있다.
옛날옛적에 학교에서 전자· 컴공을 전공했던 분이라면 혹시 그레이 코드(gray code)라고 기억하는 분 계신가?
통상적인 2진법과 달리, 숫자가 1씩 증가할 때 언제나 1개의 비트만이 바뀌게 숫자를 특이하게 표현하는 방식이다. 즉, 01111이다가 10000으로 바뀌는 식의 격변이 없다는 것이다. 물론 이런 숫자 인코딩을 갖고 진지한 산술 연산을 할 수는 없지만, 다른 용도로 쓸모는 있다고 한다.

0 1 3 2 6 7 5 4 ...
난 저걸 봐도 비트를 flip하는 규칙 자체를 잘 모르겠다. 숫자가 커질수록 긴가민가 헷갈린다. 솔까말 이거 규칙을 찾는 걸로 IQ 테스트 문제를 내도 될 것 같다.
그런데 일반 숫자를 그에 상응하는 그레이 코드로 바꾸는 공식은 어이없을 정도로 간단하다. x^(x>>1), 다시 말해 자신의 절반값과 자신을 xor 하면 된다.

자, 여기서 끝이 아니다.
저 수열에서 각 숫자들을 구성하는 2진법 비트의 배열 순서를 뒤집어 보자. 10진법으로 치면 1024를 4201로 바꾸는 것과 같다.

비트를 shift나 rotate하는 게 아니라 reverse 하는 건 내가 알기로 왕도가 없다. 그냥 for문 돌려서 1비트씩 차근차근 처리하는 수밖에 없다. 마치 주어진 숫자를 2진법으로 표현했을 때 1의 개수를 구하는 것처럼 말이다.
비트 수가 고정돼 있고 속도가 무진장 빨라야 한다면 미리 계산된 테이블을 참조해야 할 것이다.

N=8이라면 비트 자릿수는 3일 테고.. 0 1 3 2는 2진법으로 각각 000, 001, 011, 010일 텐데,
이걸 뒤집으면 차례대로 000, 100, 110, 010.. 즉 0 4 6 2 ... 형태로 바뀐다. 이 정도면 완전 난수표 수준으로 숫자를 뒤섞은 거나 마찬가지로 보인다.

저 수열이 확보됐으면 그걸 토대로 기존 Walsh 행렬을 개조해 보자. 즉, 지금 줄 배열이 0 1 2 3 4..의 순인데, 그걸 0 4 6 2 ... 즉, 둘째 행(1)에다가 다섯째 행(4)을 집어넣고, 다음 행에다가 일곱째 행(6)을 넣는 식으로 순서를 바꾼다. 그러면..

이런 인상적인 모양의 무늬가 만들어진다. 이것도 크기별로 규칙성이 있다. 좌측 상단은 사각형이 큼직하고, 우측 하단으로 갈수록 픽셀이 조밀해진다.
얘는 여러 명칭으로 불리는데, 통상적으로는 Walsh 행렬의 Hadamard 변환이라고 불린다.
실제 저 행렬/테이블을 구하는 건 아무 프로그래밍 언어로나 10분이면 코딩 가능할 것이다. 참고로 비트 reverse 같은 난감한 동작 없이 저 행렬을 얻는 다른 계산법도 존재한다.

이런 무늬 행렬은 전자공학 신호 처리 쪽에서 쓰인다고는 하는데.. 난 그쪽을 전공하지 않아서 잘 모르겠다. 단지 0과 1만 갖고도 인간 두뇌의 잉여력이 얼마나 폭발할 수 있는지에 경이로움을 느낄 따름이다.

수 년 전에 디더링 패턴의 생성 규칙에 대해 글을 쓰고 나서 이런 재귀적인 무늬를 주제를 다룬 건 무척 오랜만이다. xor은 온갖 난수와 암호도 만들어 내는 이산수학과 정보 이론의 진수임이 틀림없어 보인다. 세상에 이런 게 있다는 걸 알게 됐다는 차원에서 간단히 글을 남기게 됐다.

(xor은 x-y 2차원 평면에다가 진리표를 나타냈을 때 0과 1 결과를 직선 하나로 단순 분류할 수 없는 유일한 연산이기도 하다. 일명 XOR 문제..;; 마치 특정 그래프에 대해 한붓그리기가 불가능한 것과 비슷한 인상을 주는데.. 과거에 한때는 퍼셉트론 무용론과 함께 AI 겨울을 야기한 이력이 있다.)

Posted by 사무엘

1. 완전히 새로운 알고리즘 분야

컴퓨터는 정말 대단한 기계이다.
정보의 최소 단위인 0과 1을 분간하고, 임의의 주소가 가리키는 메모리의 값을 읽거나 쓸 수 있고 프로그램의 실행 지점도 메모리의 값을 따라서 변경 가능하게 했더니(튜링 완전) 그야말로 무궁무진한 양의 정보를 가히 무궁무진한 방식으로 처리가 가능해졌다.

이런 이론적인 근간이 마련된 뒤에 반도체의 집적도가 더 올라가고 메모리와 속도가 더 올라가고 가격이 더 내려가는 건 그냥 시간 문제일 뿐이었다.
그런데.. 단순히 복잡한 계산이나 방대한 검색을 빠르게 해내는 것만으로 컴퓨터가 인간의 고유 영역을 완전히 침범하고 대체했다고 보기는 곤란하다. 그건 그냥 자동차가 인간보다 더 빠르고 중장비가 인간보다 더 힘센 것만큼이나, 기계가 인간의 역할을 일부 보조하고 확장하는 것일 뿐이다.

물론 단순히 동력과 관련된 분야는 말이나 소 같은 동물도 인간보다 약간이나마 더 우위에 있긴 했다. 그에 비해 정보 처리 분야는 자연계에 지금까지 인간의 라이벌 자체가 아예 존재한 적이 없었다는 차이가 있다.
그러나 인간도 속도가 느리고 개인의 능력이 부족할 뿐이지.. 많은 인원을 동원하고 많은 시간만 주어지면 기계적인 정보 처리 정도는 '유한한 시간' 안에 언젠가 다 할 수 있다. 일을 좀 빠르고 정확하게 수행하는 것만 갖고 '창의적이다', '인간을 닮았다'라고 평가해 주지는 않는다.

정렬과 검색에, 다이나믹이니 분할 정복이니 하는 최적해 구하기처럼 고전적인 분야에서 고전적인(?) 방법론을 동원하는 알고리즘은 이미 수십 년 전에 다 연구되어서 깔끔한 결과물이 나왔다. 그런 건 이미 대학교 학부 수준의 전산학에서 다 다뤄지는 지경이 됐으며, 정보 올림피아드라도 준비하는 친구라면 아예 중등교육 수준에서 접하게 됐다.

그런데 현실에서는 그렇게 깔끔하게 떨어지지 않는 더 복잡하고 난해한 문제를 풀어야 한다. 깔끔하게만 접근했다가는 시간 복잡도가 NP-hard급이 되어 도저히 감당할 수 없는 문제를 적당히 타협하여 풀어야 한다.
중· 고등학교의 고전역학 문제에서는 "공기의 저항은 무시한다" 단서가 붙지만, 대학교에 가서는 그런 것까지 다 고려해야 하는 것처럼 말이다.

대수적으로 답을 구할 수 없는 문제에 대해 근사치를 효율적으로 구하기 위해 수치해석이라는 기법이 등장했듯, 전산학에도 각종 휴리스틱과 근사 알고리즘이라는 게 존재한다. 압축 알고리즘으로 치면 무손실이 아닌 손실 분야인 셈이다. 구체적인 건 학부 수준을 넘어 대학원에 소속된 별도의 연구실에서 다룰 정도로 난해하다.

그런데.. 이런 것들은 여전히 사람이 범접하지 못하는 분량의 계산 문제를 최대한 빠르게 효율적으로 푸는 방법에 대한 연구이다. 그런 것 말고 사람은 간단히 하는데 컴퓨터에게는 굉장히 난해해 보이는 일이 있다.
컴퓨터로 하여금 텍스트나 음성 형태의 인간의 자연어를 알아듣고 타 언어로 번역한다거나, 그림으로부터 글자 같은 정보를 알아보게 할 수 없을까?
컴퓨터를 바둑· 장기· 오목 같은 게임의 고수로 키울 수 없을까?

이건 단순히 TSP(순회하는 세일즈맨 문제)를 더 그럴싸한 가성비로 다항식 시간 만에 푸는 것과는 분야가 다르다.
저런 걸 기계가 인간과 비슷한 속도와 정확도로만 해내더라도 굉장한 이득이다. 기계를 부리는 비용은 인간을 고용하는 인건비보다 넘사벽급으로 저렴한 데다, 기계는 인간 같은 감정 개입이 없고 지치지 않고 실수도 전혀 하지 않기 때문이다.

하물며 속도와 정확도가 인간 전문가의 능력을 능가하게 된다면 게임 끝이다. 기계적인 단순 노동력이나 판단력만을 요구하는 일자리는 사라지며, 인간은 기계가 대신할 수 없는 더 창의적이고 전문적인 일자리로 갈아타야 할 것이다.

2. 흑역사

소위 '인공지능'에 대한 연구는 진공관이니 트랜지스터니 하던 무려 1950년대 컴퓨터의 초창기 때부터 천조국의 날고 기는 수학자, 컴퓨터 공학자들에 의해 진행돼 왔다. 특히 세부 분야 중 하나로서 기계번역도 연구됐으며, 1954년에는 조지타운 대학교와 IBM이 공동 연구 개발한 기계번역 솔루션이 실제로 출시되기도 했다.

인류 역사상 최초로 기계번역이란 게 연구된 언어는 러시아어 → 영어이며, 이는 전적으로 냉전 덕분이다. 하긴, 2차 세계 대전 때는 번역이 아니라 암호를 해독하는 기계가 개발되긴 했었다. 적성국가들의 언어 중 일본어는 영어와의 기계번역을 연구하기에는 구조가 너무 이질적이고 어려웠을 것이다.

그래도 인간 번역가가 아닌 컴퓨터가 러시아어 텍스트로부터 영어 텍스트를 허접하게나마 뱉어 내자 학계와 업계는 흥분했다. 이런 식으로 조금만 더 연구하면 컴퓨터가 금방이라도 세계의 언어 장벽을 다 허물어 줄 것 같았다.

그때는 학자들이 자연어에 대해서 뭔가 순진 naive하게 원리 원칙대로 규칙 기반으로, 낭만적으로 접근하던 시절이었다. 인간의 언어도 무슨 프로그래밍 언어처럼 유한한 문법과 생성 규칙만으로 몽땅 다 100% 기술 가능하고 parse tree를 만들고 구문 분석이 가능할 거라고 생각했다. 물론 그 규칙이 간단하지는 않겠지만, 촘스키 같은 천재 언어학자 몇 명을 외계인과 함께 골방에다 갈아 넣고 며칠 열나게 고문하면 다 찾아낼 수 있을 것이고.. 그러면 언어의 기계 분석은 게임 끝이지 않겠냐 말이다.

궁극적으로는 전세계 모든 언어들의 교집합과 합집합 요소를 망라하는 중간(intermediate) 언어도 만들 수 있을 것이라고 생각했다. 세계 각국의 언어들을 그 중간 언어와 번역하는 시스템만 만들면 전세계 사통발달 언어 번역 시스템을 만들 수 있지 않겠는가? 이 정도 생각은 나조차도 한 적이 있다.

그랬으나.. 뚜껑을 열어 보니 영광은 거기서 끝이었다.
기계번역은 빵점 백지 상태에서 4, 50점짜리 답안을 내놓는 것까지는 금방 할 수 있었지만, 거기서 성적을 7, 80점짜리로라도 올려서 실용화 가능한 상품은 오랫동안 연구비를 아무리 투입해 줘도 선뜻 나오지 않았다.
인간의 언어라는 게 절대로 그렇게 호락호락 만만하지 않고 매우 불규칙하고 복잡한 구조라는 게 연구하면 연구할수록 드러났기 때문이다. 지금까지 사용한 연구 방법론 자체가 약발이 다하고 한계에 다다랐다.

이 때문에 1970년대에는 돈줄을 쥔 높으신 분들이 "인공지능"이란 건 밥값 못 하는 먹튀 사기 허상(hoax)일 뿐이라고 매우 비관적이고 보수적으로 생각하게 됐다. 컴퓨터는 그냥 계산기일 뿐, 그 돈으로 그냥 인간 번역가나 더 양성하고 말지..
이 단어 자체가 학계의 흑역사 급으로 금기시되어 버렸다. 인공지능이란 게 키워드로 들어간 논문은 저널에서 믿고 걸러냈으며, 관련 연구들의 연구비 지원도 모조리 끊길 정도였다.

이 현상을 학계에서는 제1차 AI 겨울(혹한기, 암흑기, 쇼크, 흑역사 등등...)이라고 부른다. 과거의 무슨 오일 쇼크 내지 게임 업계 아타리 쇼크처럼 말이다.
그렇게 고비를 겪었다가 더 발달된 연구 방법론으로 활로가 발견되고, 그러다가 또 2차 겨울을 극복한 뒤에야 요 근래는 인공지능의 중흥기가 찾아왔다고 여겨진다.

3. 문제는 데이터

지금은 기계번역이건, 게임 AI이건, 패턴인식이건 무엇이건.. 인공지능의 주재료는 규칙이 아니라 데이터이다.
기계번역 시스템을 개발하는데 언어학 문법 지식이 동원되지 않으며, 보드 게임 AI를 만드는데 통상적인 게임 규칙 기반의 알고리즘이 동원되지 않는다. 이상한 노릇이 아닐 수 없다.

그러는 게 아니라 요즘 인공지능이라는 것은 아이디어는 매우 간단하다. 기출문제와 정답을 무수히 많이, 인간이 상상할 수도 없을 정도로 많이 주입시켜 준 뒤, 이로부터 컴퓨터가 규칙성을 찾아내고 새로운 문제가 주어졌을 때 정답을 추론하게 하는 방법을 쓴다. 해결하고자 하는 문제를 기술하고 정답의 조건을 명시하고 알고리즘을 구현하는 걸 인간이 일일이 하는 게 아니라.. 그 자체를 컴퓨터가 알아서 하게 하는 것이다.

이것이 '기계학습', 그 이름도 유명한 machine learning이다. 이것이 이전에 인공지능을 구현하는 방법론이던 '전문가 시스템'을 대체했다. 이런 무지막지한 방법론이 적용 가능할 정도로 요즘 컴퓨터의 속도와 메모리가 매우 크게 향상된 덕분이다.

인간의 입장에서 기계학습을 시키는 방식은 지도(supervised learning) 또는 비지도 학습으로 나뉜다.
그리고 기계의 입장에서 학습(?)을 실제로 수행하는 방법으로는 인공 신경망, 앙상블, 확률(은닉 마르코프 모델), 경사/기울기 하강법 같은 여러 테크닉이 있는데, 기울기 하강법은 복잡한 선형 방정식을 푸는 심플렉스와 비슷하다는 느낌도 든다.

인공 신경망은 생물의 신경망이 동작하는 원리에서 착안하여 만들어진 기계학습 모델이라고는 하지만 당연히 실제 인간 뇌의 작동 방식에 비할 바는 못 된다.
MLP니 CNN이니 RNN이니 하는 신경망 용어들이 존재하며, 그리고 이 인공 신경망을 어떻게 하면 잘 갖고 놀 수 있을까 고민하는 연구 분야를 '딥 러닝'(심층학습)이라고 한다. 마치 네트워크 계층의 다양한 기술 용어만큼이나 AI에도 계층별로 다양한 기술 용어가 존재한다.

게임 AI라면 단순히 뭔가를 인식하고 분류만 하면 장땡인 게 아니라 뭔가 극한의 최적해를 찾아가야 할 텐데.. 이런 걸 학습시키는 건 딥 러닝의 영역이다. 알파고처럼 말이다. 그런데 알파고 하나가 지구상의 최고의 인간 바둑 기사를 이긴 것은 물론이고, 다른 재래식 알고리즘으로 십수 년간 개발되어 온 기존 바둑 AI들까지도 다 쳐발랐다니 무서운 일이 아닐 수 없다. 뭐, 개인용 PC 한 대만으로 그렇게 동작하는 건 아니긴 하지만 말이다.

오늘날 연구되고 있는 인공지능은 무작정 인간과 동급으로 생각하고 창조하는 기계는 당연히 아니고, 컴퓨터의 막강한 메모리와 계산 능력으로 지금까지 주어진 데이터를 토대로 새로운 상황에 대처하는 답안을 꽤 그럴싸하게 제시하는 '약한 인공지능'일 뿐이다.

쉽게 말해 "서당 개 삼 년이면 풍월 읊는다"처럼 말이다.
추리소설를 한 1000편쯤 읽고 나니 다른 새로운 추리 퀴즈에도 설정이 뻔히 보이고 답이 보인다.
드라마를 1000편쯤 보고 나니 비슷비슷한 드라마들은 스토리 전개가 어찌 될지 '안 봐도 비디오'처럼 된다. 그런 것 말이다.

그런데 저게 말처럼 쉬운 일인 건 아니다.
학습 대상인 무수한 텍스트· 이미지· 음성 데이터 내지 각종 게임 복기 데이터를 어떤 형태로 수치화해서 벡터 형태로 표현할 것인가?
그리고 '학습'이라는 걸 하는 동안 해당 AI 엔진의 내부에서는 구체적으로 무슨 계산 작업이 행해지는가?
컴파일러만 해도 결과물로 OBJ 파일이라는 게 생기는데, 그 내부적인 학습 상태는 어떤 형태로 표현되며, 이것만 따로 저장하고 불러오는 방법이 존재하는가? 본인은 AI알못이다 보니 전혀 모르겠다. ㅡ,.ㅡ;;

수천, 수만, 아니 그 이상 셀 수 없이 많은 숫자들로 이뤄진 벡터 I가 또 수없이 많이 있다고 치자. 이 숫자들은 현실 세계를 표현하는 미세한 자질을 표현한다.
그런데 어떤 블랙박스 함수 f가 있어서 f(I_1..n)에 대한 결과가 O_1..m라는 벡터 집합으로 나왔다고 한다.

컴퓨터는 이 I와 O 사이에서 규칙성을 찾아서 I에 대해 O와 최대한 비슷한 결과를 산출하는 함수 f를 구한다. 그러면 이제 임의의 다른 아무 input에 대해서도 수긍할 만한 출력 결과를 얻을 수 있을 것이다.
패턴 인식? 기계번역? 유사 작곡이나 창작? 현실에서 해결하려는 문제가 무엇이건 machine learning이 하는 일은 본질적으로 저걸로 요약된다. 내가 AI 쪽으로 아는 건 이게 전부이다.

지금은 TensorFlow 같은 범용적인 기계학습 엔진/라이브러리까지도 구글 같은 괴물 기업에 의해 오픈소스로 몽땅 풀려 있으며, 이걸 파이썬 같은 간편한 스크립트 언어로 곧장 돌려볼 수도 있는 세상이 됐다.
그런 라이브러리를 직접 개발하고 유지보수 하는 것까지는 바라지도 않는다. 방대한 현실 데이터를 수집해서 저기에다 적절하게 집어넣고, 이로부터 고객이 원하는 유의미한 추세나 분석 결과를 얻는 것만 해도 뭔가 프로그래밍 코딩과는 별개로 아무나 할 수 없는 전문 영역의 일이 돼 있다.

오늘날 AI 엔진의 연구를 위해서는 근간 이론이라 할 수 있는 선형대수학, 편미분, 확률 통계는 무조건 먹고 들어가야 된다. 엔진 코드를 직접 다루지 않고 쓰기만 하는 사람이라도 엔진이 어떤 원리로 돌아가는지 정도는 알아야 가장 적절한 방법론/알고리즘을 선택할 수 있을 테니 저런 것들을 맛보기 수준으로라도 알아야 할 것이다.

과거에 정보 사냥 대회가 있었던 것처럼 이제는 주어진 데이터로부터 새로운 문제를 잘 푸는 기계학습 모델을 설계하는 것이 경진대회의 아이템 내지 학교와 직장의 과제가 될 것으로 보인다. 컴퓨터가 할 수 있는 일이 더 늘어난다면 사람만이 할 수 있는 일은 그보다 더 수준 높고 추상적인 쪽으로 이동할 수밖에 없으니 말이다.

아무리 그래도 그렇지 자연어의 문법과 어휘 자체를 전혀 모르는 상태에서 데이터 학습만으로 댓글이 선플인지 악플인지를 기계가 분간할 수 있는 걸까? 그래도 클레멘타인 영화에 늘어선 댓글이 선플인지 악플인지 판단하려면 그에 대한 특별한 학습-_-;;이 필요할 것 같다.

그리고 변화무쌍 복잡한 필기체의 인식이 아니라, 그냥 자동차 번호판의 정향화된 숫자 내지 겨우 QR 코드의 인식 정도는.. '영상 처리 기술'의 영역이지, 저 정도의 거창하게 기계학습이니 뭐니 하는 인공지능의 영역은 아니다. 그건 구분해서 생각할 필요가 있다.

오래 전부터도 각종 전산학 알고리즘 용어를 검색할 때 종종 걸려 나오긴 했는데.. 국내 개인 사이트 중에 AIStudy라는 곳이 있다. 나모 웹에디터가 있던 시절부터 존재했던 정말 옛날 사이트이다. 그런데 운영자가 내 생각보다 굉장히 어린 친구이다. 정말 대단할 따름이다.
당연히 과학고-카이스트 라인이려나 생각했는데 그렇지는 않고 일반고-서울대 테크를 타 있다. 앞날에 건승을 빌어 본다.

Posted by 사무엘

C 언어는 가히 프로그래밍 언어계의 라틴어라 해도 과언이 아닌 대중적인 언어가 돼 있다. 얘는 알골(Algol), 그 다음으로 B라는 언어의 뒤를 이어 단순하게 C라고 명명되었으며 1972년에 만들어졌다. 이걸 보면 컴퓨터계에서 3.0 버전이 흥행 대박 친다는 법칙은 언어 분야에서도 유효한 것 같다.

C 언어의 고안자는 '데니스 리치'이다. 이 사람은 지난 2011년 가을에 마침 스티브 잡스와 거의 1주일 간격으로 나란히 작고했다(잡스가 먼저). 그래서 컴퓨터쟁이들 사이에서는 둘 중 덜 유명한 사람이 사실은 컴퓨터계에 훨씬 더 큰 공헌을 했다는 요지의 글을 올리곤 했다.

C는 기본적으로 컴파일 형태로 빌드되는 언어이며, 1990년대를 전후해서 16비트 도스 시절엔 볼랜드라는 회사에서 개발한 터보 C 컴파일러가 아주 대중적으로 쓰였다.
그러나 터보 C보다 이전에 IBM PC용으로 최초로 등장한 C 컴파일러는 Lattice C라고 다른 회사 제품이었다. 1982년인가 그렇다. 이게 그 먼 옛날에 타 플랫폼용으로 개발된 프로그램들을 도스용으로 포팅하는 데 중요한 선구자적 역할을 했다. 얘가 당대의 다른 후속 경쟁사 컴파일러들에 비해 코드 생성 성능도 좋았다고 한다.

사실은 Microsoft C도 Lattice C를 기반으로 개발되었다. 그러다가 1985년에 개발된 MS C 3.0부터 마소가 완전히 독자적인 컴파일러 개발 라인을 구축했다고 영문 위키백과를 보면 나온다. 브라우저에다 비유하자면 IE의 소스에서 모자이크의 소스를 완전히 떼어낸 것과 비슷한 격이겠다.

Windows의 경우 1.0은 처음에 파스칼로 개발되었으며, 이거 영향으로 실행 바이너리들을 들여다보면 export 심벌들의 명칭은 대소문자 구분이 없고 문자열도 앞에 길이가 기록된 형태로 저장되었다고 한다. 대소문자 구분이 없는 건 확실하게 본 기억이 있는 반면, 후자는 잘 모르겠다.

물론 초창기에도 파스칼이 아닌 C언어 기반의 Windows SDK가 있긴 했다. Windows 1.0 SDK의 경우 바로 저 초창기의 MS C 3.0까지는 아니고 4.0과 연계해서 동작했던 걸로 기억한다. 운영체제(?)의 개발과 컴파일러의 개발이 나름 병행되었던 셈이다. 그래도 뭐, 파스칼의 흔적이 어떤 형태로든 과거에 존재했기 때문에 PASCAL이라는 calling convention 명칭도 오늘날까지 legacy로 버젓이 전해지는 아닌가 싶다.

그러다 Lattice C는 1980년대 후반에 개발사가 타사에 인수되었으며 물건 역시 MS, Borland 같은 후발주자 대기업(?) 제품에 밀려서 역사 속으로 사라졌다. C를 제외하면 볼랜드는 파스칼을 민 반면, 마소는 빌 게이츠의 입김과 추억이 담긴 Basic을 밀었다. 베이직이 Quick-을 거쳤다가 나중에 폼 디자인 기능이 탑재된 Visual Basic이 되었다면, C 계열은 Quick-을 거쳤다가 C++ 언어에 MFC까지 탑재하여 Visual C++이라는 공룡으로 거듭났다. 물론, 그래도 VC에 지금과 같은 IDE의 프로토타입이라도 갖춰진 물건은 또 한참 뒤인 4.0 (1995)부터이다.

도스 시절에는 Turbo/Borland라는 브랜드로 볼랜드 컴파일러가 심지어 마소의 컴파일러조차도 따돌리며 리즈 시절을 구가했다. 1990년대 중반이 되면서 32비트 도스라는 틈새시장을 겨냥해서 Watcom, DJGPP 같은 제품이 꼽사리로 꼈을 뿐이며, 정작 마소와 볼랜드는 32비트 도스 플랫폼 지원은 상대적으로 미흡했다.

허나, Windows 95/NT가 널리 퍼지면서 주력 C/C++ 컴파일러는 Visual C++로 판도가 급격히 기울었다. Lotus 1-2-3이 하루아침에 급격히 밀리고 Excel이 천하를 평정했으며, 넷스케이프가 90년대 말에 정말 급격히 몰락한 뒤 IE 세상이 된 것처럼 말이다. 컴파일러는 브라우저처럼 무슨 끼워팔기 독점 같은 게 있지도 않았는데 어쩌다 상황이 바뀌었는지 모르겠다. (옛날엔 플랫폼 SDK와 함께 제공되던 공짜 컴파일러는 상용 Visual C++와 동급의 고성능 컴파일러가 아니었음)

자, 그럼 다음으로 C에 이어 C++도 언어와 컴파일러 역사를 회고해 보겠다. C++은 1970년대 말에 C with Classes라는 가칭으로 개발되었다가 1983년에 지금의 이름으로 첫 발표되었다. C++의 고안자는 덴마크 사람이다. 그리고 초기의 몇 년 동안(1980년대 중반) C++은 인지도가 안습했던 관계로 독자적인 컴파일러가 존재하지 않았다.

오늘날 C++의 위상과 지위를 생각하면 저런 시절이 존재했다는 게 믿어지지 않는다만, 그때는 C++ 코드를 C 코드로 변환해 주는 Cfront라는 전처리기 형태로 C++의 구현체가 명맥을 이었다. 말은 전처리기라고 했지만 소스 코드를 완전히 분석하고 변환하는 것이기 때문에 기술 수준은 엄연히 전처리기를 넘어 컴파일러의 front end급은 된다.

그러다가 C++ 직통 컴파일러가 등장한 것은 1980년대 말~1990년대 초이다. 메이저한 개발사인 볼랜드와 마소에서 C++ 컴파일러를 내놓은 것은 역시나 빨라도 1990년과 그 이후부터이지만, 1980년대 말에.. 그래픽 카드로 치면 VGA의 등장과 비슷한 시기에 C++ 직통 컴파일러를 내놓은 제조사도 있었다.
IBM PC/도스용으로는 Zortech C++가 그런 선구자 축에 든다. 딱 우리나라가 올림픽 하던 시절과 얼추 비슷하게 첫 작품이 나왔다.

Zortech C++은 훗날 1993년경에 Symantec C++ 이라고 브랜드 이름이 바뀌어서 6~7.x 버전까지 개발되었다. 도스와 OS/2, Windows (16/32비트)를 모두 지원하는데 역시나 볼랜드, 마소, 왓컴 같은 다른 브랜드에 밀려서 인지도는 그리 높지 못했던 듯하다.
본인은 먼 옛날에 어둠의 경로를 통해서 이 컴파일러 자체는 접한 적이 있다. Hello, world!만 출력하는 프로그램을 빌드해 봤는데 exe의 크기가 꽤 작게 나왔던 걸로 기억한다.

그리고 Zortech / Symantec C++ 컴파일러의 개발자는 Walter Bright이라고.. 프로그래밍 언어 연구와 컴파일러 개발에만 뼈를 묻은 유명한 아저씨이다. 원래 전공은 전산· 컴공도 아닌 기계공학인데 프로그래머로 전업 후, 컴공에서 최고로 어려운 분야 축에 드는 컴파일러를 곧장 파기 시작했다는 게 대단하다.
이 사람이 D 언어의 고안자이기도 하다는 걸 본인은 최근에 알게 됐다. D에 대해서는 개발자 개인이 아니라 Digital Mars라는 개발사의 이름만 알고 있었기 때문이다.

C++ 컴파일러를 개발하는 현업에 수십 년 종사했으니 그는 C++의 언어 구조와 빌드 과정에 존재하는 구조적인 비효율과 단점에 대해서 누구보다도 잘 알고 있을 것이다. 그러니 자신의 경험과 노하우를 집약해서 네이티브 코드 컴파일 언어이면서 C/C++의 단점을 보완한 새로운 언어를 직접 만드는 지경에 이르렀다. 하지만 D의 지지자· 사용자들이 어떻게든 똘똘 뭉쳐서 언어의 인지도를 끌어올리는 데 목숨을 걸어도 시원찮을 판에, 런타임 라이브러리가 Phobos와 Tango로 분열되고 커뮤니티가 폭파되는 큰 악재를 겪기도 한 모양이다.

거기에다 C++ 자체도 2010년대부터는 부스터를 단 듯이 언어와 라이브러리가 모두 하루가 다르게 미친 듯이 발전하는 중이다. 이게 과연 내가 알던 그 C++가 맞나 싶은 생각이 들 지경이며, 오죽했으면 같은 C++로도 이런 새로운 패러다임을 잔뜩 도입해서 코딩을 하는 걸 Modern C++이라는 비공식 명칭으로 따로 일컬을 정도이다. 이대로 가면 인클루드의 단점을 개선하는 import/패키지 기능까지 가까운 미래에 C++에 도입될 추세다. 그러니 "호환용 레거시가 너무 지저분하다"처럼 태생적으로 어쩔 수 없는 것 빼고는 단점들이 의외로 많이 해소되었다.

그걸로도 모자라서 다른 대기업이나 오픈소스 진영에서도 Rust처럼 네이티브 기반이면서 독특한 패러다임을 담고 있는 언어를 내놓고 있으니 D 역시 자신만의 메리트와 경쟁력을 확보하기 위해서는 갈 길이 아직 먼 것 같다.
C에서 파생형 언어 명칭을 만든 게 C++, C#뿐만 아니라 D라니 참 재미있다. C++뿐만 아니라 C#도 고안자가 덴마크 사람이라니 저 나라도 의외로 전산 강국인 듯하다.

(여담이지만 Walter Bright 아저씨는 컴파일러 개발자 겸 PL 연구자로 이름을 날리기 전인 1970년대부터 이미 Empire이라는 턴 기반 전략 시뮬 게임을 만들기도 했다. 워낙 너무 옛날이니 오늘날과 같은 컴퓨터에서 컬러 그래픽이 나오는 형태의 게임은 아니었겠지만, 아주 어린 시절부터 정말 비범한 분이었다는 건 확실해 보인다. 게다가 저 작품은 전략 시뮬 장르에서 맵의 전체 시야를 노출해 주지 않는 fog of war라는 개념을 첫 도입한 선구자이기도 하다고 한다.)

Walter Bright 말고, 또 볼랜드나 마소 계열도 아니면서 C++ 골수 덕후인 컴파일러 제조사가 하나 더 있다. 바로 Comeau. C++98이던가 03 시절에 그 악명 높은 템플릿 export 키워드를 유일하게 손수 다 구현한 이력도 있는 대단한 용자이다. 얘들 역시 1989년 초에 곧장 C++ 컴파일러를 내놓았으며, 그때부터 도스와 OS/2 등 다양한 플랫폼을 지원했는데, 거기 내부엔 또 어떤 출신과 배경을 가진 컴파일러/PL 괴수가 기업을 이끌고 있나 궁금해진다.

Comeau 컴파일러는 오늘날은 프런트 엔드로는 Edison Design Group의 제품을 사용하여 동작한다. 그럼 저 업체와는 어떤 관계인지 궁금하다. 그리고 프런트가 그런 관계이면 쟤들은 최적화와 타겟 코드 생성 같은 백 엔드 쪽에 차별화 요소가 있어야 할 텐데.. 백 엔드로는 아예 CPU 제조사라는 결정적인 텃새가 있는 인텔 컴파일러도 강세 아니던가? 그런 제품과 경쟁이 되려나 모르겠다.

이상. 이 글은 볼랜드나 마소 같은 유명 대기업 계열이 아니고 그렇다고 gcc 같은 오픈소스 진영도 아니면서 C/C++ 컴파일러를 상업용으로 제일 먼저 PC에다 구현했던 선구자들이 누군지를 문득 생각하면서 끄적여 보았다.

Posted by 사무엘

지금 와서 가만히 생각해 보니, 컴퓨터 알고리즘을 동원하여 푸는 문제들은 다음과 같은 세 범주로 나눌 수 있는 것 같다. 뒤로 갈수록 설명이 길어진다.

1. 최적해를 다항 시간 만에 구할 수 있으며, 직관적인 brute-force 알고리즘과 뭔가 머리를 쓴 알고리즘이 시간 복잡도 면에서 충분히 유의미한 차이를 보이는 문제

간단한 발상의 전환으로 인해서 속도가 드라마틱하게 빨라질 수 있고, 알고리즘에 대한 정량적인 분석도 어렵지 않게 다 되는 경우이다. 요런 게 알고리즘 중에서는 가장 무난하다. 정보 올림피아드에도 이런 부류가 가장 많이 나온다.
가장 전형적인 예는 시간 복잡도 O(n^2)가 O(n log n)으로 바뀐다거나, 지수함수 복잡도가 O(n^2)로, 혹은 O(n^3)이 O(n^2)로 바뀌는 것이다. 물론 시간 복잡도를 줄이기 위해서는 공간 복잡도가 시공간 trade-off 차원에서 추가되는 경우가 대부분이다. 중간 계산 결과들을 모두 저장해 놓는 다이나믹 프로그래밍 문제가 대표적인 예이다.

정렬, common subsequence 구하기, 그래프에서 최단거리 찾기 같은 깔끔하고 고전적인 문제들이 많다. 기하 분야로 가면 convex hull 구하기, 거리가 가까운 두 점 구하기도 있다. 하지만 세상에 산적한 문제들 중에는 이 1번 부류에 속하지 않는 것도 많다.

2. 최적해를 다항 시간 만에 구하는 것이 가능하지 않은 (것으로 여겨지는) 문제

P에는 속하지 않지만 NP에는 속하는 급의 문제이다. 이건 다항 시간 만에 원천적으로 풀 수 없는 문제를 말하는 게 아니며 개념과 관점이 사뭇 다르다. 비결정성 튜링 기계라는, 실물이 없는 이론적인 계산 기계에서는 그래도 다항 시간 안에 풀 수 있다는 뜻이다.

입력 데이터의 개수 n에 비례해서 상수의 n승 내지 n 팩토리얼 개수의 가짓수를 일일이 다 따져야 하는 문제라면 다항 시간 만에 풀 수가 없다. 그런데 실생활에는 이런 무지막지하게 어려운 문제가 은근히 많이 존재한다. 진짜 말 그대로 n!개짜리 뺑이를 쳐야 하는 외판원 문제가 대표적이고, 그래프에도 '해밀턴 경로 문제'처럼 이런 어려운 문제가 산적해 있다. 이런 분야의 문제는 소위 말하는 NP-complete, NP-hard이기도 하다.

요런 문제는 brute force 알고리즘으로는 대용량 데이터를 도저히 감당할 수 없고 그렇다고 다항 시간 최적해 알고리즘이 있는 것도 아니기 때문에, 이런 문제는 100% 최적해는 포기하고 그 대신 95+n%짜리로 절충하고 시간 복잡도는 O(n^2)로.. 뭔가 손실 압축스럽게 tradeoff를 하게 된다.
국제 정보 올림피아드에는 이런 문제가 많이는 안 나오지만 전혀 안 나오는 건 아니다. 출제된다면 답은 최적해와의 비율로 점수가 매겨지며, 프로그램 실행이 아닌 그냥 제출형으로 출제되기도 한다.

P와 NP 사이의 관계는 전산학계에서 만년 떡밥이다. 현실에서는 마치 장기간 실종자를 법적으로 사망한 것과 마찬가지로 간주하듯이 P와 NP는 서로 같지 않다고 여겨지고 있다. 이를 전제로 깔고 발표된 연구 논문들도 수두룩하다. 하지만 그게 정말로 딱 그러한지는 전세계의 날고 기는 수학자들이 여전히 완벽하게 규명을 못 하고 있다.

엔하위키에는 P!=NP임을 증명하는 사람은 전산학 전공 서적에 이름이 실릴 것이고, P=NP임을 증명하는 사람은 아예 초등학생 위인전에 등재될 것이라고 얘기를 했는데... 적절한 비유인 것 같다. 지수함수 brute force 말고는 답이 없는 문제가 좀 있어야 암호와 보안 업계도 먹고 살 수 있을 텐데..!

3. 최적해를 다항 시간 만에 구할 수 있음이 명백하고, naive 알고리즘도 실생활에서 그럭저럭 나쁘지 않은 결과가 나오지만, 그래도 미시적· 이론적으로는 최적화 여지가 더 있는 심오한 문제

말을 이렇게 어렵게만 써 놓으면 실감이 잘 안 가지만 이 그룹에 속하는 문제의 예를 보면 곧장 "아~!" 소리가 나올 것이다. 이 분야에도 어려운 문제들이 은근히 많다.

(1) 문자열 검색
실생활에서는 그냥 단순한 알고리즘이 장땡이다. 원본 문자열을 한 글자씩 훑으면서 그 글자부터 시작하면 대상 문자열과 일치하는지 처음부터 일일이 비교한다. 실생활에서 텍스트 에디터는 대소문자 무시, 온전한 단어 같은 복잡한 옵션들이 존재하며 각 글자들의 변별성도 높다(대상 문자열과 일치하지 않는 경우 첫 한두/두세 글자에서 곧바로 mismatch가 발생해서 걸러진다는 뜻). 그 때문에 그냥 이렇게만 해도 딱히 비효율이 발생할 일이 없다.

하지만 문자열 검색이라는 건 실무가 아닌 이론으로 들어가면 생각보다 굉장히 심오하고 난해한 분야이다. 원본과 대상 문자열이 자연어 텍스트가 아니라 오로지 0과 1로만 이뤄진 엄청 길고 빽빽하고 아무 치우침이 없는 엔트로피 최강의 난수 비트라고 생각하자. 그러면 예전에 패턴이 어디서부터 어긋났는지를 전혀 감안하지 않은 채 오로지 1글자씩만 전진하는 방식은 효율이 상당히 떨어진다. 이제야 좀 더 똑똑한 문자열 검색 알고리즘이 필요해진다.

퀵 정렬의 중간값(pivot) 선택 알고리즘을 의도적으로 엿먹이는 '안티' 데이터 생성 알고리즘만큼이나..
특정 문자열 검색 알고리즘을 엿먹여서 언제나 최악의 경우로 한 글자씩만 전진하게 만드는 문자열 데이터를 생성하는 안티 알고리즘도 있을 것이다.

(2) 팬케이크 정렬
a1부터 a_n까지 임의의 수 배열이 존재하는데, 우리가 이 수열에 대해 취할 수 있는 동작은 여느 정렬 알고리즘처럼 임의의 두 원소끼리의 교환이 아니다. 1~2, 1~3 또는 1..m (m<=n)처럼 첫째부터 m째의 원소들을 모조리 역순으로 뒤집는 것만 가능하다. 1 7 4 2였으면 2 4 7 1로 바꾼다는 것. n개의 임의의 수열이 있을 때 수열을 정렬하기 위해 필요한 이론적인 최대 뒤집기 횟수는 정확하게 얼마나 될까? 한꺼번에 몇 개를 뒤집건 한번 뒤집는 데 걸리는 시간은 무조건 상수라고 가정하고, 뒤집기 자체 외에 다른 계산의 비용(가령, 현 구간에서 maximum 값을 찾는 것)은 전혀 고려하지 않아도 된다.

본인은 아주 어렸을 때 GWBASIC 교재에서 이 팬케이크 정렬 문제와 같은 방식으로 수열을 뒤집어서 "사람으로 하여금 문제를 풀게 하는" 프로그램을 본 기억이 있다. 프로그램의 이름이 REVERSE였다.
이 문제는 마치 선택 정렬과 비슷한 방식으로 명백한 해법이 존재한다. 가장 큰 수가 m째 원소에 존재한다면 m만치 뒤집어서 가장 큰 수가 맨 처음에 오게 한 뒤, 판 전체를 뒤집어서(n만치) 그 수가 맨 뒤로 가게 하면 된다. 이 과정을 그 다음 둘째, 셋째로 큰 수에 대해서 계속 적용하면 된다.

그렇게 명백한 해법의 계산 횟수는 최대 2*n-3으로 알려져 있다. 하지만 이것은 그렇게 뒤집은 여파가 다음으로 큰 수들을 정렬하는 데 끼치는 영향이 감안되어 있지 않다. 물론 여기서 좀더 머리를 써 봤자 2n이던 계수가 1.xx 정도로나 바뀌지 그게 n 내지 심지어 log n급으로 확 바뀌지는 못한다. 비록 O(n) 표기상으로는 동일하지만 그렇게 상수 계수를 조금이라도 줄이는 최적화이다 보니, 알고리즘이 더 까다롭고 머리가 아프다.

마이크로소프트의 창립자인 그 빌 게이츠가 1979년에 바로 이 문제의 계산 횟수를 최적화하는 알고리즘을 (공동) 연구하여 이산수학 학술지에다 투고했었다. 이 사람의 기록은 그로부터 거의 30년이 지난 2008년에야 더 정교한 알고리즘이 나옴으로써 깨졌다. 이것은 빌이 단순히 비즈니스맨이기만 한 게 아니라 엔지니어 기질도 얼마나 뛰어났고 수학 쪽으로도 얼마나 천재였는지를 짐작케 하는 대목이다. 학부 중퇴 학력만으로도 이미 전산학 석· 박사급의 걸출한 리서치를 했으니 말이다.

(3) 행렬의 곱셈
갑자기 팬케이크 정렬 얘기가 좀 길어졌는데 다음 항목으로 넘어가자면.. 계산 관련 알고리즘도 이런 급에 속한다. 대표적으로 행렬.

일반적으로야 두 개의 n*n 정방행렬끼리 곱셈을 하는 데 필요한 계산량, 정확히 말해 두 수 사이의 곱셈 횟수는 정확하게 O(n^3)에 비례해서 증가한다. 그러나 거대한 행렬을 2*2 형태의 네 개로 쪼개고, 덧셈을 늘리는 대신 곱셈을 줄이는 방식으로 최적화를 하는 게 가능하다. 게다가 쪼개진 행렬이 여전히 크다면 그걸 또 재귀적으로 쪼갤 수 있다.
a+bi와 c+di라는 복소수의 곱셈을 위해서 통상적으로는 ab, ac, bc, bd라고 곱셈이 총 4회 필요하다고 여겨지지만 실은 덧셈을 더 하는 대신에 곱셈은 ac, bd와 (a+b)*(c+d)로 3회로 줄일 수 있지 않은가? 그런 식으로 줄인 것이다.

그렇게 해서 O(n^3)보다 이론상 작은 시간 복잡도가 최초로 제안된 게 1969년에 나온 슈트라센 알고리즘이다. 대략 O(n^2.8). 정확하게 2.8인 건 아니고 지수 자체가 로그 n 이런 형태로 떨어진다. 프랙탈의 차원 수가 로그로 표현되는 것처럼 말이다.
여기서 2.8x의 정확한 의미는 log[2] 7이다. 원래 2*2 행렬 두 개를 곱하기 위해서는 상수 곱셈이 8회 필요한데, 중간 과정의 공식들을 궁극의 캐사기 테크닉을 동원하여 변형했다. 어마어마한 양의 우회 연산을 통해 덧셈은 횟수가 왕창 늘었지만 곱셈이 8회에서 7회로 딱 1회 줄었다! (도대체 무슨 약 빨고 연구해서 이런 걸 생각해 냈을까? ㄷㄷ) 이 여파가 분할 정복법의 특성상 재귀· 연쇄적으로 적용된 덕분에 전체 시간 복잡도가 감소한 것이다.

그리고 이 바닥도 발전에 발전을 거듭한 덕분에 오늘날은 무려 O(n^2.4)대까지 곤두박질쳤다. 덧셈과는 달리 곱셈은 이런 최적화의 여지가 존재한다는 사실 자체가 아주 신기하지 않은가? 크기가 서로 다른 행렬들의 최소 곱셈 횟수를 구하는 다이나믹 프로그래밍 문제하고는 완전 별개의 영역이다.

아래의 그림을 보자(움짤임). RGB라는 세 대의 차량이 서로 부딪치지 않고 G는 그대로 위로, R과 B는 서로 좌우가 엇갈리게 빠져나가려면 어떻게 하면 좋을까? 아래의 중앙은 길이 막혔기 때문에 횡단을 할 수 없다.
결국 가운데 G는 곧이곧대로 위로 나가서는 안 되며, R과 B의 경로를 피해서 몇 배나 더 긴 우회를 해야 한다. 하지만 그래도 RGB 모두 신호 대기가 없이 서로 엇갈리는 방향으로 술술 소통이 가능하다.

자연에는 관성이라는 게 존재하니, 다리가 아니라 바퀴가 달린 자동차나 열차에게는 우회를 하더라도 이게 훨씬 더 나은 방법인 것이다.
행렬도 덧셈이라는 우회가 아무리 몇 배로 더 늘어 봤자, 아주 큰 행렬(차량 소통이 엄청 많을 때)에 대해서는 곱셈이 눈꼽만치라도 줄어드는 게 도로로 치면 신호 대기가 없어지는 것에 맞먹는 이익이 될 수 있다는 생각이 든다.

물론 행렬의 곱셈 시간 복잡도가 O(n^2)보다 더 낮아질 리는 없으며, 저런 알고리즘들은 지수를 줄이는 대신 공간 복잡도(스택 사용..) 같은 다른 오버헤드가 왕창 커졌다는 점을 감안해야 한다. 크기가 몇십~몇백 정도 되는 초대형 행렬에서 두각을 발휘하지, 그냥 3차원 그래픽용으로나 간단히 쓰이는 3*3이나 끽해야 4*4 행렬에서 적용할 만하지는 않다.

Posted by 사무엘

PL(프로그래밍 언어)계에서 함수형 프로그래밍 언어는
자동차 엔진으로 치면 로터리 엔진, 발전소 업계로 치면 핵융합 발전 같은 뭔가 이상은 높지만 현실은 아직 좀 시궁창인 그런 떡밥스러운 영역으로 간주되는 것 같다.

전산학을 전공해서 PL 수업을 들은 분이라면 이미 잘 아시겠지만, 프로그래밍 언어란 크게 절차형과 선언형으로 나눌 수 있다.
절차형은 튜링 기계라는 컴퓨터의 특성을 그대로 반영하여 메모리로부터 값을 읽은 뒤 연산을 수행해서 값을 변경하고, 메모리 위치도 바꾸는 절차를 순차적으로 일일이.. 즉 HOW 위주로 기술하는 언어이다. 정보 올림피아드 경시부가 다루는 것은 응당 절차형 프로그래밍 언어를 활용하여 프로그램을 작성해서 문제를 해결하는 능력이다.

(덧붙이자면 튜링 기계에다가 데이터뿐만 아니라 코드, 즉 상태 변환 로직까지 동일한 메모리에다 올려서 해석하는 계산 모델이 바로 오늘날 컴퓨터의 근간이 된 프로그램 내장형, 즉 폰 노이만 모델이다. 자동차 엔진로 치면 정말 외연 기관에서 흡입-압축-폭발-배기 4행정 내연 기관으로 변모한 수준의 발전이 아닌가 싶다.)

한편, 선언형은 우리가 원하는 솔루션의 정의 내지 조건이 이러하다.. 라고만 써 주는 형태의 WHAT 지향형 언어이다. 그러면 컴퓨터가 알아서 문제를 풀어 낸다.
따지고 보면 데이터베이스 질의어인 SQL은 DLL, EXE 같은 실행 파일을 만드는 용도의 언어가 아닐 뿐이지 아주 대표적인 선언형 언어이다. 복잡한 DB에서는 질의어를 만드는 것도 굉장히 복잡한 일이 되며, 두 DB간의 JOIN은 어떻게 시키고 어느 구문부터 풀이해서 최적의 성능으로 질의를 수행할지 결정하는 것도 아주 어려운 축에 든다. 이런 거 성능 소요 시간을 몇 % 단축시키는 알고리즘을 개발해 내면, DB를 연구하는 전산학과 대학원 연구실에서는 그게 곧바로 논문감이 된다.

흔히 인공지능 문제 풀이형 언어로 알려져 있는 프롤로그도 선언형 언어이다. 이건 진짜 여러 변수들을 선언한 뒤 변수들간의 인과관계를 쭈욱 나열해 주면 이를 바탕으로 언어 런타임이 문제의 답을 찾아 낸다.

까놓고 말해 절차형 프로그래밍 언어로 "아인슈타인의 퍼즐" 같은 걸 풀려면, 프로그래머가 재귀호출에 각종 백트래킹 알고리즘을 직접 구사해야 하니 앞에서 말했던 정보 올림피아드 경시부 급의 기술이 필요하다. 그러나 프롤로그에서는 "영국인.집 = 빨강, 스웨덴.애완동물 = 개" 이런 식으로 단서만 주어진 규칙대로 쓴 뒤 쿼리를 날리면 금붕어를 기르는 사람의 국적을 구할 수 있다.

아마 네모네모 로직이나 스도쿠 같은 것도 해답이 갖춰야 할 조건을 명시하는 것만으로 바로 풀 수 있지 싶다. 단서들을 바탕으로 뺑뺑이를 돌리는 추론 과정은 언어 런타임 내지 엔진이 해 준다.
대학 학부 시절, OR개론 수업 때 잠시 접했던 선형계획법 문제 풀이 프로그램인 k-opt도 역시 지정된 문법에 따라 변수와 부등식들을 써 놓고 최소화/최대화 조건을 명시하면 프로그램이 해를 찾아 주니.. 일종의 선언형 프로그래밍 언어 런타임에 속한다고 할 수 있겠다.

그러니, 절차형 언어의 컴파일러는 최적화를 하는 게 기계어 코드 생성이나 멀티코어 병렬화 같은 아주 미시적인 것과 관계가 있는 반면, 선언형 언어의 수행 방식을 최적화하는 것은.. 거시적인 알고리즘 전략까지 결정해야 하니 더욱 까다로울 것이다. 미시적인 건 해당 언어 엔진이 아주 정교하게 구현되어 있지 않은 이상 신경 쓰기 힘들다.

앞서 언급한 SQL이나 프롤로그는 선언형 프로그래밍 언어 중에서 일종의 '논리 지향'인 물건들이다. 그런데 선언형의 하위 범주로는 '함수 지향', 함수형 프로그래밍 언어라는 게 있다. 이게 절차형보다는 좀 더 수학자스러운 형태로 컴퓨터를 부려먹는 방법을 기술하는 방법론이라고 한다. (함수형이 여느 절차형 프로그래밍과 계산 능력이 동등하다는 것은 튜링 기계와 람다 대수가 동치라는 것이 증명됨으로써 알려져 있다.)

순수한 함수형 프로그래밍 언어에서는 지저분한 대입 연산이 없고 한번 생성된 값은 변경 없이 계속 그 값으로 남아 있다. 새로운 값이 계속 생성될 뿐이다. 사실 문자열을 이런 사고방식으로 처리하는 라이브러리나 언어, 프레임워크에서는 이미 있는 문자열을 변경하는 게 굉장히 어렵기도 하다. Windows RT의 String 클래스도 그랬던 걸로 기억..

함수형 언어에서는 대입이 없으니 응당 뺑뺑이 loop도 있을 수 없다. loop을 대신하는 것은 재귀호출이다! loop조차도 기존 값을 계속 바꾸는 게 아니라 새로운 값을 자꾸 만들어 내는 방식으로 구현된다는 뜻이다.
처음에 해답의 범위가 0부터 100 사이에 있었다면 그 다음 턴에는 0부터 50 (log n 시간 복잡도), 혹은 0부터 99로 자가호출이 이뤄지고, 이것이 문제가 완전히 해결될 때까지 반복된다. 왜냐하면 이 문제의 솔루션이 바로 그런 형태로 귀납적으로 정의돼 있기 때문이다. 팩토리얼이든, 두 수의 최대공약수이든, 정렬이든 다른 무엇이든.

이 패러다임에서는 함수가 다른 여느 데이터와 완전히 동일한 수준으로 다른 함수의 인자가 될 수 있고, 특히 이름 없이 함수의 몸체만을 여느 값처럼 달랑 전해 줄 수 있고, 다른 함수로부터 합성되고 유도된 새로운 함수가 함수의 리턴값이 될 수 있다. 새로운 함수가 동작하는 데 필요한 주변 문맥은 클로저라는 물건이 알아서 다 처리해 준다.
C/C++의 함수 포인터에 머리가 굳은 프로그래머라면 calling convension은 무엇인지, this 포인터가 포함된 멤버 함수인지, pointer-to-member라면 다중 상속으로 인한 부가 오버헤드는 없는지 같은 디테일 때문에 머리가 복잡해질 것이다.

함수형 언어에서 if문은 응당 자기 자신도 조건이 만족하는 쪽의 값을 되돌리는 함수 형태이다.
그러나 if는 조건이 만족하는 쪽만 '계산'이 행해질 터이니 if(a) b; else c; 를 나타내는 if(a, b, c)는 통상적인 함수 호출 func(a, b, c)와 의미상으로 완전히 동일할 수는 없다. 예약어로 따로 해석되고 취급을 받아야 할 듯하다.

물론 이런 함수형 프로그래밍 언어가 구현되기 위해서는 현실에서 컴파일러가 최적화해 줘야 하는 것, 그리고 언어 런타임이 해 줘야 하는 오버헤드가 적지 않다. 끝없이 새로운 값을 생성해 내더라도 이제 참조가 끝나서 더 쓰이지 않는 값은 GC가 알아서 제거해 줘야 하고, 재귀호출, 특히 tail recursion 정도는 알아서 메모리 복잡도를 O(n) 급으로 늘리지 않는 일반적인 loop처럼 돌아가게 컴파일러나 런타임이 최적화를 해 줘야 한다. 함수를 값처럼 부드럽게 다루는 것도 기술적으로는 단순 함수 포인터 이상의 추상화 계층이 필요하며, 말처럼 쉬운 일이 아니다.

예를 들어.. X라는 함수가 있는데.. 얘는 a라는 인자를 받고는,
b라는 인자를 받아서 a에다가 b를 더한 값을 되돌리는 Y라는 함수를 되돌린다고 치자.
결국 Y는 X라는 함수가 호출될 때 전달되었던 매개변수 내지 그때 생성된 X 내부의 지역 변수에 의존하여 동작하는데..
나중에 Y가 단독으로 호출될 때는 X라는 함수는 실행이 끝나고 그 문맥이 존재하지 않는다. 이를 어찌하리?
이런 딜레마를 피하기 위해 C/C++ 언어는 애초에 함수 안에 함수를 만드는 걸 지원하지 않는 쪽으로 설계되었으며, C++의 functor 같은 것도 전부 자기가 자체적으로 데이터 멤버를 갖고 있는 객체 형태로 만들어지게 된 것이다.

또한, 아무리 대입이 사이드 이펙트가 남는 지저분하고 기피되어야 하는 연산이고.. 다른 모든 연산을 loop 대신 재귀호출로 때운다 해도.. 당장 외부 파일/키보드로부터의 input은.. 대입 연산 없이는 감당이 도저히 불가능하다. 그리고
return t1.len() > t2.len() ? t1: t2
처럼 그 재귀호출의 결과값을 취사 선택하는 간단한 판단을 위해서라도 임시 변수에 대입하는 것 정도는 근본적으로 전혀 없을 수가 없다.
어디 그 뿐이랴. 대용량의 단일 데이터를 대상으로 여러 함수들이 포인터만 주고받으며 동작하다 보면, 한 함수가 자기 argument 안에 입출력 대상인 모든 데이터를 집어넣는 것은 무리가 있다.

허나 함수형 프로그래밍이 성능면에서 불리한 요소만 있는 건 아니다. 대입으로 인한 side effect 같은 게 없으니 소스 코드의 정적 분석은 더 용이할 것이고 병렬화 등 입맛에 맞는 최적화에도 더 유리할 것이다. 애초에 선언형 프로그래밍 언어는 구체적인 실행 방식은 그런 똑똑한 컴파일러나 언어 엔진에게 맡기고 있으니까.
이러니 PL 분야를 연구하는 전산학자나 수학 덕후들이 함수형 프로그래밍 언어에 더욱 열광하는 듯하다. 저런 패러다임이 응집도· 결합도 같은 소프트웨어 공학적인 측면에서 더 깔끔한 코드를 만드는 데 도움이 되는 것은 덤이다.

대학교 전산학과에서는 함수형 프로그래밍 언어로 보통 Scheme을 실습하는 편이다. 본인도 먼 옛날 학부 시절에 '프로그래밍의 이해(PP)'라는 과목을 통해 그 물건을 접했으며, 그걸로 무슨 다항식의 곱셈을 하는 프로그램도 숙제로 만들고 여러 덕질을 했었다. 함수형 언어의 진짜 본좌라고 일컬어지는 Haskell 같은 건 난 모름.;;

여담이지만 지금 생각해 보니, 온갖 복잡한 괄호가 배배 꼬여 있는 Scheme 코드는.. 언어학에서 문장 구문 분석을 괄호로 표현해 놓은 것과 사뭇 닮았다는 생각이 들었다. (S (NP .. ) (VP ...)) 이러는 식.
Schme에서는 S 대신에 define, lambda, if 따위가 있을 것이다.

물론 그때는 본인은 <날개셋> 한글 입력기 개발에 도움이 안 되는 건 진짜 생까고 무시하던 시절이어서 그 코스의 의미를 제대로 이해를 못 했다. 왜 괜히 계산 과정을 이 따위로 어색하게 표기를 하는지..??
그건 사칙연산 같은 기초적인 연산자조차도 통상적인 표기법이나 우선순위를 깡그리 무시하고 정말로 오로지 함수 위주로.. 프로그래밍이, 아니 계산(computing)이라는 작업 자체를 몽땅 주어진 규칙대로 피연산자들을 처리해서 reduce하는 과정이라고 극도로 추상화한 귀결일 것이다. 일종의 발상의 전환인 것이다. car, cdr 명령이 튜링 기계로 치면 메모리 셀을 이동하고 값을 읽는 동작에 해당할 것이다.

단, Scheme도 마냥 순수 함수형 언어이기만 한 것은 아니다. 필요한 경우 대입 연산이 있을 수 있고 일부 절차형 패러다임 구문을 집어넣을 수도 있다. 마치 C#에서 부분적으로 unsafe, unmanaged 코드를 집어넣듯이 말이다.
그리고 반대로 C++ 역시, 기본적으로 객체지향 패러다임을 주류로 내세운 절차형 언어이지만 최근에는 함수형 프로그래밍 패러다임도 받아들여서 람다 함수를 기존 함수 포인터나 functor의 대용으로 쓸 수 있게 되었듯이.. 요즘 언어들의 대세는 자기 정체성은 유지하면서 다른 패러다임에서도 유용한 건 적극 받아들이는 것인 듯하다.

과연 함수형 프로그래밍 언어가 그저 대학교 과목에서나 잠깐 접하고 마는 떡밥 내지 PL 분야의 연구자들만 쓰는 도구 수준을 넘어.. 현업에서 적극 즐겨 쓰이는 날이 올지 모르겠다. 지금 현업에서 전혀 안 쓰인다는 말은 아니지만 아직까지는 수학 덕후, 컴덕후들의 전유물이라는 인상이 강한 편이니 말이다. 그래도 한 가지 확실한 건, 함수형 프로그래밍 패러다임을 실현해도 될 정도로 요즘 컴터 환경이 좋아지자, 각종 언어들에도 이 패러다임이 적극 많이 도입되고 이게 유행을 타고 있다는 사실이다.

여담으로, 람다 대수를 고안한 앨론조 처치는 family name이 어째 '교회'다..;; 독실한 신자 가문이기라도 했나 싶은 잡생각이 든다.

그리고 궁금한 게 있는데.. 이름 없는 함수에서 재귀호출을 해야 할 때 함수 자기 자신을 가리키는 this, self 같은 키워드는 없는가 싶다.
이 의문은 C++에서 람다 함수가 추가되었을 때부터 여러 프로그래머들에 의해 제기되어 왔다. 하지만 뾰족한 해결책은 없으며, std::function에다가 자신을 저장한 뒤, 그 변수명을 캡처로 도로 넘겨 줘야만 재귀호출이 가능하다. Scheme 역시 일단 def로 자기 이름을 지은 뒤, 그 이름을 호출해 줘야 된다.

재귀호출을 그렇게도 좋아하는 함수형 언어가

[](int x) { return x<=1 ? 1: this_func_itself(x)*(x-1); }

개념적으로 this_func_itself에 해당하는 키워드 같은 건 정말 없는 건지 신기한 노릇이 아닐 수 없다.

Posted by 사무엘

여러분은 다음과 같은 서로 완전히 다른 분야의 관행들에서 공통된 패턴이 존재한다고 생각하시는가? 만약 존재한다면 공통점이 무엇일까?

• 컴퓨터에서 각종 계정의 암호를 설정하는데, 암호는 무조건 n글자 이상에 대소문자와 숫자 등이 반드시 골고루 섞여야 한다고 프로그램이 사용자에게 강요를 한다.
• 출퇴근 시간엔 서울 지하철 사당 역은 2호선과 4호선 사이의 지름길 직통 환승 통로를 폐쇄하고 먼 우회 통로로만 환승이 가능하게 만든다. 또한 사람이 지나치게 많이 몰리는 행사가 열리면 가까운 지하철 역이 통째로 폐쇄되고 열차가 무정차 통과한다.
• (종교 얘기. 비기독교인은 skip해도 좋음) 예루살렘에서 성령이 강림한 후 신약 기독교회가 갓 태동했다. 그러나 하나님은 역설적으로 그 기독교 성지에서 맹렬한 기독교 박해와 스데반의 순교를 허락하셔서 신자들을 뿔뿔이 흩어 버렸다.

내가 생각하는 이것들의 공통점은... 한데 몰려서는 안 되는 곳에 사람들이 지나치게 많이 몰릴 때 “그 몰리는 선택지 자체를 없애 버려서 분산을 강제로 유도”했다는 점이다. 그리고 이로써 집단 내부의 잠재적 부작용이나 병폐를 해결했다.

먼저 종교의 경우다. 먼저 믿고 구원받은 크리스천은 주님의 명령대로 세상 방방곡곡에 흩어져서 복음을 전해야 하는데 그게 말처럼 쉽지 않다. 어지간하면 그냥 신자들끼리만 기득권을 형성하고 교제라는 명목의 친목질만 하면서 고향에서 편하게 살고 싶다. 그러니 하나님이 저런 역경을 허락하신 것이다. 물리적으로만 보자면 그건 자기 신자를 줄이고 세력을 약화시키는 팀킬인데 기독교는 오히려 그런 역경을 통해서 역설적으로 잡초처럼 더 강해지고 널리 퍼져 온 것이다.
(단, 그렇다고 해서 기독교 박해 행위 자체를 정당화할 생각은 하지 마시길.)

교회사뿐만 아니라 바벨 탑 사건도 비슷한 맥락으로 사람들을 강제로 뿔뿔이 흩어 버린 경우에 속한다. 온 인류가 단일 민족 단일 언어이면 지금처럼 복음 전할 때에도 “아프리카 원주민이나 세종대왕, 이 순신 같은 사람도 다 예수 전해듣지도 못했는데 지옥 갔냐?” 이런 쓸데없는 질문을 받을 일이 없었을 텐데.. 하나님이 왜 그런 비효율적인 자충수를 일부러 두신 걸까?

두 말할 나위도 없이 인류가 단일 언어 단일 체계이면.. 다같이 하나님을 믿는 것보다 다같이 순식간이 부패하고 타락하고 썩어 버리는 게 훨씬 더 빨리 진행되기 때문이다. 다 합당한 이유가 있다.
그 대신, 교회가 태동하던 무렵에는 복음이 빨리 퍼져 나가라고 바벨 탑 사건 때와는 정반대로 언어 장벽을 잠시 극복해 주신 것이다. 그게 바로 '방언 은사'이라는 거다. 성경의 방언은 알아들을 수 있는 외국어이지, 울랄날따따따 잡소리가 절대 아니다.

자 그건 그렇고, 교통 얘기로 오면..
사람이 한 장소에 너무 몰리면 꼼짝달싹 못 하고 아무도 이동을 못 하게 될 뿐만 아니라 압사 사고 등 안전상의 위험도 매우 커진다. 제일 가까운 지하철역을 폐쇄하는 것은 사람들을 더 먼 곳까지 강제로 이동시킴으로써 밀집도를 낮추는 효과를 내며, 우회 환승 통로 역시 환승 승객을 수용할 공간을 확보하여 밀도를 낮춰 준다.

새해에 타종 행사를 하고 나면 종각/시청 일대의 지하철역이 폐쇄되고 불꽃 축제가 있을 때는 여의도 근처의 지하철역이 폐쇄되는 이유가 이로써 설명된다. 지난 여름에 교황이 왔을 때에도 광화문, 시청 근처의 지하철역은 당연히 폐쇄크리를 먹었다. 정말 상상을 초월하는 수의 인파가 몰렸기 때문이다.

서로 가깝고 같은 기간에 동일한 십자형으로 건설된 천호 역은 환승 거리가 짧은 반면, 군자 역은 거리가 일부러 꽤 길게 만들어져 있다. 7호선이 8호선보다 더 수요가 많고 혼잡하기 때문일 것이다.
그런데 천호도 마냥 짧기만 한 건 아니다. 천호에서 8호선을 타는 승객의 압도 다수가 잠실 역에서 내리는데, 환승 지점은 열차의 뒷부분이고 잠실에서 빨리 갈아타려면 암사 방면 열차의 맨 앞까지 이동을 해야 한다. 이것 때문에 사람들이 많이 걷는다. 지하철 8호선이 만들어질 때 이런 것까지 다 지능적으로 고려를 했는지는 모르겠다.

자, 그 다음으로 암호 얘기를 하겠다.
모든 사람들이 정말 정보 엔트로피가 높은 완전 무작위한 숫자· 문자를 암호로 사용한다면..
저런 제약은 오히려 암호 공격자에게 좋은 단서로 작용할 수 있다. 비록 암호 조합 문자열이라는 파이 전체에서 차지하는 비중은 여전히 미미하겠지만, 어쨌든 n글자 이하는 절대로 거들떠보지 않아도 되고, 한 종류의 문자만으로 이뤄진 문자열은 처음부터 탐색 대상에서 제끼면 되니까 말이다.

그런데도 굳이 저런 제약이 존재하는 건.. 불행히도 매우 많은 사람들이 저 작은 표본을 벗어나지 않는 범위에서 암호를 허술하게 만들고, 그게 공격자에게 왕왕 털리기 때문이다.
password, qwerty, q1w2e3, asdf, letmein, love 등...;;
그러니 차라리 그 표본을 명시하고서 사용자들로 하여금 강제로 배제하게 하는 게...
공격자에게 새 발의 피 정도의 단서를 던져주고서 전체 보안은 넘사벽급으로 훨씬 더 강화하는 효과를 낸다. 내 발뒤꿈치를 주고 상대방의 머리를 공격하는 전략 되겠다.

암호라는 건 마치 캡챠만큼이나 서로 모순되는 두 이념을 적당히 잘 충족해야 한다.
캡챠가 사람은 쉽게 알아보고 컴퓨터는 못 알아보는 그림이라면, 암호는 공격자--공격자의 주 도구인 컴퓨터도 포함--는 유추하기 무진장 어려우면서 당사자는 기억하기 쉬워야 한다.
주인이 기억하기 쉬우려면 결국 주인은 자기 개성을 표현하는 문자열을 떠올리게 되는데, 이렇게 되면 암호 공격은 거의 사회과학의 영역으로까지 확장되게 된다.

(더 극단적으로는, 기계적으로 완전 철통같은 암호라 해도 암호를 아는 사람을 돈이나 미인계로 매수한다든지, 혹은 아예 물리적으로 잡아 족침으로써 어이없게 뚫어 버리는 예도 있다.;; brute force 테크닉 그딴 것도 필요 없다. 성경에도 삼손의 지인들이 삼손의 수수께끼를 어떻게 풀었던가? 삿 14 참고)

일반적으로 컴퓨터 소프트웨어의 암호 입력란은 IME가 동작하지 않아서 영문· 숫자 이외의 문자를 입력할 수 없다. 이건 여러 모로 바람직한 조치라 여겨진다.
암호는 무슨 문자를 입력하느냐보다는 결국 무슨 keystroke를 입력했느냐가 더 중요하며, 지금 입력하는 글자가 일반적으로 화면에 보이지 않기 때문에 복잡하게 입력 모드 같은 걸 따질 처지가 못 된다.
또한 암호 입력란에서 IME 같은 별도의 소프트웨어 계층이 동작할 경우, 암호 문자열을 악성 프로그램이 가로채는 보안 문제가 커질 수도 있다.

하지만 이런 점에도 불구하고, 운영체제의 자체 GUI를 쓰지 않는 프로그램 중에는 IME가 동작하는 암호 입력란을 가진 경우도 있다. 굳이 한글로 입력을 안 하고 영문 자판에서 한글 입력을 하면.. 무질서도가 상당히 높은 알파벳 문자열이 생성되기 때문에 외국인 공격자가 알아내는 데는 애로사항이 꽃핀다. 이 사용자가 한국인이라는 단서가 없다면 말이다.
특히 세벌식은 사용자가 매우 적은 데다가 자체적으로 4단의 숫자· 기호까지 일부 활용하기 때문에 이런 보안 면에서 아주 좋다. Mac OS가 악성 코드가 별로 안 들끓는 이유도 딴 거 없고 사용자가 심히 적어서 해커들에게 별로 돈이 안 되기 때문이다. 간단하다.

아무도 모르고 내가 기억하기 쉬운 문자열이라는 특성상, 국가를 막론하고 욕설을 암호로 사용하는 사람도 있다. 뭐, 나쁠 것 전혀 없는 발상이긴 하지만 너무 대중적인(?) 욕설은 공격자들도 이미 다 파악하고 있으니 이 역시 조심해야 한다.

암호는 닥치고 20글자 이상으로 엄청 길면.. 무질서도가 기하급수적으로 치솟는다. 어지간히 단순무식한 형태의 암호라고 해도 엄청나게 긴 것에는 답이 없다. 글자수가 몇 자 늘어날 때마다 0.n초이던 예상 공격 시간이 그야말로 수천, 수만 년 이상으로 뻥튀기된다. 그러니 암호라는 건 pass-word가 아니라 최하 phrase나 sentence 정도의 규모로 만드는 게 좋다.

Microsoft Iphone 내지 언어학의 Colorless green ideas sleep furiously처럼 서로 개연성이 없는 생뚱맞은 단어들(저 문장 자체는 절대 쓰지 말 것! ㅋㅋ), 내가 좋아하는 무리수나 엄청 방대한 소수의 x~y째 자리수의 base64 인코딩 등을 섞으면 공격자가 뚫기 대단히 어려운 암호를 만들어 낼 수 있다. 그리고 까먹었더라도 그 암호를 생성하는 공식을 기억하고 있으니 나중에라도 컴퓨터를 돌려 언제든지 다시 만들 수 있다.

그리고 굳이 저런 식으로 머리를 안 굴리더라도, 본인 같은 사람은 직업 특성상 맨날 숫자와 특수문자와 알파벳이 뒤죽박죽 섞인 문자열을 취급하는 게 일이니... 저런 조건을 모두 만족하는 진짜 암호스러운(cryptic) 암호(password)를 의외로 금방 떠올릴 수 있었다.
요즘은 암호 관리자 전용 앱도 많이 나와 있는데, 이런 식으로 암호 생성기가 같이 연계되고 각 포털 사이트별로 암호 변경 주기를 관리도 해 주는 똑똑한 앱이 있으려나 궁금하다.

터치스크린 입력 방식이 시각 장애인에게 악재인 것만큼이나(점자!)..
PC와는 구조적으로 다른 스마트폰의 문자 입력 방식은 무질서도가 높은 암호를 입력하는 데 악재인 것 같다.
작은 화면에서 알파벳, 숫자, 특수문자를 섞어서 수월하게 입력하는 게 압도적으로 불편하고 까다롭기 때문이다.
물론 그 때문에 거기에는 패턴 제스처 같은 다른 암호 입력 방법도 등장했겠지만, 아무래도 문자 입력만치 보안이 강력하지는 못하다.

끝으로 글을 맺으며 든 생각이 있다.
우리말은 엄연히 다른 개념인 password와 encrypt/cryptic이라는 두 의미가 '암호(화)'에 모두 담겨 있다.
이건 어찌 보면 '다른'에 different와 another가 모두 포함돼 있고, 조사 '과/와'에 and뿐만 아니라 with가 섞여 있으며
단순히 시계의 표시 시각이 이르거나 늦은 것까지 다 '빠르다/느리다'로 표현하는 것만큼이나..
일면 좀 부정확하고 어정쩡하게 들린다.

하지만 한국어만 저렇게 한데 싸잡아 표현하는 건 아닌 듯하다.
또한 '암호'는 정보에 대한 접근 가능 여부 자체를 binary로 통제하는 것이고 '암호화'는 정보에 접근했더라도 해독을 못 하게 하는 것인데.
암호화를 해독하기 위한 암호가 있기도 하니, 목표면에서는 굳이 서로 떼어서 생각할 필요가 없는 비슷한 개념인지도 모르니까 말이다.

Posted by 사무엘