« Previous : 1 : 2 : 3 : 4 : Next »

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

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 사무엘

2016/01/12 08:30 2016/01/12 08:30
, , ,
Response
No Trackback , 9 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1181

※ 메모리 단편화

컴퓨터에서 무작위 읽기/쓰기가 가능한 모든 기억장치.. 즉 RAM, 파일 시스템, 데이터베이스 따위에는 모두 구조적으로 단편화라는 문제가 존재한다.
메모리를 10바이트씩 찔끔찔끔 요청했는데 최소 할당 단위 제약 때문에 실제로는 수백 바이트 단위로 성큼성큼 용량이 짤려 나간다거나(내부 단편화),
전체 남은 용량은 1000바이트인데 한 600바이트 정도 연속된 구간이 없어서 메모리 할당이 실패하는 외부 단편화가 모두 존재한다.

메모리라는 게 1차원적인 공간이기 때문에 이건 뭐 어쩔 수 없다.
그래서 컨텐츠가 실제로 차지하는 용량보다 전체 소모 용량이 더 커지게 되고, 이런 걸 관리하는 프로그램이나 유틸리티에는 조각 모음(defrag), shrink, compact 같은 동작을 강제로 수행하는 기능이 있다. (뭐, 디스크 중에서 SSD는 예외적으로 조각 모음이 필요하지 않은 구조라고는 하지만.)

디스크는 애초부터 파일 시스템의 지배 하에 있으며 그 시스템이 제공하는 방식대로 디렉터리와 파일 이름을 통해서만 내용에 접근 가능하다. 일반적인 응용 프로그램이 디스크를 무슨 실린더 번호 x, 트랙 y, 섹터 z 같은 형태로 무식하게 접근하는 경우는 거의 없다. 그런 방식은 오늘날의 운영체제에서는 더욱 금기시되고 있다.

그렇게 파일명이라는 고수준 추상 계층이 있는 덕분에 디스크는 내부적으로 막 조각 모음을 해도 딱히 파일을 못 찾는 일이 발생하지는 않는다. 저수준 처리는 운영체제의 파일 시스템이 알아서 다 처리해 준다. 또한 디스크 정도면 물리적으로 액세스를 하는 데서 발생하는 병목이 소프트웨어적인 추상화 계층을 거치는 시간보다 훨씬 더 길기도 하고 말이다. 사용자에게는 외부 단편화보다는 클러스터 최소 단위로 인한 내부 단편화가 현실적으로 더 와 닿는다.

그런데 RAM은 디스크와는 사정이 다르다. 단편화를 예방한답시고 함부로 컨텐츠들을 재배치하면 memcpy 오버헤드는 둘째치고라도 그 메모리 주소를 직접 가리키고 있던 수많은 포인터들이 작살이 나 버린다.
메모리 자원이 극도로 가난하고 열악하던 16비트 Windows 시절에는 운영체제의 global/local heap으로부터 메모리를 할당받고 나면 곧바로 포인터가 돌아오는 게 아니라 핸들 하나만이 돌아왔다. 이 핸들이 가리키는 메모리는 운영체제의 사정에 따라 수시로 재배치될 수 있는데, 메모리를 실제로 사용할 때만 lock을 걸어서 위치를 고정시킨 뒤, 포인터를 얻어와서 메모리를 참조하곤 했다. 사용이 끝나면 다시 unlock을 해 줘야 한다.

이것이 바로 GlobalAlloc - GlobalLock - GlobalUnlock - GlobalFree 사이클이다. 재배치를 하는 이유는 당연히 메모리 단편화를 극복하고, 연속된 긴 메모리 공간을 언제나 확보하기 위해서이다. 16비트 시절에 메모리 블록이나 리소스 같은 데에 discardable, resident, non-resident 같은 속성이 달려 있던 이유는, 수시로 재배치 내지 재로딩 같은 빡센 메모리 관리에 대응하기 위해서이다.
운영체제가 자동으로 무슨 garbage collect를 해 주는 것도 아니고, 저런 일을 해야만 했다는 게 참 안습하다.

여기서 우리가 알 수 있는 점은, 32비트 정도 되는 주소 공간에서 가상 메모리가 제공되는 게 프로그래머의 관점에서 얼마나 축복이냐 하는 것이다. 4기가바이트 정도 넉넉한 공간이 있으면, 단편화 문제는 주소빨로 어느 정도, 상당 부분 극복이 가능해진다. 어지간히 단편화가 심한 상태라 해도, 또 대용량 메모리 요청이 들어오면 걍 다음 주소를 끌어다가 물리 메모리에다 대응시켜 쓰면 되기 때문이다.

그 연속된 가상 메모리 주소를 실제로는 여기저기 흩어졌을 가능성이 높은 지저분한 물리 메모리로 대응시키는 건 운영체제와 CPU의 몫이다. 물리 메모리가 부족하면 하드디스크 스와핑까지 알아서 해 준다. 가상 메모리 덕분에 프로세스간에 보안이 더 향상된 것도 덤이고 말이다.

이것이 RAM과 디스크의 차이이다. 디스크에 파일명이 있다면 RAM에는 가상 메모리 메커니즘이 있다. 한 주소 공간 안에서 스레드가 여러 개 있는 경우 가상 메모리의 필요성은 더욱 커진다.
물론, 세상에 공짜는 없으니, 가상 메모리는 메모리를 관리하기 위한 추가적인 메모리도 적지 않게 소요하는 테크닉인 걸 알아야 한다. 물리적인 메모리뿐만이 아니라 가상 메모리 주소 영역 자체도 떼먹는다.
오늘날 64비트 운영체제라 해도 어마어마하게 방대한 공간인 64비트 전체를 사용하는 게 아니라 40비트대 정도만 사용하는 것도 이런 이유 때문이다.

※ 옛날 이야기

옛날의 프로그래밍 언어나 소프트웨어 플랫폼을 살펴보면, 메모리와 관련하여 오늘날 당연한 기본 필수라고 여겨지는 요소가 대놓고 빠진 것들이 적지 않아 놀라게 된다.

(1) 예를 들어 옛날에 포트란 언어는 함수 호출은 가능하지만 초기에는 동일 함수에 대한 중첩/재귀 호출이 가능하지 않았다. 세상에 뭐 이런 언어가 다 있나 싶다..;; 함수 안에서 지역 변수의 사용이 스택 기반으로 되어 있지 않고 늘 고정된 주소로만 접근하게 돼 있어서 그랬던 모양이다.

오늘날의 프로그래밍 언어에서야 지역 변수는 스택의 기준 주소로부터 상대적인 위치를 건드리게.. 일종의 position independent code 형태로 접근된다. 재귀 호출 지원뿐만 아니라 코드 실행 주체가 증가하는 멀티스레드 환경에서는 각 스레드가 또 독립된 스택을 갖고 있으니 절대 고정 주소가 더욱 의미를 상실하기 때문이다. 멀티스레드는 thread-local이라는 일종의 새로운 scope까지 만들었다.

(2) 한편, 프로그래밍 언어 쪽은 아니지만, Win32의 구현체 중에 제일 허접하고 불안정하고 열악하던 Win32s는..
멀티스레드도 없고 각 프로세스마다 독립된 주소 공간이 없는 건 그렇다 치는데... DLL은 자신이 붙는 각 프로세스별로 자기만의 독립된 데이터 공간마저도 보장받지 못했다. 16비트 DLL과 다를 바가 없다는 뜻.

옛날에 아래아한글 3.0b는 윈도 95나 NT 말고 3.1 + Win32s에서 돌아갈 때는 무슨 자기네 고유한 메모리 서버 프로그램을 먼저 실행한 뒤에야 실행 가능했다. 이제 와서 다시 생각해 보니, 그 메모리 서버가 하는 일이 바로 DLL별로 고유한 기억장소를 할당하는 것과 관련이 있지 않았나 싶다. 아래아한글의 소스를 모르는 상태에서 그냥 개인적으로 하는 추측이다.

아시다시피 16비트 Windows는 가상 메모리 같은 게 없다 보니, 콜백 함수의 실행 context를 레지스터에다 써 주는 것조차 소프트웨어가 수동으로 해야 할 정도로 진짜 가관이 따로 없었다.

※ 쓰레기(다 쓴 메모리) 수집

끝으로 garbage collector 얘기다.
heap으로부터 할당하는 메모리는 너무 dynamic한지라 언제 얼마만치 할당해서 언제 해제되는지에 대한 기약이 없다. 그걸 소스 코드만 들여다보고서 정적 분석으로 완벽하게 예측하는 건 원천적으로 불가능하다.

하지만 정해진 scope이 없는 동적 메모리를 잘못 건드려서 발생하는 소프트웨어 버그는 마치 자동차의 교통사고처럼 업계에서 상당히 심각한 문제이다.
memory leak은 당장 뻑이 나지는 않지만 프레임 단위 리얼타임으로, 혹은 수 개월~수 년간 지속적으로 돌아가는 소프트웨어에서는 치명적이다. 또한 다른 메모리/포인터 버그도 단순히 혼자만 뻑나는 걸로 끝나면 차라리 다행이지, 아예 악성 코드를 실행시키는 보안 문제로까지 상황을 악화시킬 수 있다.

이 동적 메모리 관리를 사람에게 수동으로 맡겨서는 안전하지 못하니, 메모리 자원 회수를 프로그래밍 언어 런타임 차원에서 자동으로 보장되게 하는 기법이 연구되어 왔다.
고전적인 reference counting 테크닉은 C++의 생성자/소멸자 패러다임과 맞물려서 일찍부터 연구되어 왔으며 smart pointer 같은 구현체도 있다.

이건 원리가 아주 간단하며, 언어 차원에서 포인터의 scope가 벗어나는 족족 메모리가 칼같이 회수되는 게 컴파일 시점에서 보장된다. 그래서 깔끔한 것 하나는 좋다.
허나 이 기법은 생각보다 비효율과 단점도 많다. 대표적인 논리적 결함인 순환 참조는.. 서로 다른 두 객체가 상대방을 서로 참조하여 똑같이 참조 횟수가 1보다 커지고, 따라서 둘이 메모리가 결코 해제되지 않아서 leak으로 남는 문제이다.

즉, 레퍼런스 카운팅이 잘 동작하려면, 참조를 받은 피참조자는 자신을 참조하는 놈을 역참조하지 말아야 한다. 이걸 어기면 객체간의 레퍼런스 카운트가 꼬여 버린다.
문제는 이걸 일일이 조심하면서 코드를 작성하는 게 상황에 따라서는 차라리 걍 메모리 자체를 수동으로 관리하는 게 나을 정도로 효율이 떨어질 수 있다는 것이다. 게다가 고리가 어디 A-B, B-A 사이에만 생기겠는가? A-B, B-C, C-A 같은 식으로 더 골치 아프게 생길 수도 있다. 참조 관계는 정말로 cycle이 없이 tree 형태로만 가야 한다.

그러니 이 문제는 예상 외로 굉장히 심각한 문제이다. 멀티스레드에서의 '데드락'하고 다를 바가 없다! 서로 뭔가 꼬여서 끝이 안 난다는 점, 잡아 내기가 극도로 어렵다는 점이 공통점이다.
성능을 더 희생하고라도 메모리 leak 문제를 완전히 다른 방식으로 접근한 전용 garbage collector가 괜히 등장한 게 아니었겠다 싶다.

가비지 컬렉터라고 해서 무슨 용 빼는 재주가 있는 건 아니다. 기본적으로는 당장 접근 가능한 메모리로부터 출발해서 그 메모리로부터 추가로 접근 가능한 메모리 블록을 줄줄이 순회하여 표시를 한 뒤, 표시가 없는 메모리를 죄다 해제한다는 아이디어를 기반으로 동작한다. 동적으로 할당받은 메모리 내부에 또 동적 할당 메모리의 포인터가 있고, 그게 또 이상하게 얽히고 배배 꼬인 걸 어떻게 일일이 다 추적하는지 더 구체적인 방법은 잘 모르겠지만.

어찌 보면 단순무식하다. 주인 없이 주차장에 장기간 방치되어 있는 폐자전거들을 일괄 처분하기 위해 모든 자전거에 리본을 달아 놓은 뒤, 일정 날짜가 지나도록 리본이 제거되지 않은 자전거를 갖다 버리는 것과 개념적으로 비슷하다! 혹은 기숙사의 공용 냉장고에서 주인에게로 접근(?)이 안 되는 장기 방치 식품을 주기적으로 제거하는 것과도 비슷한 맥락이다. 단지 좀 더 성능을 올리기 위해, 메모리 블록들을 생존 주기별로 분류를 해서 짬이 덜 찬 메모리가 금방 또 해제될 가능성이 높으므로 거기부터 살펴보는 식의 관리만 하는 정도이다. 자바, .NET의 가상 머신들도 이런 정책을 사용한다.

이건 즉각 즉각 자원이 회수되는 게 아니며, 리얼타임 시스템에서는 적용을 재고해야 할 정도로 시공간 오버헤드도 크다. 그러나 한번 수집이 벌어질 때 랙이 있다는 말이지, 매 대입 때마다 시도 때도 없이 카운터 값을 변화시키고 그때 스레드 동기화까지 해야 하는 레퍼런스 카운팅도 성능면의 약점은 상황에 따라 피장파장일 수 있다.

언어 차원에서 이런 가비지 컬렉터가 제공되어서 delete 연산자와 소멸자 자체가 존재하지 않는 언어가 요즘 추세이다. 자바나 C#처럼. 하지만 메모리는 그렇게 자동으로 수집되지만, 파일이나 다른 리소스 핸들은 여전히 수동으로 해제를 해야 할 텐데 무작정 소멸자가 없어도 괜찮은지는 잘 모르겠다. 본인은 그런 언어로 대규모 프로그램을 작성한 경험이 없다. C++ 이외의 언어에서는 RAII 개념이 아예 존재하지 않는 건지?

Posted by 사무엘

2015/09/20 08:28 2015/09/20 08:28
, ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1140

본인이 인터넷에서 굉장히 고맙게, 유용하게 잘 열람하는 정보 중 하나는 지도이다.
참 대단하지 않은가? 항공 사진, 길거리 사진, 길 찾기, 실시간 대중교통 연계와 도로 상황 안내 등... 정말 혀를 내두르는 수준이다. 이젠 도대체 얼마나 더 똑똑해질 거리가 남아 있는 걸까?

아울러, 지도의 일종인 차량용 내비게이션 소프트웨어도 도대체 어떤 천재가 만들었나 싶은 생각이 든다. 도로 상황을 감안해서 길을 찾는 건 당연한 소리이고, 그걸로도 모자라서 길 가는 중에 실시간으로 “해당 경로에 사고가 발생했습니다. 우회 경로를 재탐색할까요?”까지도 튀어나온다.

2013년엔 구글 회장이 한번 방북을 하고 났더니 구글어스가 평양을 중심으로 북한의 세부 지리 정보(단순 항공 사진은 예전부터 제공했음)를 제공하기 시작했다. 얘를 시작으로 2014년 하반기부터는 국내 지도 사이트들도 북한 정보를 제공하기 시작했다.
고무적인 현상이다. 물론 구글어스도 그 자체는 처음부터 구글이 개발한 게 아니라 타 업체 솔루션을 인수한 것이긴 하지만 말이다.

본인이 예전에 인터넷 지도에 대해 썼던 글은 이 모든 기능이 별도의 응용 프로그램이 아니라 웹에서 웹 표준 기술만으로 바로 구현 가능해진 것이 신기하다는 요지였다.
이번에는 다른 분야에서 대단히 신기하게 느껴지는 것에 대해 이야기를 늘어놓아 보겠다. 바로 이미지 가공 기술이다.

지도 사이트들이 제공하는 평면 항공 사진은 (1) 넓디넓은 영역을 한결같이 위에서 아래를 내려다보는 단일 각도로 본 이미지이다. 그런데 이거 정말 가공을 많이 했겠다는 생각이 들지 않는가?
이미지에서 원근감이라는 걸 완전히 제거하고 건물들이 마치 스타크래프트 맵처럼 보이게 해야 한다. 중심에서 먼 곳의 건물일수록 모양이 왜곡되어 보이는 카메라 렌즈의 오차를 보정해야 한다.

물론 엄청 높은 곳에서 촬영을 하면 건물 자체의 높이로 인해 발생하는 원근감은 상당수 없어지지만 이번엔 반대로 고층 건물도 높이가 전혀 표현되지 않게 되며, 또 사진의 화질이나 해상도, 그리고 구름으로 인한 시야 가려짐 같은 기술적인 문제도 커진다. 게다가 지구 자체도 근본적으로 평면이 아니라 둥근 구이니, 이로 인한 평면의 왜곡은 카메라의 위치가 높아질수록 더욱 부각되어 보일 것이다.

이런 항공 사진은 전세계의 것을 동시에 촬영하기란 불가능할 테니 여러 사진, 혹은 연속적으로 촬영된 사진을 파노라마 사진 만들듯이 연결해야 할 것이고 이 사진들은 촬영 시간대도 최대한 일치해야 할 것이다(광량의 차이). 또한, 주행 중이어서 시시각각 위치가 변하는 자그마한 자동차나 열차의 모습은 어떻게 보정을 하면 좋을까?
이런 것들을 다 극복하고 전국· 전세계의 항공 사진을 최대한 일관성 있는 색조와 각도로 엮는 것은.. 그 어려움과 복잡함이 정말 말도 못 할 것 같다. 비행기에서 아래를 내려다보고 사진만 팡팡 찍는다고 해서 구현 가능한 게 아니다.

사용자 삽입 이미지
(사진으로 나타난 63 빌딩의 높이와, 그림자의 길이를 비교해 보자.;; 각도가 뭔가 자연스러운 것 같지는 않다. 보정을 한 게 아닐까..)

그 보정이 자동화가 가능한지 아니면 일일이 수작업으로 행해지는지가 궁금하다.
마치 요런 영화 촬영 기법을 떠올리게 한다. 피사체는 시간이 정지한 듯 꼼짝 않고 있는데 카메라가 뱅그르르~ 돌아가면서 다른 위치와 각도에서 피사체를 응시하며 촬영하는 것 말이다. 심지어 사람이 하늘에 붕 떠 있는 채로 그런 장면이 나오기도 하니 더욱 신기한 일이다.

그리고 다음으로 생각할 것은 로드뷰이다.
이것은 앞의 항공 평면 사진과는 반대로, (2) 단일 시점에서의 view를 모든 각도로 제공하는 것이다. 이것은 어쨌든 연속으로 촬영할 수는 없기 때문에 로드뷰의 시점은 수~십수 미터 간격으로 띄엄띄엄 제공된다.

사용자 삽입 이미지

이런 시점 view는 지금이야 지도 사이트에서 쉽게 열람할 수 있는 기능이 됐지만, 옛날에 2000년대 초엔 철도청 홈페이지에서 자바 애플릿 형태로 비슷한 기능을 제공한 게 있었다.
바로 새마을· 무궁화· 통일호 내지 전동차의 객실 내부를 저런 로드뷰처럼 상하좌우 둘러보는 기능이었다.

이 기능은 내부적으로 2차원 평면 형태의 파노라마 사진을 한 장 저장하고, 그 그림의 일부에다 원근법을 적용하여 변형한 것을 표시하는 형태로 구현되어 있다. 내가 아는 건 이게 전부이고 구체적으로 어떤 계산을 하는지, 그리고 이런 용도로 사용하는 사진은 어떤 형태이고 어떻게 촬영하는지에 대해서는 잘 모른다. 그야말로 상하좌우 시야각이 다 열려 있는 특수한 카메라를 써야 할 텐데..

내가 10여 년 전에 이미 3차원 그래픽 시연 프로그램이라는 것도 만들어 봤지만, 비트맵 이미지로부터 3차원 시야를 어떻게 구현하는지는 여전히 감이 안 온다.
2차원 이미지에서 원근감을 넣거나 없애고, 평면과 공간 사이를 오고 가게 하는 기술이 참 대단하게 느껴진다. 그 기술이 인터넷 지도, 더 나아가 증강현실 같은 것도 가능하게 한 셈이다.

Posted by 사무엘

2015/04/08 08:32 2015/04/08 08:32
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1081

뭐, 무식이 자랑이랄 수는 없겠지만,
본인은 전산학 내지 컴퓨터공학의 여러 분야들 중에서 문외한에 가깝게 제일 모르는 분야는 통신, 네트워크, 웹, 보안 쪽이다.
왜 제일 모르느냐 하면, 저건 컴퓨터 한 대만으로 독학이 가능하지 않고, 뭔가 '감'을 터득할 수 없는 분야이기 때문이다. 그래서 그런 걸 잘하는 사람들이 부럽다..

일례로 완전 최저수준 소켓 API와, 고수준 HTTP API 사이의 중간 과정에 대한 감이 전혀 없다. 후자도 분명 전자를 이용해서 구현됐을 텐데, 내부 구현이 어찌 돼 있는지 난 아는 게 없다.
그리고 네트워크 트래픽이 컴퓨터의 I/O 병목엔 어떤 영향을 끼치는지, 그 패킷이 어떻게 해서 한 운영체제 내부의 특정 응용 프로그램으로 잘 전달이 되는지, DDoS 공격이 서버 컴퓨터에 어떤 물리적인 영향을 끼쳐서 서버를 뻗게 할 수 있는지, (아님 단순히 프로세스/스레드의 무한 스폰으로 인해 소프트웨어적인 자원 고갈만으로 뻗는 건가?)

HTTP 프로토콜에서 파일 업로드는 어떤 절차를 거쳐서 되는지, 방화벽이라는 게 정확히 뭘 하는 물건인지,
왜 구닥다리 윈도 2000/XP sp0을 띄운 채로 랜선을 꽂으면 뭐가 뚫려서 어떻게 되는지..
요즘은 네트워크 패킷은 하부 계층에서 압축이나 암호화를 좀 하는 게 있는지 등등..

이런 것들은 난 하나도 모..른..다. 저런 거 하나도 몰라도 <날개셋> 한글 입력기 개발하는 덴 아무 지장이 없기 때문이다.
그렇다고 해서 내가 컴퓨터 명령어 체계나 운영체제/소프트웨어 자체의 내부 구조나 보안에 대해 전혀 모르느냐 하면 그것도 물론 아니니.. 지식의 분포가 좀 불균형하다면 불균형한 셈이다.

본인은 초딩 중고학년 때 개인용 PC, 중학교 때 모뎀과 PC 통신, 고등학교 때 인터넷과 이메일, 그리고 대학교 때 무선 인터넷과 휴대전화의 순으로 문명의 이기들을 접했다. 랜 선이라는 걸 태어나서 처음으로 구경한 게 고등학교 때부터인데, 그 기간 동안 언젠가 집도 인터넷 접속 방식이 전화 모뎀에서 전용선으로 바뀌었다. 그때가 한창 전국적으로 인터넷 전용선이 깔리던 시절이었으니까.

지금까지 통신 기술은 정말 눈부신 속도로 발전했다.
신문· 방송에서 기자의 이메일을 공개하는 게 대세가 된 게 1990년대 후반부터이다.
지금으로부터 10여 년 전엔 '블로그'라는 단어가 도전 골든벨의 마지막 문제의 답이었다는 게 믿어지시는가? (그것도 학생이 못 맞혔고 그 당시엔 내게도 생소했다)

옛날에는 인터넷 연결을 위해서도 PC 통신을 할 때처럼 먼저 전화를 걸어야 했다. 사용 시간 카운터가 올라가는 자그마한 인터넷 연결 창이 뜬 동안만 인터넷을 이용할 수 있었다.
또한, 모뎀과 마우스를 동시에 사용하려면 두 물건을 서로 COM 포트가 충돌하지 않게 배치를 해야 했다.
Windows 3.x에서는 운영체제 차원의 네트워크 지원이 전무하기 때문에 트럼펫 Winsock인지 뭔지 하는 걸 먼저 설치해야 했다.

이 모든 것들이 지금은 까마득한 옛날 이야기가 됐다.
지금은 뭔가 그렇게 상태를 확인하면서 인터넷을 해야 하는 상황은 스마트폰 태더링으로 무선 인터넷을 쓸 때 정도이고 이것도 제약, 압박감, 부담 같은 건 옛날과는 비교할 수 없이 작아졌다.
메인보드가 어떻게 공간 워프를 했는지, 요즘은 유선 랜과 무선 랜도 전부 내장되어 나온다. 따로 뭘 장착조차 할 필요 없이 바로 접속만 하면 된다.

오늘날 인터넷이라고 불리는 그 통신망은 OSI 레이어 계층 중 제3계층(네트워크 계층)을 차지하는 IP라는 프로토콜을 기반으로 동작한다. IPv4, IPv6 같은 주소 체계도 이 계층에서 규정하는 것이기 때문에 모든 인터넷 통신은 이 체계를 기반으로 구성되어 있다.

그리고 그 아래의 제4계층(전송 계층)에는 인터넷 프로토콜을 따르는 네트워크 패킷을 보내는 방식의 차이를 규정하는 프로토콜이 있는데, 크게 TCP와 UDP가 있다.
TCP는 보낸 패킷이 반드시 순서대로 도착한다는 것은 보장되지만, 보냈던 단위랄까 형태가 그대로 도착하지는 않는다.
aaa, bb, ccccc, ddd, e 이렇게 패킷을 보냈으면 받는 쪽은 aa, ab, bccc, cc, dd, d, e 뭐 이렇게 받을 수도 있고 다른 형태가 될 수도 있다. 조립은 받는 쪽에서 알아서 해야 한다.

UDP는 TCP와는 달리 보낸 패킷이 원래의 형태 그대로 간다는 보장은 되지만.. 일부 패킷이 전송 과정에서 누락될 수가 있다.
즉, 위의 경우 ddd가 누락돼서 aaa, bb, ccccc, e 이렇게 갈지도 모르지만.. 일단 간 놈은 원래 형태 그대로 간다. 패킷의 누락 여부 판단을 받는 쪽에서 알아서 해야 한다.
그래서 TCP는 일종의 스트림 지향적이며, UDP는 개개의 패킷이 모 아니면 도 형태로 가는 메시지 지향적이다.

형태도 보존되고 누락 현상도 없는 만능 프로토콜이 없는 이유야 뭐, 세상에 값도 싸고 성능도 좋은 물건은 존재하지 않기 때문인 것과 같은 맥락일 것이다.
그게 필요하면 UDP 같은 걸 기반으로 패킷 누락을 감지하고 재전송을 요청하는 로직을 응용 프로그램이 별도로 구현해 줘야 한다.

온라인 게임에서는 “기관총 난사 내지 캐릭터 이동 같은 것만 UDP이고 나머지는 다 TCP”라는 말 한 마디로 요약된다.
자주 발생하기 때문에 반응성이 중요하고 적당히 좀 씹혀도 상관 없는 것만 UDP이고.. 나머지 크리티컬한 것들은 다 TCP를 써야 한다는 뜻이다.
그러나 온라인 게임에서 발생하는 트래픽의 상당수, 대략 70% 가까이는 그래도 UDP 방식이라고 한다.

실시간으로 스트리밍되는 대용량 오디오/비디오 데이터도 자명한 이유로 인해 UDP 방식으로 전송된다.
이런 차이를 보면, TCP와 UDP의 관계는 사실상 무손실 압축과 손실 압축의 관계나 마찬가지인 것 같다.

TCP의 경우 응용 프로그램이 아니라 아래의 프로토콜 차원에서 패킷의 누락을 감지하여 누락이 있는 경우 재전송 요청을 한다.
그런데 모바일처럼 네트워크 환경이 원래 워낙 열악해서 패킷 손실이 굉장히 자주 발생하는 곳에서는
TCP 방식에서는 끝도 없이 재전송 요청을 하고 받은 데이터에 결함이 없는지 체크와 빠꾸만 반복하느라 응용 프로그램이 그 동안 멍하니 있어야만 하는 일이 발생한다고 한다.
즉, TCP가 구조적으로 오버헤드가 더 크니, 네트워크가 열악한 곳에서는 그런 동작을 감안해야 한다.

게임에서 그래픽 엔진, 물리 엔진, 동영상/캡처 엔진도 아니고 네트웍 엔진 미들웨어로 먹고 사는 분이 국내에 일단 한 분 계신다. 넷텐션의 대표이사인 배 현직 씨. 이 업계에서는 이미 유명인사이다.

난 네트워크 쪽 프로그래밍을 해 본 건 먼~ 옛날에 소켓 API 대충 뚝딱해서 오목을 만들고..
DirectPlay를 써서 스크래블 정도 보드 게임에다가 네트웍 플레이를 넣어 본 게 전부이다. 그래도 그것만으로도 굉장히 재미있는 경험이었다.
저수준에서 패킷 암호화, 각종 오류 처리 그런 건 모른다. DPlay는 나름 하드웨어 독립을 추구한 통신 API이긴 한데, 요즘은 모뎀이고 시리얼 케이블 그딴 건 다 없어졌으니 그런 추상화 계층이 필요가 없어지면서 자연스레 도태했다. 잘은 모르겠지만 제1계층(물리 계층)은 거의 획일화가 돼 버린 것 같다.

※ 여담. IPX는 어디로 갔는가?

스타크래프트에서 배틀넷 말고 그냥 LAN으로 친구들끼리 팀플을 할 때, 옛날에는 배틀넷 다음으로 위에서 둘째인 IPX를 으레 고르곤 했다. 그러나 어느 패치 때부터인가 맨 아래에 UDP가 추가되었으며 그걸 고르는 걸로 구조가 바뀌었다. IPX는 동작하지 않기 시작했다. 어찌 된 일일까?

IPX라는 프로토콜은 똑같이 이더넷 랜선으로 통신을 하지만, 오늘날의 인터넷과는 다른 방식으로 통신을 한다. 즉, IP와 대등한 제3계층에서 방식이 다른 프로토콜인 것이다. IPX는 옛날에 네트워크 솔루션으로 유명했던 노벨 사에서 개발했고 실제로 매우 널리 쓰이기도 했지만 오늘날은 IP에 밀려서 사라졌다.

Windows 95때까지만 해도 네트워크 구성요소들을 설치하고 나면 기본으로 깔리는 것은 IPX였다. TCP/IP 지원 기능은 운영체제 CD를 넣어서 별도로 설치해야 했다. 무슨 말이냐 하면, 오늘날 당연시되고 있는 이 컴퓨터의 IP 주소를 설정하는 기능이 Windows 95에는 기본으로 없었다는 뜻이다. (심지어 네트워크 기능이 설치된 컴에서도)

사용자 삽입 이미지

그 다음 1990년대 중후반, Windows 98부터는 인터넷의 중요성이 워낙 크게 부각되기 시작했으니 TCP/IP 지원도 같이 포함되었다.
여담이지만 Windows에서는 등록정보/속성을 나타내는 단축키가 R인 편인데, 95에서는 유독 저 대화상자에서만 R은 삭제이고, 등록정보는 P였다. 무척 불편했는데 이 역시 98부터는 다같이 R로 개선됐다.

하긴, 본인도 옛날부터.. Windows가 근거리 네트워크 차원에서 제공하는 컴퓨터 간의 폴더 공유 기능과, 웹브라우저로 띄우는 인터넷은 기술적으로 무슨 관계인가 궁금하긴 했다.
인터넷 열풍 앞에서 IPX는 점점 잉여로 전락했으며, Vista부터는 드디어 IPX 지원이 hlp 도움말만큼이나 짤렸다. 그래서 스타크래프트도 근거리 팀플에 인터넷 프로토콜을 사용하는 UDP 지원이 추가된 것이다.

Posted by 사무엘

2015/02/05 08:37 2015/02/05 08:37
, , , ,
Response
No Trackback , 10 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1058

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

  • 컴퓨터에서 각종 계정의 암호를 설정하는데, 암호는 무조건 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 사무엘

2014/11/04 08:37 2014/11/04 08:37
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1025

유니코드 1.x가 제정되었을 때는 믿거나 말거나 한글도 글자마디는 완성형 몇천 자만 지금과는 딴판의 영역에 등록되어 있었다. 단, 글자마디뿐만 아니라 옛한글을 포함한 자모도 자음 134개(물론 초성과 종성의 개수는 서로 다르고 따로 등록됨), 모음 66개가 등록되어서 이 자모들을 아래아한글 2.x가 한컴 2바이트 코드에서 그대로 채택해서 썼다. 한컴 2바이트 코드는 기존 조합형 코드와 유니코드를 적당히 짬뽕한 문자 코드였던 것이다.

유니코드는 첫 도입 배경이 저렇다 보니 “유니코드 = all 2바이트 단일 문자 체계 = wide character 문자 체계”라고 혼동하는 사람이 적지 않다. 그러나 이는 개념적으로 올바른 관계가 아니다. 2바이트 문자 체계로만 치자면 한컴 2바이트 코드도 이에 해당하며, 윈도 이외에 유닉스 계열 OS에서는 wide character는 16비트가 아니라 32비트인 경우도 있다. 왜 32비트이냐 하면 6만 5천여 개라는 집합 크기도 시간이 흐르다 보니 부족해졌기 때문이다.

1996년에 유니코드 2.0이 제정되면서 유니코드는 오늘날 우리가 아는 유니코드와 같은 뼈대가 갖춰졌다. 한번 등록한 문자는 이제부터 재배치나 제거 없이 영구불변으로 굳히기로 했으며, 이때 현대 한글 글자마디 11172자가 순서대로 고스란히 등록되었다. 2바이트 조합형처럼 비트 연산은 못 쓰지만 그래도 테이블 없이 뺄셈과 나눗셈, 나머지 연산으로 한글의 자소 정보를 얻을 수 있으니, 과거 조합형 한글 코드의 장점을 유니코드에서도 물려받은 셈이다.

외국 위원들의 반대를 무릅쓰고 한글에다 유니코드의 금싸라기 영역을 이만치 할당 받기 위해 한국 위원회 사람들이 애를 많이 썼다. 사실 확장완성형도 유니코드 등록 근거를 대기 위해 급히 만들어진 것이라고 한다.
이와 더불어 유니코드 2.0에서는 중요한 개념 내지 꼼수가 추가로 도입되었는데, 바로 surrogate이다.
16비트 공간 중 일부 영역은 그대로 쓰지 말고 따로 떼어 내서 두 글자를 뭉쳐서 더 많은 종류의 글자를 표현하는 데 쓰자는 것이다.

0xD800부터 0xDBFF는 high surrogat이고, 0xDC00부터 0xDFFF까지는 low surrogate이다. high는 언제나 앞에, low는 언제나 뒤에 오는 식으로 역할이 딱 고정되어 있다. 1024개의 앞짝과 1024개의 뒷짝이 만나니, 총 2048개의 독립 글자를 희생하여 2의 20승, 약 100만여 개의 글자 공간을 추가로 확보할 수 있게 된다. 요컨대 유니코드에 U+D800 같은 글자는 없고, U+D7FF 다음에는 곧바로 U+E000이 이어진다. 그 대신 0xD800과 0xDC00이 만나면 U+10000이라는 surrogate, 즉 확장 평면이 시작될 뿐이다. 예전의 16비트 단일 영역은 '기본 다국어 평면'(BMP)이라고 불리게 되었다.

비록 과거의 1바이트/2바이트 혼합 체계보다는 사정이 훨씬 낫고 문자열 처리가 수월한 건 사실이지만, 어쨌든 유니코드도 확장으로 인해 2바이트 단일 표현(UCS2)이라는 깔끔한 장점은 포기해야 하게 되었다. 이쯤 되니 유니코드라는 개념에서 문자 코드와 인코딩을 구분해서 표현해야 할 필요가 생겼다.

유니코드 자체는 UCS, 즉 universal character set이라 불리는 단일 문자 집합이다. 얘는 '가'라는 한글 글자에다가 U+AC00이라는 코드값을 부여해 줄 뿐, 그 코드값이 메모리나 파일에 어떻게 표현되는지에 대해서는 규정하지 않는다. 이를 표현하는 방식이 바로 Unicode transfer format, 즉 인코딩이 된다.

모든 유니코드 번호를 아무 뒤끝 없이 32비트 정수 하나로 균일하게 표현하면 그것은 UTF32이다. 아까 wide character가 4바이트인 플랫폼은 바로 UTF32를 구현하는 자료형인 것이다. 가장 깔끔하고 공간도 넉넉하고 모든 글자를 하나씩 쉽게 접근할 수 있지만 한 글자가 4바이트나 차지하여 메모리 낭비가 심하다.

BMP 영역에 있는 놈은 종전대로 16비트 정수 하나로 표현하고 확장 평면에 있는 놈만 surrogate 두 개로 쪼개서 표현하는 방식은 UTF16이라고 불린다. UCS2를 개념적으로 확장한 것이기 때문에 처음부터 2바이트 wide character를 표방하며 개발된 Windows 플랫폼이 매우 사랑하는 방식이다. 비록 Windows의 wchar_t는 이제 유니코드 코드 포인트 하나를 온전히 표현할 수 있을 정도로 충분히 크지 못한데도 말이다.

끝으로, 그 이름도 유명한 UTF8이 있다. 얘는 U+007F 안에 드는 전통적인 알파벳· 숫자, 제어 문자들은 1바이트로 유지하고, 나머지 BMP 영역의 외국어들은 2~3바이트로 표현하고 surrogate는 BMP와 동일한 4바이트로 늘여 표현하는 진정한 multibyte 인코딩이다.

n째 문자를 찾는 무작위 접근은 안 되겠지만, Windows NT처럼 커널을 처음부터 16비트 문자 단위로 설계하지 않고도 기존 8비트 문자 시스템에서 유니코드를 단절감 없이 표현할 수 있다는 엄청난 장점이 있다. CPU의 엔디언(비트 배열 순서)의 영향을 받지 않으며, tail byte가 기존 영문· 숫자와 충돌을 일으키지도 않는다는 점도 좋고 말이다.
그래서 얘는 웹에서 매우 사랑받고 있고 윈도 이외의 플랫폼에서는 파일뿐만 아니라 메모리 저장용으로도 UTF8이 즐겨 쓰인다. 사실 윈도만 이례적으로 UTF16을 너무 사랑하고 있는 것이고.. ㅎㅎ

여담이지만 UTF32, 16, 8 중 유니코드의 문자 집합이 먼 미래에 또 확장되어야 할 때, 공간이 가장 넉넉하게 남아 있는 놈은 두 말할 나위 없이 UTF32이다. UTF8이야 애초부터 들쭉날쭉 가변 길이 인코딩을 표방했기 때문에 한 글자당 4바이트보다 더 긴 5~6바이트까지 약간 더 확장할 여지가 있다. 지금 당장은 그것까지는 쓰이지 않지만 말이다.

하지만 UTF16은 유일하게 확장의 여지가 전혀 없다. 지금 surrogate 영역이 다 차 버리면 surrogate의 surrogate라도 또 만들지 않는 이상 답이 없다. 그리고 그런 헛짓을 할 바에야 차라리 UTF16을 폐기하고 UTF8 아니면 UTF32로 갈아타는 게 낫지..;; 이런 미묘한 면모가 있다.

다만, 한글 표현의 관점에서는 메모리가 가장 적게 드는 인코딩이 UTF16이라는 것도 감안할 점이다. 현대 한글 글자마디의 경우 UTF8은 3바이트, UTF32는 4바이트이지만 UTF16은 2바이트다. 초-중-종성이 모두 갖춰진 옛한글이라면 UTF8과 UTF32는 각각 9바이트, 12바이트를 차지하지만 UTF16은 6바이트이니 차이가 더 벌어지게 된다. 유니코드에는 한글이 완성형(글자마디+호환용 자모) 방식과 조합형(세벌 한글 자모) 방식이 모두 등록되었으며 완성형 방식도 11172자가 순서대로 모두 등록되었으니, 예전의 조합형· 완성형 논쟁을 완전히 종결짓는 데 성공했다.

Windows NT도 처음에 개발될 때 문자 처리 단위를 wide로 무리해서 넓히느라 고생하지 말고, 그냥 UTF8만 도입했으면 어땠을까 싶지만 이제 와서는 다 지난 일이다. 아무래도 UTF8보다야 UTF16이 컴퓨터의 입장에서는 더 빠르고 간편하게 각각의 문자를 인식할 수 있으며, 이것이 메모리와 성능 소모면에서 UTF32와 UTF8 사이의 완충지대 역할을 해 온 건 부인할 수 없기 때문이다. 덕분에 Windows API의 관점에서는 UTF8조차도 native 인코딩인 유니코드 UTF16으로부터 '변환'되어야 하는 여러 multibyte 인코딩 중의 하나일 뿐이다~! ㅎㅎ

옛날에 인터넷 익스플로러의 버전이 5~6이던 시절엔 한글로 된 URL이 인식이 잘 안 돼서 맨날 “URL을 UTF8로 보냄” 옵션을 끄라는 지시가 팁처럼 공유되곤 했다. 당시엔 Unicode-aware하지 않은 웹 서버가 아직 많아서 말이다. 오늘날로 치면 UAC(사용자 계정 컨트롤)를 끄거나 팝업 창 허용 기능을 사용하는 것과 비슷한 편법이다.
하지만 요즘은 UTF8 방식 URL이 표준으로 정착한 지 오래다. 호환성을 중요시하는 IE에나 그런 옵션이 있지, 크롬 같은 브라우저는 선택의 여지 없이 무조건 UTF8이기도 하고 말이다.

유니코드는 문자 처리 기술의 발전과 함께 더욱 덩치가 커졌으며, 한편으로 더욱 복잡해지고 지저분해지고 있다.
UTF32가 아닌 인코딩으로는 어차피 메모리 배열 인덱스만으로 실제 글자 인덱스를 얻을 수 없는 것은 물론이거니와, 메모리 상으로 존재하는 글자 코드 포인트 수와, 화면에 출력되는 글자의 수도 일대일 대응이 전혀 이뤄지지 않게 되었다. 옛한글이라는 것도 유니코드 관련 기술이 방대해지면서 덤으로 같이 처리 가능해졌을 뿐이다. 진짜 미치도록 복잡한 문자에 비하면 옛한글 쯤이야 양반이지... 동일한 글자를 나타내는 방법이 여러 가지 존재하게 되어서 정규화라는 것도 필요해졌다.

코드 포인트 값만으로 정렬을 하는 것 역시 상당수 의미를 잃었다. 옛한글 자모는 유니코드 5.2 때 한양 PUA 비표준에만 존재하던 것들이 추가 등록되었는데, 이것들의 코드 포인트상의 순서를 따지는 건 부질없는 짓이다. 가뜩이나 부족한 BMP 공간의 여러 틈새에 산발적으로 간신히 등록된 것 자체를 감지덕지해야 할 판이다.

한자는 더욱 가관이다. 유니코드에서 공간을 압도적으로 제일 많이 차지하고 있는 문자인 건 두 말할 나위도 없거니와.. BMP 영역에 이미 등록돼 있고 호환용 같은 이유도 없는데 작업자의 실수로 인해 나중에 surrogate 확장 평면에 중복 등록된 글자도 있고, 일본 문자 코드의 실수 때문에 문헌에 전혀 등장한 적이 없는 유령 한자가 등재돼 있기도 하다.

이것이 오늘날의 컴퓨터 문명을 지배하고 있는 가장 원초적인 규범에 속하는 유니코드의 현실이다. ㅎㅎ
수십 년 주기로 유니코드를 전면 reset하고 코드값을 재정리하면 어떨까 싶지만 그건 기존 컴퓨터 문명이 핵 전쟁 같은 걸로 폭삭 없어지지 않는 한, 상상 속에서나 가능한 일일 것이다.

Posted by 사무엘

2013/12/16 08:25 2013/12/16 08:25
, , , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/909

디지털 컴퓨터는 전자 신호로 0과 1만을 인식할 수 있다. 그렇기 때문에 컴퓨터에서는 문자 역시 0과 1의 조합인 숫자로 표현되며, 문자를 그런 숫자에다가 대응시키는 규칙이 바로 문자 코드이다. 정보 교환을 원활히 하기 위해서는 보내는 쪽과 받는 쪽이 모두 문자 코드가 통일돼 있어야 함은 두 말할 나위가 없다.

정보량의 최소 단위는 1비트이지만 현실적으로 컴퓨터의 기억 장치들이 한 글자로 취급하는 정보량의 최소 단위는 8비트, 즉 바이트이다. 8비트, 2^8승, 즉 256이라는 정보량은 숫자와 알파벳을 정하는 데는 충분하고 상위 1비트를 잉여화하여 오류 검출용으로까지 사용할 수 있을 정도이지만, 한글이나 한자 같은 문자를 담는 데는 턱없이 부족하다.

한자는 글자를 체계적으로 부분글자로 분해할 뾰족할 방도가 없는 상태로 글자 수가 너무 많다. 한글은 글자 생성 체계는 한자보다 훨씬 더 유리한 위치에 있지만, 실용적으로 편하게 다루려면 여전히 1만여 개의 미리 조합된 음절 형태를 그대로 배당해야 한다.

예를 들어 현실에서 '학교'라는 단어는 두 글자로 간주되지, 데이터베이스나 문서 분량 같은 데서 5글자라고 계수되는 곳은 아무도 없다. 코드 차지 영역을 줄이자니 메모리 사용량이 늘며, 그리고 오늘날로 치면 화면에 보이는 글자 길이와 메모리를 차지하는 글자 길이가 서로 완전히 따로 노는 complex script 급의 복잡한 기술이 필요해진다.

결국 한글과 한자는 1바이트만으로 표현할 수 없고 통상 2바이트로 표현된다. 그런데 기존 1바이트 영문· 숫자를 건드릴 수는 없으니 1바이트와 2바이트 문자가 공존하는 multi-byte 코드 체계가 만들어진다. 영문권에서 패리티 비트 내지 유럽 특수문자를 표현하는 데 쓰이는 최상위 1비트는, 이 문자가 1바이트로 끝인지 아니면 2바이트 문자의 첫 바이트(lead byte)인지를 판별하는 비트로 쓰인다.
공교롭게도 한글· 한자는 폭도 균일한 2글자 분량을 차지하여 비주얼 상 잘 어울린다. 전각· 반각이라는 개념이 여기서 유래된다.

그런데 lead byte는 그렇다 쳐도 2바이트의 다음 둘째 바이트인 tail byte도 기존 순수 1바이트 문자들과(영문· 숫자 같은) 전혀 겹치지 않게 할 것인지? 아니면 어차피 얘는 lead byte에 의해 변별이 됐으니 좀 문맥 의존적으로 겹치는 걸 허용할 것인지가 문제가 된다. 한글 코드의 경우 완성형은 겹치지 않으나 조합형은 겹친다.

그렇기 때문에 조합형은 tail byte가 대문자 알파벳과 소뭇자 알파벳이 제각기 따로 될 수 있고 심지어 \ 역슬래시 문자가 나올 수도 있다. 이런 이유로 인해 조합형은 1비트 + 초중성 5비트씩 한글의 구성 원리를 매우 잘 반영하여 설계된 문자 코드임에도 불구하고 당시 8.3 제약이 있던 시절에 파일 이름을 사실상 한글로 지정할 수 없었으며, 심지어 이론적으로는 // 주석을 조합형 한글로 지정한 경우 \ 때문에 2-byte aware 하지 않은 컴파일러에서는 충돌이 발생할 수도 있었다.

옛날에 한글 MS-DOS 시절에 한글 도스 셸이나 QBasic처럼 텍스트 GUI(?)를 구현한 프로그램들을 실행해 보면 한국 마소가 굉장히 잘 만든 게 있었다. 메뉴나 대화상자 같은 게 표시되어서 배경에 있던 2바이트 텍스트를 반토막 내더라도 깨진 문자열을 보여주는 법이 결코 없었다. 늘 짝수 바이트가 유지돼야 하는 한글/한자 영역이 홀수 바이트로 줄어들면 가장자리를 하나 삭제해 주면 된다.

그러나 문맥 의존적인 문자 코드로 그런 걸 구현하려면 문자열을 처음부터 읽어 봐야 하고, 두 바이트 중 하나가 소실됐을 때의 뒷처리가 문맥 독립 코드보다 더 어려우면 어렵지 쉽지는 않을 것이다. 불가능하다는 뜻은 아니지만.

조합형을 옹호하고 완성형을 까기에만 바쁜 분들의 심정이야 세벌식+한글 에반젤리스트로서 본인은 적극 이해한다. 그러나 과거의 2바이트 한글 코드의 이면엔 이런 면모도 있었음을 지적하고자 한다. 완성형은 여러 이슈가 얽혀서 그렇게 만들어졌지, 작정하고 한글을 난도질하려는 악의적인 의도로 만들어진 건 아니었다. 문맥 독립성뿐만 아니라 굉장히 보수적인 국제 규격 권장 사항을 만족하는 방식으로 문자 코드를 만들려다 보니, 한글 11172자에다 한자와 각종 특수문자들까지 넣을 절대적인 공간 자체가 부족했기 때문이다.

나중에 완성형에다 어거지로 한글 부족분을 채워 넣은 cp949 확장완성형은 어차피 조합형처럼 문맥 독립성이 깨졌다. 물론, 어차피 이렇게 만들 거면 처음부터 조합형으로 가지 하는 비판은 피할 수 없게 된 게 사실이다. 그런데, 이런 비슷한 삽질을 일본도 문자 코드를 만들면서 했으며, 이를 우리나라도 그대로 답습했을 뿐이다.

조합형과 완성형은 11172자와 2350자의 차이뿐만 아니라 한글 낱자를 표현하는 방식에서 매우 큰 차이가 있다.
조합형은 글자마디와 자모의 차이가 사실상 없다. 그냥 초 중 종성 중 한 성분만 있으면 자모이고, 초성과 중성이 갖춰졌으면 글자마디이다. 초성 ㄱ과 종성 ㄱ을 구분해서 표현할 수 있고 초성+종성이나 중성+종성 같은 '미완성 한글'도 얼마든지 표현할 수 있다.

그러나 완성형엔 그런 개념이 없다. 한글 입력을 처음 시작했을 때 쓰라고 '호환용 한글 자모'라는 게 있는데 그건 한글이 아니라 명목상으로는 '특수문자' 영역이다. 그냥 한글 자모 모양인 그림일 뿐이다. 초성+종성 구분이나 미완성 한글 표현 같은 건 없다.

메모리 1바이트가 아깝던 16비트 도스 시절에 국내에서는 조합형 한글 코드+글꼴이 쓰였지 마소의 윈도처럼 2350자 완성형 코드+글꼴로 돈지랄을 하는 프로그램은 전혀 없었다. 이런 압도적인 인지도의 차이로 인해 조합형은 1992년에 한국의 복수 표준으로 승격되어서 cp1361이라는 이름으로 나름 운영체제의 코드 페이지에 등록도 됐다.

자, 이렇게 컴퓨터는 1바이트 인코딩에다가 한중일 문화권을 위한 1+2바이트 멀티바이트 인코딩 구도가 유지되었고 마소에서는 이를 도스 시절부터 코드 페이지라고 불렀다. 그런데 이런 문자 코드들은 (1) 알파벳· 숫자 같은 공통 문자를 제외하면 같은 문자라 해도 국가마다 배당된 코드값이 같을 수가 없고, (2) 문자 집합 자체의 크기가 너무 작아서 세계 모든 문자들을 한 코드 페이지에다 담을 수 없다는 문제가 있었다.

人(사람 인)이라는 한자가 한국· 중국· 일본의 표준 코드에서의 코드값이 같을 리가 없으니 (1)은 자명한 문제다. (2)의 경우, 2바이트 코드라 해도 앞서 보았듯이 1바이트 문자와의 충돌을 피하기 위해 매우 제한된 영역의 바이트들만 묶을 수 있다. 이 때문에, 문맥 의존까지 시킨다 해도 추가로 만들 수 있는 문자는 1만여 자에 불과하다. CJK에서 쓰는 상용 한자들이나 간신히 다 집어넣을 정도이다.

그래서 1980년대 말부터 이런 발상의 전환이 이뤄졌다. “앞으로 컴퓨터의 메모리는 증가하고 소프트웨어 국제화의 중요성은 커질 테니, 글자 하나의 크기를 16비트로 쿨하게 확장하고 6만여 자의 공간에다가 전세계 언어 문자들을 집어넣고 동일 문자 동일 코드값을 실현하는 게 어떨까?”

이것이 바로 유니코드의 존재 목적 되시겠다. 컴공 전공자가 아니더라도 컴퓨터에서 '유니코드'라는 말은 한 번쯤은 다들 들어 보셨을 것이다. 이건 그야말로 컴퓨터 문자 코드계의 바벨 탑 내지 에스페란토 같은 물건이다.

마이크로소프트는 소프트웨어의 국제화에 굉장한 혜안이 있던 기업이었다. 그래서 OS/2와 결별하고 Windows NT를 첫 개발할 때, 애초부터 8비트 문자가 아니라 유니코드를 담을 수 있는 16비트 문자를 기반으로 설계했다. 심지어는 NTFS 파일 시스템까지도. 그리고는 이를 독자적으로 wide character이라고 부르기 시작했다. 어차피 8비트 문자만으로 충분하던 라틴 문화권에서는 별로 득이 되는 것도 없이 메모리 사용량만 두 배로 뻥튀기되는 대가를 감수하고라도 말이다.

Win32 API는 기존 16비트 윈도 API를 최대한 닮게 설계되었지만, 문자열을 다루는 모든 API에 A 버전과 W 버전 구분이 생겼다. 다만, 32비트 시절에 처음으로 도입된 OLE/COM 같은 기술은 처음부터 오로지 유니코드(= wide) 문자열만 취급하게 만들어졌다.

PE 방식으로 만들어진 32비트 EXE/DLL은 string 테이블, 메뉴, 대화상자 같은 리소스의 저장 포맷도 다 유니코드 방식으로 바뀌었다. 윈도 3.1에다가 Win32s를 설치하면 32비트 커널 DLL뿐만 아니라 각종 코드 페이지 변환 테이블도 설치되는 걸 볼 수 있다. 그게 바로 리소스를 변환하기 위해서이다.

윈도 NT가 3.x나 9x보다 메모리 사용량이 매우 많았던 이유 중 하나도 유니코드 때문이며, 반대로 윈도 9x가 유니코드 API를 지원하지 않았던 이유도 가정용 PC의 부족한 메모리 문제 때문이다.
이 때문에 컴파일 스위치만 바꿔서 유니코드와 기존 멀티바이트를 모두 커버할 수 있는 TCHAR, _T 같은 개념도 그때 생겼다. 두 개의 문자 포맷을 모두 지원하는 작업은 정말 엄청난 대공사였을 것 같다.

Posted by 사무엘

2013/12/13 08:24 2013/12/13 08:24
, , , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/908

지뢰찾기 연구

요즘 팔자에도 없던 지뢰찾기에 살짝 재미가 붙었다.
본인은 비슷한 학력· 경력으로 IT 업계에 종사하는 여느 사람들과는 달리, 머리 싸움을 즐기는 스타일이 전혀 아니었으며 복잡한 퍼즐 게임 따위와도 담을 쌓고 지내는 편이었다. 이런 점에서 본인은 완전 퍼즐 게임 매니아인 T모 님과는 성향이 다르다.

그래도 지뢰찾기 정도면 요령을 알고 나니까 은근히 재미있다. 초보 레벨로는(9*9, 지뢰 10개) 40초~1분 남짓한 시간 동안 대략 60~70%대의 승률로 깨겠다. 처음엔 초보 레벨조차도 5분이 넘게 끙끙대기도 했으나, 마치 경부선 서울-부산 열차의 운행 시간이 17시간에서 6시간대~4시간대로 줄어들듯이 시간이 단축되었다.

사용자 삽입 이미지
지뢰찾기는 소련에서 개발된 테트리스와 더불어 시간 죽이기용으로 상당히 적절한 컴퓨터용 퍼즐인 거 같다. 여느 보드 게임과는 달리, 물건이 먼저 존재하다가 컴퓨터로 옮겨진 게 아니라 처음부터 컴퓨터용으로 만들어진 게임이라는 차이가 있다.

맥북의 터치패드 격인 트랙패드로는 도저히 게임을 할 수 없는 듯했다.
두 손가락을 동시에 누르거나 패드 우측 하단을 지그시 누르면 우클릭이 되긴 하는데, 이게 생각보다 정확하게 인식되지가 않는 듯하기 때문이었다.

지뢰가 있다는 깃발만 꽂으려고 우클릭을 했는데, 그게 좌클릭으로 인식되어 지뢰를 밟고 장렬히 죽는 참사가 한두 번 발생하는 게 아니어서 말이다. 단, Windows Vista 이후부터 새로 개발된 지뢰찾기는 Shift+클릭으로 우클릭, 더블클릭으로 좌우 클릭도 돼서 조작이 훨씬 더 편해졌다.

키보드로는 Space는 셀 개봉(좌클릭)이고, Shift+Space가 깃발(우클릭)이다.
그런데 이번엔 깃발이 꽂힌 것을 제외한 모든 인접 셀들을 한꺼번에 개봉하는 건 키보드로 어떻게 하는지 모르겠다. 게임에 익숙해지고 나면 셀 개봉은 하나씩 클릭하는 것보다 저렇게 개봉을 훨씬 더 즐겨 하게 되는데 말이다.

지뢰찾기라는 게임은 풀이 순서를 논리적으로 명확하게 유추 가능한 상황이 대부분이지만, 가끔은 주어진 정보만으로는 정확한 지뢰 배치를 알 수 없어서 찍기(guessing)를 해야 하는 경우도 있다. 지뢰가 정확하게 어떤 조건으로 배치되어 있을 때 그런 상황이 생기는지는 잘 모르겠다.

숫자 정보로부터 유추 가능한 지뢰 배치 가짓수는 기본적으로 폭발적으로 증가할 수 있으며, 어떻게 될 수 있는지 백트래킹으로 일일이 하나하나 때려박아 넣으며 추적을 하는 수밖에 없다. 뭔가 네모네모 로직을 푸는 것 같은 느낌이 들기도 한다. 이 때문인지 이 문제는 전산학적으로 봤을 때 NP 완전 문제라는 것까지 증명되었다.

그리고 찍기가 필요 없는 명확한 상황일 때 사람이 지뢰를 찾는 절차는 의외로 아주 명료하고 기계적이다.
딱 이 정도 영역이 개봉되고 인접 셀의 지뢰 정보가 이렇게 주어졌을 때, '명백한 해법' 하나만 동원해서라도 컴퓨터가 게임 진행을 충분히 도와 줄 수 있겠다는 생각이 들었다.

그래서, 막간을 이용해 지뢰찾기를 푸는 프로그램을 짜 봤다.
초-중급 수준의 간단한 클래스 설계와 알고리즘 구현이 동원되니 심심풀이 땅콩 코딩용으로 꽤 적절한 거 같다!
'명백한 해법'을 적용할 수 없어서 '찍기'를 해야 할 때, 지뢰가 있을 만한 위치를 가장 유력하게 유추하는 것 정도까지 구현해야 비로소 중급-고급 사이를 넘볼 수 있지 싶다.

대략의 코딩 내역은 이러하다.
지뢰 답을 알고 있는 MineSource 클래스(각 칸마다 지뢰 여부를 실제로 담고 있는 2차원 배열),
그리고 그 MineSource에다가 쿼리를 해 가며 1~8 숫자와 자기가 찾아낸 지뢰 위치 정보만을 알고 있는 MineSolver 클래스를 만들었다.
이들은 다 2차원 배열과 배열의 크기는 공통 정보로 갖고 있으므로 MapData라는 동일 기반 클래스를 설정했다.

MineSource는 특정 위치 x,y에 대한 쿼리가 온 경우, MineSolver에다가 인접 셀들의 지뢰 개수를 써 준다. 인접 셀에 지뢰가 하나도 없다면 여느 지뢰찾기 프로그램이 그러는 것처럼 인접 셀 8개도 한꺼번에 개봉하면서 flood fill을 한다.
곧바로 지뢰를 찍었다면 당연히 곧바로 게임 오버라고 알려 준다. 그리고 요즘 지뢰찾기 게임 구현체들이 그런 것처럼, 첫 턴에서는 절대로 지뢰를 찍는 일이 없게 내부 보정을 하는 것도 이 클래스에서 하는 일이다.

지뢰찾기의 '명백한 해법'은 딱 두 가지이다.

  1. 열리지 않은(지뢰 마크가 있는 놈 포함) 인접 셀의 개수와 자기 숫자가 '같은' 셀은 주변 미개봉 셀이 다 지뢰임이 100% 확실하므로 그것들을 전부 지뢰 마크(깃발)로 표시한다.
  2. 깃발이 꽂힌 주변 셀의 개수와 자기 숫자가 같은 셀의 경우, 지뢰 마크가 없는 나머지 열리지 않은 인접 셀은 지뢰가 아닌 게 100% 확실하다. 따라서 전부 개봉한다.
  3. (위의 명백한 해법만으로 개봉할 만한 셀이 존재하지 않는 건 운이 나쁜 케이스다. 패턴을 기반으로 랜덤 추측을 해야 하는데, 이건 일단 보류.)

텍스트 모드에서 자기 스스로 무작위하게 지뢰밭을 만들고 지뢰찾기를 풀기도 하는 자문자답 프로그램을 만드니, 200줄이 좀 안 되는 코드가 완성되었다.
이 프로그램은 인접 셀에 대해서 뭔가 조건을 만족하는 셀의 개수를 세거나, (getCount) 일괄적으로 동일한 조치를 취하는(doAction) 패턴이 많다.

이걸 그냥 for(j=y-1; j<=y+1; j++) for(i=x-1; i<=x+1; i++)이라는 2중 for문만으로 돌리기에는 i나 j가 boundary 밖인 경우도 고려해야 하고, (i,j)가 (x,y)와 같은 위치인 경우도 피해 가야 하기 때문에 loop 자체가 생각보다 복잡하다.
그러니, 그 loop 자체만 하나만 짜 놓고 loop 안에서 하는 일을 그때 그때 달리 지정하는 것은 템플릿-람다로 깔끔하게 설계했다.

다음은 프로그램의 간단한 실행 결과이다.

after the first turn:
+ + 1 . . . . . .
+ + 1 . 1 1 1 . .
+ + 1 . 1 + 2 1 .
+ + 1 . 1 2 + 1 .
1 1 1 . . 1 + 2 1
. . . . 1 1 + + +
. . . . 1 + + + +
. 1 1 2 2 + + + +
. 1 + + + + + + +

(중간 과정 생략)

picking 7 9
@ @ 1 . . . . . .
2 2 1 . 1 1 1 . .
1 1 1 . 1 @ 2 1 .
1 @ 1 . 1 2 @ 1 .
1 1 1 . . 1 2 2 1
. . . . 1 1 3 @ 2
. . . . 1 @ 3 @ 2
. 1 1 2 2 2 2 1 1
. 1 @ 2 @ 1 . . .
You Won!


이 정도 초보적인 지뢰 찾기 풀이 프로그램은 이미 다 개발되고도 남았으니,
유튜브를 뒤지면 신의 경지 수준의 속도를 자랑하는 지뢰찾기 TAS (매크로 프로그램 내지 역공학을 동원한 게임 스피드런) 동영상들이 나돌고 있다.

여담이다만, 지뢰찾기를 하다가 지뢰를 밟아서 게임 오버가 될 때 본인은 깜짝 깜짝 잘 놀란다. =_= 마치 옛날에 페르시아의 왕자를 하는데 타이밍을 잘못 잡아서 왕자가 쇠톱날(chopper)에 두 동강 나서 죽는 것 같은 그런 느낌이다.

Posted by 사무엘

2013/09/26 08:32 2013/09/26 08:32
, , , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/881

지금으로부터 수십 년 전에는 동네마다 컴퓨터 학원이 있었고, 꼬꼬마가 프로그래밍을 공부하겠다고 하면 으레 GWBASIC부터 시작하곤 했다. 베이직은 16비트 MS-DOS뿐만 아니라 각종 가정용 8비트 컴퓨터에도 특유의 인터프리터 환경이 내장되어 있기도 해서 접하기가 한결 쉬웠다.

그때와는 달리 오늘날의 컴퓨터 교육은 이미 만들어진 소프트웨어들을 활용만 하는 실무에만 치우친 편이다.
지금 컴퓨터 프로그래밍을 처음부터 공부하고 싶다면 무엇부터 시작하는 게 좋을까?
이 질문에 대한 답변은 그 사람이 무슨 프로그램을 작성하고 컴퓨터로 무엇을 하고 싶은지 목적에 따라 크게 달라진다.
이 글은 나의 지극히 좁은 편견만을 반영하고 있으므로, 당연히 프로그래머마다 생각이나 견해가 다를 수 있다.

1. 비전문가/비전공자로서 그냥 최소한의 시간 투자로 개인적인 컴퓨터 활용도만 높이고 싶다면(고급 계산기 + 기초 알고리즘 실습 + 파일 자동 조작 + 매크로/자동화 도구 등)

개인적으로 파이썬을 추천한다. 복잡한 자료형을 다루기가 쉬워서 여타 언어들에 비해 짧은 코드만으로 복잡한 일을 한번에 끝낼 수 있다. 방대한 크기의 파일을 읽어서 내가 원하는 처리를 한 뒤 출력을 뱉어내는 수십 줄 남짓한 프로그램만 짤 줄 알아도 인생이 굉장히 편해질 수 있다.
좀 수학 덕후 기질이 있다면, 함수형 프로그래밍 언어를 건드려 봐도 될 듯.

2. 1보다는 좀 더 나아가서 가성비가 뛰어난 개발 환경에서 최소한의 GUI까지라도 만들어 보고 싶으면

Windows 플랫폼 한정으로 C#급 언어가 가장 좋겠다.

3. 웹브라우저에서 어지간한 애니메이션이나 프레젠테이션을 다 띄우고, 글이나 그림을 계산 결과로서 출력하고 싶으면

HTML + 자바스크립트.
요즘은 HTML이 단순히 화면에 뿌려지는 글과 그림, 하이퍼텍스트 문서일 뿐이라고 생각하는 건 큰 오산이다.
문서에다 서식을 주는 건 이제 CSS라는 방대한 별도의 규격으로 독립해 나가고, HTML은 문서 반 코드 반이다. 실시간으로 내용이 업데이트되고 화면 끝까지 스크롤됐을 때 추가로 컨텐츠를 로딩하고.. 사용자의 조작에 반응하여 그림을 뿌려 주는 등, 예전에는 ActiveX나 하다못해 플래시라도 써야 했을 컨텐츠들이 지금은 저것만으로 다 된다.

웹브라우저가 거의 플랫폼 독립적인 프로그램 구동 플랫폼처럼 바뀌었으니, 이를 활용할 줄 알면 역시 컴퓨터 활용 능력이 크게 향상될 수 있다. 웹 프로그램은 다른 언어나 런타임, IDE 같은 걸 설치할 필요조차 없이, 그냥 메모장에서 코딩 후 웹브라우저에서 곧바로 돌려보면 된다.

4. 맥 OS용 응용 프로그램이나 아이폰 앱을 개발하고 싶다면

Objective C + xcode + COCOA API 등등으로 고고씽이다. 일단 맥북을 장만해야 할 것이고 Windows와는 너무 이질적인 개발 환경 때문에 처음에 고생 많이 할 것이다.

5. 안드로이드 스마트폰용 앱을 개발하고 싶다면

자바 + 이클립스 IDE에 익숙해져야 할 것이다. Java는 요즘 스마트폰 앱 개발용 언어로 입지가 확 되살아난 듯하다. 이게 완전한 웹용 언어도 아니고(자바스크립트는 자바와 전혀 다른 언어임), 자바 애플릿이 플래시/ActiveX를 완전히 대체하는 RIA (rich internet application) 프레임워크로 자리잡은 것도 아니고, 로컬에서는 느리고 성능이 안 좋다 보니 전통적인 기계어 프로그램들에 밀려서.. 예전까지는 위상이 좀 어정쩡했기 때문이다. 로컬에서는 일부 크로스플랫폼 소프트웨어의 GUI(프런트 엔드)를 돌릴 때나 좀 쓰이곤 했다.

6. 끝으로, PC + Windows 환경에서 네이티브 코드 + standalone으로 실행되는 프로그램을 개발하고 싶다면

아래아한글이나 <날개셋> 한글 입력기나 어지간한 온라인 게임과 같은 급의 기계어 실행 파일을 만들고 싶다면..
역시나 재래식 Visual C++이나 최소한 델파이 같은 툴로 가야 한다.
개발 환경, 언어 문법과 기본 라이브러리, Windows API, 그 뒤 개발 분야에 따라 추가적인 라이브러리 공부까지 산 넘어 산이다.

오늘날 프로그램 개발 환경이 결국 로컬 + 웹 + 앱이라는 세 양상으로 구분된다고 예전에 글을 쓴 적이 있는데.. 그것과도 관계가 있다.
프로그래밍, 더 나아가 소프트웨어 개발에 관심이 있는 분이라면 이런 아이템들을 참고하면 되겠다.
그런데 정작 이런 글을 쓴 본인은 6만 빼고 나머지 분야는 여전히 너무 모른다는 게 함정..ㅎㅎ

Posted by 사무엘

2013/09/17 08:37 2013/09/17 08:37
,
Response
No Trackback , 13 Comments
RSS :
http://moogi.new21.org/tc/rss/response/878

수학에서 행렬은 굉장히 흥미로운 물건이다.
행렬끼리의 덧셈이나 행렬의 상수배는 어려울 게 없는 쉬운 연산이지만, 행렬끼리의 곱셈은 그렇지 않다. 행렬 A와 B사이의 곱셈은 A의 가로 크기와 B의 세로 크기가 같아야 정의되며, 새로 생기는 행렬의 크기(dimension)는 반대로 B의 가로 크기와 A의 세로 크기로 결정된다.

이런 특성상 행렬의 크기는 세로, 즉 row부터 먼저 써 주는 게 직관적이다. 세로 x줄 가로 y줄짜리 x,y 행렬과 y,z 행렬의 곱은 x,z 크기가 된다고 표기가 가능하기 때문이다.

또한, 앞에 있는 행렬과 뒤에 있는 행렬이 원소가 서로 연산되는 방향이 다르기 때문에 행렬의 곱셈은 교환 법칙이 성립하지 않는다. A×B가 일반적으로 B×A와 같지 않다는 뜻. 그러나 결합 법칙은 성립한다. (A×B)×C와 A×(B×C)는 동일하므로, 같은 방향만 유지하면 아무 순서로나 행렬을 곱해 줘도 된다.

그래서 이것과 관련하여 흥미로운 문제가 하나 있다.
크기가 들쭉날쭉 다르지만 순서대로 곱셈은 가능한(= 인접한 행렬끼리는 앞 행렬의 가로 크기와 뒤 행렬의 세로 크기가 일치) N개의 행렬들이 있다. 우리는 이들을 모두 최소의 계산량만으로 곱하고 싶다.

역행렬이나 행렬식 값을 구하는 비용에 비할 바는 아니겠지만 행렬의 곱셈은 꽤 비싼 연산이다. 일반적으로 x,y 크기와 y,z 크기의 행렬을 곱하는 데는 원소들간에 x*y*z회의 곱셈이 필요하다. n 크기의 정사각행렬의 경우 이는 n^3으로 귀착된다. (뭐, 분할 정복법을 활용하여 n^2.x승으로 줄이는 복잡한 알고리즘이 있긴 하지만 이것은 초기 준비 오버헤드가 굉장히 크기 때문에 행렬이 무진장 클 때에나 의미가 있다.)

예를 들어 A는 4*2 크기, B는 2*3 크기, C는 3*1크기의 행렬/벡터라고 치자.
이것을 A*B*C 순으로 진짜 순서대로만 곱하면 A*B를 곱하는 데 4*2*3=24회의 곱셈이 동원되고, 그 결과물인 4*3 행렬을 C와 곱하느라 12회의 곱셈이 필요해서 계산량은 총 36이 된다.

사용자 삽입 이미지

그러나 B*C부터 먼저 곱한 뒤 A를 거기에다 곱하면 열수가 적은 C 덕분에 B*C는 겨우 6회 만으로 끝나고, 거기에다 4*2*1=8회의 곱셈이 추가되어 총 14의 계산량만으로 A*B*C를 구할 수 있다. 답은 결국 똑같은데도 (AB)C보다 A(BC)가 훨씬 더 나은 전략인 것이다.

신기하지 않은가? 그래서 이런 configuration을 일반화하여 {4, 2, 3, 1}이라고 표현하고, 더 나아가 n>=3인 n개의 자연수라고 치자.
이 입력에 대해서 최소 곱셈 횟수와 실제 곱셈 순서를 구하는 것이 문제이다.

정올 공부를 한 분이라면 아시겠지만, 이것은 다이나믹 프로그래밍, 혹은 동적 계획법이라는 알고리즘 설계 방법론을 학습하면서 예시로 다뤄지는 아주 기본 문제이다. 다이나믹 프로그래밍은 다음과 같은 경우에 유용하다.

  • 전체 구간에 대한 최적해가 부분 구간의 최적해에다가 추가 연산을 함으로써 구하는 게 가능하다.
  • 그리고 한번 답을 구해 놓은 부분 구간의 최적해는 더 바뀌지 않는다는 게 보장된다.

이 행렬의 곱셈 문제에서 가장 작은 구간은 3이며, 이때의 답은 그냥 두 말할 나위 없이 세 정수의 곱이다.
그리고 전체 구간 [1..n]에 대해서 최적해는 바로..

  • 1을 [2..n]과 곱했을 때의 계산량 (맨 앞의 행렬과 나머지)
  • [1..n-1] 과 n을 곱했을 때의 계산량 (앞의 행렬들과 맨 뒤의 행렬)

중 더 작은 놈이라고 간주하면 된다.

그럼 [2..n]과 [1..n-1]은? 각 구간에 대해서 또 동일한 해법을 적용하여 재귀적으로 구간을 계속 쪼개 나가는 것이다. 언제까지? 구간의 길이가 3이 될 때까지 말이다.
이렇듯, 다이나믹 프로그래밍은 재귀성을 띠고 있다. 이것은 수학적으로는 점화식으로 표현되며, 코드로는...

const int dat[]={4,2,3,1,2,6,5,8,3,2}; //배열

int GetMin(int f, int t)
{
    int i=t-f, j;
    if(i<3) return 0; //should not reach here
    else if(i==3) return dat[f]*dat[f+1]*dat[f+2]; //obvious case
    else {
        //사실은 i가 3인 경우도 이 조건의 특수한 케이스라고 간주할 수 있다.
        //단지 GetMin값이 0이고, t-2와 f+1이 동일한 값이 될 뿐이다.
        i=GetMin(f,t-1) + dat[f]*dat[t-2]*dat[t-1]; //(A*B)*C
        j=GetMin(f+1,t) + dat[f]*dat[f+1]*dat[t-1]; //A*(B*C)
        return i<j ? i:j;
    }
}

int answer = GetMin(0, 10);

과연 이렇게 하면 답이 구해질까?
프로그램을 돌려 보면, 10개의 정수로 표현된 9개의 서로 다른 크기의 행렬들의 곱은..
146회의 곱셈만으로 계산이 가능하다고 나온다.

구체적인 계산 순서는 이러하다.

4 (2 (3 (((((1 2 6) 5) 8) 3) 2)))

이 경우, 각 단계별 계산 순서는 다음과 같이 되기 때문에,

x y z x*y*z
1 2 6 12
1 6 5 30
1 5 8 40
1 8 3 24
1 3 2 6
3 1 2 6
2 3 2 12
4 2 2 16

곱을 전부 합하면 진짜로 146이 맞다!
참고로, 이런 전략을 쓰지 않고 진짜 FM대로 앞에서부터 뒤로 행렬을 순서대로만 곱하면 계산량은 최적해의 세 배를 넘는 492에 달한다.
이것이 바로 알고리즘이 만들어 내는 차이이다.

다이나믹 프로그래밍에는 반드시 수반되어야 하는 작업이 있다. 바로 예전에 구했던 구간 계산값들을 배열에다 저장해 두는 것이다. 그렇게 하지 않으면, 마치 피보나치 수열을 f(x) = f(x-1)+f(x-2)라고만 구현하는 것만큼이나 계산량이 n이 커짐에 따라 기하급수적으로 커지게 된다. 그것도 예전에 한번 했던 똑같은 계산을 매번 반복하느라 말이다.
그래서 이 방법을 사용한 알고리즘은 대체로 시간 복잡도와 공간 복잡도가 모두 O(n^2)이 된다. 시간 복잡도가 지수함수에서 그래도 다항함수로 바뀐다.

구간별로 최적해 자체뿐만이 아니라 구간 분할을 어떻게 했는지에 대한 정보도 따로 보관해 놓으면 아까와 같은 구체적인 계산 순서도 그 정보를 추적함으로써 구할 수 있다.

정올에서 다이나믹 프로그래밍의 중요성은.. 두 말하면 잔소리이다.
본인은 20세기에 정올 공부를 한 세대인지라 그 시절의 문제밖에 기억을 못 한다만..

1997년 한국 정보 올림피아드의 고등부 3번인 벽장 문제는 최적해를 구하고자 할 경우 공간과 시간 복잡도가 O(n^3)인 다이나믹 프로그래밍으로 풀 수 있다. 이 때문에, 16비트 환경임을 감안하더라도 이 문제는 입력의 범위가 작다. 벽장의 개수와 벽장 사용 순서가 최대 겨우 20까지밖에 안 올라가는 소규모이다. 실용적인 상황에서는 이런 부류의 시뮬레이션 문제는 휴리스틱이 동원되어야 할 것이다.

이 외에,

1999년 고등부 1번 검은 점 흰 점 연결,
2000년 고등부 1번 수열 축소

도 다이나믹으로 푸는 문제이다.
국제 정보 올림피아드의 기출 문제 중에는
10회(1998)의 둘째 날 마지막 문제인 폴리곤 게임,
11회(1999)의 첫째 날 첫 문제인 꽃 진열이 기억에 남는다. 특히 꽃 진열은 상당히 기초적인 다이나믹 프로그래밍 문제로, <날개셋> 타자연습의 문장 정확도 측정도 이와 거의 같은 발상의 알고리즘을 사용하고 있다.

난 이 바닥은 손 놓은 지가 너무 오래 돼서 기억이 가물가물하다.
정보 올림피아드에서 경시와 공모는 마치 과학과 공학, 어학과 문학의 차이와 비슷한 것 같다.

Posted by 사무엘

2013/08/14 08:34 2013/08/14 08:34
, ,
Response
No Trackback , 8 Comments
RSS :
http://moogi.new21.org/tc/rss/response/866

« Previous : 1 : 2 : 3 : 4 : Next »

블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2019/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

Site Stats

Total hits:
1293641
Today:
292
Yesterday:
499