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

2019/07/06 08:33 2019/07/06 08:33
, , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1637

Trackback URL : http://moogi.new21.org/tc/trackback/1637

Leave a comment

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

2017/03/24 19:25 2017/03/24 19:25
, , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1342

Trackback URL : http://moogi.new21.org/tc/trackback/1342

Leave a comment

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

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

Trackback URL : http://moogi.new21.org/tc/trackback/1181

Comments List

  1. Lyn 2016/01/12 21:48 # M/D Reply Permalink

    전 Genius oriented algorism 을 사용합니다.

    1. 사무엘 2016/01/13 08:08 # M/D Permalink

      오잉, 그건 무슨 분야의 어떤 알고리즘인가요??

    2. Lyn 2016/01/17 17:36 # M/D Permalink

      모든분야에 다 적용되는 알고리즘인데... 천재들이 만들어둔걸 그냥 갖다쓰는 방법입니다.

    3. 사무엘 2016/01/18 09:20 # M/D Permalink

      아아.. 제일 확실한 방법이군요. ㅠㅠ ^^

    4. Lyn 2016/01/31 10:23 # M/D Permalink

      파인만 알고리즘에 맞먹습니다.

  2. 박한철 2016/01/14 03:12 # M/D Reply Permalink

    재밌는 글 잘 보았습니다. 이런 게 수학이죠. P!=NP 는 과연 풀릴 날이 올까요 -_-

    1. 사무엘 2016/01/14 09:35 # M/D Permalink

      알고리즘 서적들이 보통은 분할 정복, 다이나믹 같은 방법론별로.. 혹은 정렬, 그래프, 문자열 같은 주제별로 알고리즘을 분류하는 편이죠. 그런데 최적화 양상으로 분류하면 저렇게 세 그룹으로 나뉜다 싶은 생각이 개인적으로 들어서 정리해 봤습니다.
      그 까마득한 옛날에 저런 걸 30대 나이 때 벌써 P와 NP라는 걸 생각해 내고 떡밥을 던지다니~ 스티븐 쿡 아저씨의 위대함을 실감합니다. ㅜ.ㅜ

  3. 박한철 2016/01/14 14:56 # M/D Reply Permalink

    저는 수학을 공부하는 입장인데 부끄럽게도 스티븐 쿡이라는 이름을 이제사 처음 들어 봤습니다 ㅠㅠ 수학과 계산과학이 겹치는 부분이 많은데 커리큘럼이 나눠져 있어서... 주로 조합수학combinatorics 쪽에서 많이 겹치는 것 같더군요.

    1. 사무엘 2016/01/15 08:55 # M/D Permalink

      아유 수학이 원래 분야가 왕창 넓어서 주 연구 분야가 아니면 교수라도 잘 모르지 않나요? ^^
      수학을 전문으로 공부하는 분들 개인적으로 참 대단하고 부럽습니다. 저도 그냥 이것저것 주워 들었을 뿐이죠. ㅎㅎ

Leave a comment

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

2014/12/28 08:39 2014/12/28 08:39
, , ,
Response
No Trackback , 9 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1044

Trackback URL : http://moogi.new21.org/tc/trackback/1044

Comments List

  1. Lyn 2014/12/29 00:06 # M/D Reply Permalink

    함수형 언어의 최적화/실행 오버헤드는 굉장히 간단한 결론이 나 버리죠 ㅎㅎ

    최종적으로 실행되야하는 CPU의 코드가 전혀 함수형이 아니라는것 (...)

  2. 허국현 2014/12/29 07:05 # M/D Reply Permalink

    Joel on Sofftware 읽을 때, 분산 처리에 사용하는 Map Reduce라는 기술을 알기 위해서는 함수형 언어를 알아야 한다는 이야기를 하던 것이 기억나네요.

  3. 사무엘 2014/12/29 08:03 # M/D Reply Permalink

    Lyn: 그렇지요. 수학이야 무한을 너무나 쉽게 논하면서 '답이 존재한다, 혹은 불가능하다' 자체만이 중요할 뿐 그 답을 구하는 방식이야 별로 중요하지 않지만.. 답을 실제로 구해야 하는 현실에서 늘 그렇게 고자세로만 살 수는 없으니.. ㅋㅋㅋ
    어셈블리어에 함수형 패러다임 같은 걸 기대할 수는 없습니다.

    허국현: 코딩을 할 때, 뭔가 지저분한 how를 따질 일 없이 프로그래머로서의 사고를 유연하게 단련하는 데는 함수형 패러다임이 도움이 되긴 합니다.

  4. 김재주 2014/12/29 13:17 # M/D Reply Permalink

    대신 함수형 언어로 작성된 프로그램은 보통 표현력이 더 뛰어나죠. 함수형 언어로 3~4줄 작성된 프로그램을 절차형 프로그래밍 언어의 대표격인 C언어로 고치면 10줄 이상이 나오는 경우가 허다하고요. 이는 달리 말하면 숙달된 한명의 함수형 프로그래머가 다른 프로그래머의 서너배 생산성을 낼 수 있다는 의미도 됩니다. 그리고 보통 함수형 언어는 타입 체킹이나 제약조건이 깐깐하다보니 웬만한 오류는 작성 단계에서 컴파일러에게 걸러진다는 걸 생각해 보면, 극단적으로 최적화가 필요한 분야가 아니라면야 해볼만 한 장사죠. 어쨌든 똑똑한 컴파일러만 있다면 자바보단 빠른 코드를 만들거든요.

    그런데 이런 장점에도 불구하고 함수형 언어가 잘 안 팔리는 이유는... 제 생각이지만, 한명의 프로그래머가 그만두면 서너명이 그만둔 것과 같은 타격을 입기 때문(?)일지도...

    1. Lyn 2014/12/29 14:08 # M/D Permalink

      전 별로 동감이 안가는데...

      함수형 언어는 한줄한줄에 많은 내용이 들어 있는 만큼, 한줄을 짤때 비교적 생각할게 많아져서 시간이 더걸려요 ...

      애초에 개발 시간에 코드 작성 시간은 얼마 포함되어 있지도 않고.
      코드가 짧아진다고 생산성이 몇배씩 올라가면 J언어같은 극단적인 축약형 언어가 생산성이 무지 높아야겠지만 그렇지 않지요

    2. 사무엘 2014/12/29 21:30 # M/D Permalink

      깔끔하고 간결한 것 하나는 부러운 점인 것 인정합니다.
      하지만 Lyn 님 말씀도 일리가 있는 것이, 1/3 내지 1/2 분량의 코드만 짜면 된다고 해서 그 코드를 짜는 데 걸리는 시간도 1/3 내지 1/2로 줄어들지는(그만큼 생산성 버프) 않을 것 같네요. ^^;;

  5. 김재주 2014/12/29 22:07 # M/D Reply Permalink

    저도 C-like 언어가 편한 입장이지만, 함수형 언어는 한 함수의 기능을 최소화된 함수 여러개로 쪼개서 짜맞추는 식이 되어야 하기 때문에 모듈화가 잘 되는 편입니다. 생각하는 방식 자체를 바꿔야 하지만 익숙한 사람에게는 더 생산성이 높죠. 중복되는 코드가 적어지는 건 덤이고요.

    뭐 함수의 크기를 최소로 하고 중복 코드를 제거하는 건 절차형 언어에서도 적극 권장되는 프로그래밍 습관이긴 하지만요. 익숙함 문제라고 봅니다.

  6. 김 진 2015/01/02 03:04 # M/D Reply Permalink

    앨론조 처치를 보고 문득 생각이 나서 찾아봤습니다: http://www.surnamedb.com/Surname/Church 목회자의 후손일 수도 있고, 단순히 교회 근처에 살던 사람의 후손일 수도 있다고 하네요

    1. 사무엘 2015/01/02 11:24 # M/D Permalink

      마치 '스미스'라는 이름이 자신이 대장장이 집안이거나 집 근처에 대장간이 있어서 붙여진 것과 비슷한 맥락이겠네요. 물론 지금은 아무 연결고리도 찾을 수 없는 엄청 먼 옛날에 그랬다는 거겠지만..
      그걸 직접 찾아 볼 생각을 하셨다니.. 고맙습니다. 새해 복 많이 받으세요. ^^;;

Leave a comment

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

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

Trackback URL : http://moogi.new21.org/tc/trackback/1025

Leave a comment

지뢰찾기 연구

요즘 팔자에도 없던 지뢰찾기에 살짝 재미가 붙었다.
본인은 비슷한 학력· 경력으로 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

Trackback URL : http://moogi.new21.org/tc/trackback/881

Comments List

  1. 김진 2013/10/06 08:11 # M/D Reply Permalink

    지뢰의 위치를 조합하는 프로그램을 작성 중에 있습니다.

    " 인접 셀에 대한 조건을 만족하는 셀의 개수를 세거나, (getCount) 일괄적으로 동일한 조치를 취하는(doAction) 패턴" 에 관한 조금의 설명을 해주실 수 있는지요?
    아직 많이 서툴러..흠흠;;;

    1. 사무엘 2013/10/06 14:30 # M/D Permalink

      오오, 반갑네요. ^^
      getCount는 이 셀 주변(8개)에 있는 이미 꽂힌 깃발의 개수 세기, 열리지 않은 뚜껑의 개수 세기 등을 통틀어 일컫는 함수이구요,
      doAction은 이 셀 주변에 있는 모든 뚜껑을 열기, 모든 열리지 않은 뚜껑에다 깃발을 꽂기 같은 동작을 총괄합니다.
      그냥 코딩 설계 기법이지 알고리즘은 아니니 어려울 건 없습니다. (지금은 밖에 있어서 일단 간단히 기억만으로 말씀드립니다.)

      아무 단서 없이 열리지 않은 셀들이 일렬로 쭉 늘어선 채 1 1 2 2 2 1 이런 식으로 있을 때 어느 뚜껑부터 까야 할지 재구성하는 게 참 어렵더군요. 제가 가끔 지는 게 그런 상황에서 뚜껑을 잘못 열어서 집니다. ^^

  2. 김진 2013/10/06 23:35 # M/D Reply Permalink

    네. 감사합니다. 저는 사실 시름이 깊어지는데요..
    c를 사용하여 콘솔로 작성하고 있습니다.

    문제상황은 다음과 같습니다.
    1)랜덤으로 지뢰를 발생시켜 자신을 포함한 주변9개의 셀에 포함된 지뢰의 숫자를 배열로 출력하시오
    2) 출력된 배열로 다시 지뢰의 위치를 짐작하여 출력해보시오.

    1)은 크게 어렵지 않게 휘리릭 왔는데.. 2)번에서 막혔습니다.
    약간의 힌트만 주시면 마무리할 수 있을 것 같은데...다시 한번 조언을 구할 수 있을지요??^^

    1. 사무엘 2013/10/07 21:01 # M/D Permalink

      2번이 결국은 역으로 지뢰찾기를 푼다는 얘기잖아요 그죠?
      저도 '휘리릭' 끝낼 수 있는 수준밖에 진척된 게 없답니다. ㅎㅎ

      명백한 솔루션이 없는 경우라면..

      2 2 3 1
      a b c d e

      a+b = 2
      a+b+c = 2
      b+c+d = 3
      c+d+e = 1

      a+b+c+d+e = 현재 남은 지뢰의 총 개수
      단, a~e는 모두 either 0 or 1

      결국 이런 논리식인지 방정식인지 모를 식들로부터 a~e 값을 유추해야 하고,
      가능한 모든 가짓수들 중에서 어느 경우에도 1일 가능성이 가장 높은 칸을 찍어야겠죠?

      문제는 게임 보드로부터 저 식을 도출해서 input/output 포맷을 전환하는 코드를 구현하는 것부터가 보통일이 아닐 듯합니다. orz
      지뢰찾기를 연구해 보셨다면 이미 다 찾아 보셨겠지만, 이런 걸 계산해 주는 Minesweeper clone 같은 프로그램도 이미 다 있긴 합니다만 그런 프로그램들은 소스 공개는 아니네요.

Leave a comment

수학에서 행렬은 굉장히 흥미로운 물건이다.
행렬끼리의 덧셈이나 행렬의 상수배는 어려울 게 없는 쉬운 연산이지만, 행렬끼리의 곱셈은 그렇지 않다. 행렬 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

Trackback URL : http://moogi.new21.org/tc/trackback/866

Comments List

  1. 세벌 2013/08/16 07:43 # M/D Reply Permalink

    저는 수학 좋아 수학과 나오고 그랬는데... 세월이 흐르면서 요즘은 수학과 거리가 먼 삶을 살고 있네요. 용묵님은 꾸준히 수학공부 하시나 봐요.

    1. 사무엘 2013/08/17 09:29 # M/D Permalink

      뭐.. 꾸준히는 아니고 옛날에 공부하다가 손 놨던 것을 복습만 한 거지요. ㅎ

  2. 나그네 2014/12/26 16:01 # M/D Reply Permalink

    4,5,1,3,2,6 일때 오답이 나오는 것 같습니다..

    1. 사무엘 2014/12/26 17:21 # M/D Permalink

      [[4, [5, [1, 3, 2]]], 6] 이렇게 104이지 않나요? 위의 함수를 그대로 돌려도 값은 정확하게 나오는걸요.

  3. 나그네 2014/12/26 18:10 # M/D Reply Permalink

    (((4 5)*(5 1))*((1 3)*(3 2)))*(2 6) 순으로 곱하면 82 나오네요.

    1. 사무엘 2014/12/26 23:52 # M/D Permalink

      아... 저 점화식이 커버하지 않는 순서대로 곱할 수도 있군요. 처음 알았습니다..!
      발상의 전환이 필요한 듯합니다. 알려 주셔서 고맙습니다~! ^^

    2. 사무엘 2014/12/28 00:33 # M/D Permalink

      ((4 5)*(5 1))* (((1 3)*(3 2))*(2 6))
      괄호 순서를 이렇게 바꾸면 82보다도 더 작은 62가 최적해가 되네요~!

      = (4*1)[20] *( (1*2)[6] *(2*6) )
      = (4*1)[20] *(1*6)[6 + 12 = 18]
      = (4*6)[20 + 18 + 24]
      = 62

      104에서 62로.. 정말 드라마틱합니다.
      프로그램을 다시 짰더니 너무 작은 값이 나와서 버그를 의심했습니다만... 프로그램이 구한 답이 맞았습니다.

  4. 나그네2 2014/12/30 12:12 # M/D Reply Permalink

    네 저도 많이 배우고 갑니다. 감사합니다..

Leave a comment

한자어로 '원'이라고 부르는 동그라미라는 도형은 시각적으로나 수학적으로나 아주 신기한 도형이다.
둥글다는 게 무슨 의미인지 기계가 계산으로 표현할 수 있을 정도로 엄밀하게 정의하자면 결국 '어떤 점에서 거리가 같은 점들의 집합'이라는 정의가 등장하게 되고, n차원 직교 좌표에서 거리라는 건 결국 차원을 구성하는 각 축의 거리들의 제곱의 합의 제곱근이라고 정의된다.

원의 지름과 원의 둘레의 비율은 그 이름도 유명한 '파이'이며, 3.141592... 로 시작하는 이 값은 무리수인 동시에 초월수라는 것도 상식이다.

그런데 이 원을 정사각형 격자 모양의 래스터 그래픽 장치에서 어떻게 하면 효율적으로 그릴 수 있을까? 그런 물건의 내부엔 컴퍼스 같은 직관적인 도구가 없는데 말이다.
중심이 x, y이고 반지름이 r인 원을 구성하는 좌표들을 어떤 계산을 통해 얻어 올 수 있을까?
원점이 중심인 원의 방정식은 x^2+y^2=r^2. 따라서 y=sqrt(r^2-x^2) 방정식을 이용하면 사분원 내지 반원을 구성하는 점을 구할 수 있다. 그리고 이 값을 바탕으로 나머지 방향의 점을 그리면 될 것이다.

#include <math.h>
template<typename T>
void Draw_Circle(int x, int y, int r, T f)
{
    double R_2 = r*r;
    for(int i=0;i<r;i++) {
        int v = (int)(sqrt( R_2 - i*i )+0.5);
        f(x-i, y-v); f(x-i, y+v);
        f(x+i, y-v); f(x+i, y+v);
    }
}

for문 자체는 0부터 r까지 사분원의 x좌표만 돌고, 이를 바탕으로 점을 찍는 함수 f를 4개 방향으로 모두 호출한다.
r의 제곱 값은 한 번만 계산하면 되므로 for문 밖에서 별도로 선언해 주는 센스도.
소숫점은 버림이 아니라 반올림이 되도록 0.5를 더한 뒤에 int로 캐스팅하는 게 좋다. 그래야 당장 그려지는 원도 90*n도 부근이 더 탱탱하고 보기 좋아진다.

함수의 사용은 MFC 기준으로 이런 식으로 하면 된다. 함수 안에서 또 다른 함수를 내부적으로 호출할 때 함수 포인터보다 람다가 참 깔끔하긴 하다. (너무 남발한 게 꼬이면 code bloat은 피할 수 없겠지만)

CPaintDC dc(this);
auto x = [&](int x,int y) { dc.SetPixel(x,y,0); };
Draw_Circle(220,220, 200,  x);
Draw_Circle(420,330, 160,  x);

사용자 삽입 이미지

그런데 아뿔싸, 역시 기울기가 1보다 더 커지는 곳에는 점이 듬성듬성 떨어져 있게 된다.
이 틈을 점 찍기가 아니라 선 그리기 같은 다른 함수로 메운다는 건 있을 수 없는 일이고..
결국, 우리의 원 그리기 알고리즘은 언제나 기울기가 1보다 작은 구간에서만 동작하게 loop 구조를 바꿀 필요가 있다.
우리는 원을 4등분했는데, 그렇게 4등분된 조각도 한쪽 끝과 맞은편 끝이 완벽하게 대칭으로 이들을 동시에 그려 보자.

가령, 1사분면에서는 x좌표를 1씩 증가시키면서 r로 근접하고(위의 코드에서 i) y좌표는 r이다가 점점 0으로 작아지는데(위의 코드에서 v),
이와 동시에 반대편에서는 y좌표를 1씩 증가시키면서 r로 근접하고, x좌표는 r에서 0으로 근접시키도록 점을 같이 그리는 것이다.
이제 loop는 변수 i의 값이 r에 도달한 지점에서 끝나는 게 아니라 v와 값이 같아지는 지점에서 끝나면 된다. (정확히는 sqrt(2)*r/2 지점이 됨)

{
    double R_2 = r*r;
    for(int i=0; ;i++) {
        int v = (int)(sqrt( R_2 - i*i )+0.5);
        f(x-i, y-v); f(x-v, y-i);
        f(x-i, y+v); f(x-v, y+i);

        f(x+i, y-v); f(x+v, y-i);
        f(x+i, y+v); f(x+v, y+i);
        if(i>v) break;
    }
}

사용자 삽입 이미지
와, 이로써 굉장히 찰진 모양의 원이 그려졌다. 한 번 루프를 돌 때마다 점이 8개가 그려지는 것이다.
그러나 이런 원 하나 그리는데 부동소숫점에, 곱셈에, 심지어 제곱근까지 꽤 부담스러운 연산이 많이 들어갔다.
이걸 좀 줄일 수는 없을까?

...
    int R_2 = r*r;
    int v = r;
    for(int i=0; ;i++) {
        if(i*i + v*v > R_2) --v;
...

loop의 앞부분을 이렇게 고쳐 보자.
x축에 속하는 i의 값이 1증가할 때마다 y축에 속하는 v의 값은 그대로 유지되거나 1 감소하거나 둘 중 한 변화만을 겪을 것이다.
i가 증가함에 따라 원점에서 i, v까지의 거리가 R보다 확 커지게 됐다면, 이 궤적은 원의 범위를 벗어나는 것이므로 y축에 속하는 v를 1 줄여 준다.

실질적으로 행해지는 연산을 이렇게 최적화해 주면 최소한 부동소숫점과 제곱근 연산은 없어진다.
그러나 최적화의 여지는 그래도 여전히 남아 있다. 저 꼴도 보기 싫은 곱셈을 없애려면 어떡하면 좋을까?

방법이 있다.
결국, i*i는 0, 1, 4, 9, 16 ...의 순열을 생성해 낼 텐데, 얘는 덧셈을 두 번 하는 걸로 대체할 수 있다. 한 번 덧셈을 한 뒤엔 증가치가 2씩 늘어나니까 말이다(1과 4의 차는 3, 4와 9의 차는 5, 9와 16의 차는 7). x^2의 도함수가 괜히 2*x가 아니다.

그리고 v는 초기값이 아예 R_2와 같으니 약분이 가능하다. 그 뒤에 v의 값이 줄어들면서 차이만이 발생할 뿐이다. 그런데 얼마를 빼 줘야 할까?
x^2가 (x-1)^2로 바뀌었을 때 감소하는 값은 잘 알다시피 2*x-1이다. 따라서 이 값만 초기에 계산해 놓은 뒤, v가 1 감소하게 됐을 때 가상의 v_square은 그만치 빼 주고, 그 델타값 자체도 2 감소시키면 된다.

...
    int v = r, i_square = 0, i_delta = 1;
    int v_delta=2*r-1, v_square_delta = 0;
    for(int i=0; ;i++) {
        if(i_square + v_square_delta > 0) {
            --v; v_square_delta-=v_delta, v_delta-=2;
        }

... //점 여덟 군데를 찍어 준 뒤

        if(i>v) break;
        else i_square+=i_delta, i_delta+=2;
    }

이로써 그 부드러운 원을 오로지 정수의 덧셈만으로, 그리고 곱셈이라고는 loop 돌기 전에 *2 단 한 번밖에 안 하는 깔끔한 원 그리기 알고리즘이 완성되었다. 놀랍지 않은가? 게다가 고정적인 두 배 연산은 잘 알다시피 bit shift로도 수행 가능한 아주 가벼운 연산이기도 하고 말이다.

GWBASIC, Windows GDI API, 옛날 볼랜드 BGI 등 모든 그래픽 라이브러리에 들어있는 원 그리기 함수는 기본적으로 이 알고리즘을 이용하여 원을 그린다. 각종 알고리즘 서적에 예제로 실려 있는 소스들도 세부적인 변수 활용이나 계수 계산에 차이가 있을지언정 기본적인 아이디어는 동일하다.

사실, 이건 거의 대학교 학부 수준이고 정보 올림피아드 공부라도 했다면 중· 고등학교 시절에라도 접했을 기초적인 내용이다. 진짜 어려운 건 이걸 응용하여 안티앨리어싱을 적용한다거나 타원을 그리거나, 아예 부채꼴 내지 회전된 원을 그리는 알고리즘이다.

단, Windows GDI가 그리는 원은 왠지 좀 엉성하고 덜 예쁜 것 같다. 비교를 할 때 반올림 보정을 안 하는지 경계가 아주 약간 덜 통통하며, 특히 기울기가 1(45도)에 가까워지는 지점에 점의 배치가 지저분하다.
차이를 보이기 위해 움짤을 만들어 보았다. 파란색 원은 GDI 함수로 그린 것이고, 빨간색 원은 우리가 작성한 함수로 그린 것이다.

사용자 삽입 이미지

Posted by 사무엘

2013/07/28 08:27 2013/07/28 08:27
, , ,
Response
No Trackback , 6 Comments
RSS :
http://moogi.new21.org/tc/rss/response/860

Trackback URL : http://moogi.new21.org/tc/trackback/860

Comments List

  1. kimtaeho 2014/01/14 12:27 # M/D Reply Permalink

    예전에 세벌식 익힌다고 깝치다가 ㅎㅎ 김용묵님을 알게 되었는데 수년이 지나서 검색하다 발견하게 되었네요.
    세벌식은 지금도 사용하고 있는데 결국 두벌식도 대세때문에 안쓸려니 너무 불편해서
    혼합해서 쓰고 있습니다용. 집에서는 두벌, 회사에서는 세벌...
    제품이 아무리 성능이 좋아도 호환성도 무시할 수가 없나봅니다.
    가는 곳마다 세벌로 바꿔서 타자를 치기란 참 불편하니.

    어쨌든 8비트 뇌가 조금이라도 개발이 될려나 싶어 세벌식을 배웠건만
    아무런 도움이 안된다는 사실을 깨달았으며,
    그때도 느꼈지만 용묵님 뇌의 dna는 나랑은 참 다르구나를 ....

    이제는 펌웨어쪽 엔지니어가 되었는데 기초가 후달리니 --; OTL......이라는...
    그저 늦더라도 기초를 확실히 이해하는 수밖에 없군요.

    저를 잘 기억하시지는 못하겠지만 저도 용묵님의 이름이 특이하여
    용묵님의 개성이 컴터를 통해서도 느껴저서 그분이 그분이구나를 알았습니다.
    부단히 정진하는 모습에 많이 자극 받고 배워갑니다.

    잡설이 길었네요. 그러머 나중에 또 들릴께요. 휘리릿....

    1. 사무엘 2014/01/14 17:12 # M/D Permalink

      반갑습니다.
      직장이라고 해서 한 컴퓨터를 여러 사람이 같이 쓰느라 세벌식 쓰기가 불편한 건 아닐 것 같은데 그렇게 하셔야 할 불가피한 이유가 있나 궁금하네요.
      저는 튀는 마이너 분야 하나를 오래 깊게 파서 그거 하나로 먹고 살 뿐이지, 컴퓨터 분야의 진정한 괴수 덕후들에 비할 바는 못 됩니다. 저도 좀 머리가 빨리 잘 돌아갔으면 하는 바람이 있습니다. ㅜ.ㅜ
      발자취 남겨 주셔서 고맙습니다. 앞으로 종종 뵈었으면 합니다. ^^;;

  2. kth 2014/01/15 12:43 # M/D Reply Permalink

    참 묵님.
    혹시 정규식에 대해서 아시나요?
    프로그램 달인이니 ㅎㅎ 아실 것 같은데.
    전 얼마전에 조금 배웠는데..


    추신: 세벌만 꼭 쓸 필요는 없는 것 같아요.
    두벌을 쓸 상황이면 두벌을 ,
    세벌을 쓸 상황이면 세벌을
    ㅎㅎ 그게 자유로움이 아닐까...

    세벌이 손가락이 자연스럽다는 느낌은 드는데,
    게으름의 극치로 세벌 환경을 설정하고, 나중에 다시
    바꾸는 것도 귀찮아서..쿨럭...

    또 하나는 안타깝게도 전 오타쿠의 수준에 못 들어가지만 ㅠ.ㅠ, 들어가고 싶은데 그런 기질이 없네요. 젠장.
    어쨌든 오타쿠가 부럽습니다.

    1. 사무엘 2014/01/15 18:59 # M/D Permalink

      1. 정규 표현식이라 하면 주어진 조건을 만족하는 텍스트 패턴을 지정하는 규격 말인가요?
      저는 [] - ^ $ 같은 아주 간단한 것밖에 모르고 즐겨 사용할 정도로 능숙하지도 않습니다.

      2. 저도 두벌식과 세벌식을 다 아주 능숙하게 다룹니다.
      하지만 그래도 세벌식이 타속이 더 빠르고, 단순히 속도를 넘어서 손이 편합니다.
      조금만 오래 타자를 칠 일이 있으면, 두벌식을 칠 줄 알고 또 남의 컴퓨터라 해도 일부러 세벌식으로 잠시 전환을 해서 세벌식으로 친답니다. 그만큼 차이가 크거든요.

      벌식 전환이 걸린다면 제가 개발한 파워업을 사용하거나, 날개셋 입력기에서 복벌식을 사용해 보는 것도 한 방법일 것 같습니다.

      3. 철도를 아는 것이 모든 오타쿠 기질의 기초이죠. 이것부터 시작해 보시는 게 어떨까요? ㅋㅋㅋㅋ

  3. 비밀방문자 2014/01/27 19:07 # M/D Reply Permalink

    관리자만 볼 수 있는 댓글입니다.

    1. 사무엘 2014/01/28 09:26 # M/D Permalink

      네, 내일 퇴근 뒤부터 명절 시작이죠. 님께서도 즐거운 연휴 보내시길 바랍니다. ^^
      저는 공식 석상에서는 인서울이라는 것까지만 말씀드립니다. 누군지 정확하게 잘 모르는 분과는 일단은 이메일 교류만 받습니다. 개인적으로 하실 말씀이 많으면 홈페이지 대문(블로그 첫 화면 말고)에 있는 이메일을 보내 주시면 좋겠습니다.

      선생님의 관심분야는 텍스트 내지 문자열 처리 쪽인지요? 저도 궁금합니다.
      제가 쓰는 답장은 다른 사람에게도 다 보이기 때문에 짤막하게만 썼습니다.

Leave a comment

IOCCC라고, 사람이 가장 알아 보기 힘들고 충공깽스러운 형태로 작성된 C 프로그램 코드를 접수받는 공모 대회가 있다.
단순 코더가 아니라 전산학 내공과 해커 기질이 충만한 레알 베테랑 프로그래머라면 이미 들어서 알 것이다.

입상작들은 내가 보기에 크게 (1) 아스키 아트형, 아니면 (2) 크기 줄이기 암호형이라는 두 갈래로 나뉜다. 대회에 공식적으로 이런 식으로 참가 부문이 나뉘어 있는 건 아니지만, 여기 참가자들이 추구하는 오덕질의 목표가 대체로 이 둘 중 한 갈래로 나뉘기 때문이다.

전자는 영락없이 아스키 문자로 사람 얼굴이나 문자 같은 그림을 그려 놨는데 그건 컴파일 되는 올바른 C 코드이다. 그뿐만이 아니라 그걸 실행하면 기가 막힌 유의미한 결과물이 나온다. 간단한 게임이라든가 원주율값 계산 같은 것부터 시작해 심지어 CPU 에뮬레이터나 간단한 컴파일러, 운영체제까지 들어있는 경우도 있다.

후자는 수단과 방법을 가리지 않고 길이를 줄이기 위해 들여쓰기, 주석, 헝가리언 표기법 따위는 다 쌈싸먹고 진짜 정체를 알 수 없는 이상한 숫자와 기호와 문자로 범벅이 된 코드인데, 빌드해 보면 역시 소스 코드의 길이에 비해 믿을 수 없는 퀄리티의 동작이 나온다. 자바스크립트 같은 코드를 난독화 처리한 것과 비슷한 형태가 된다.

어떤 언어에서 소스 코드 자신을 출력하는 프로그램을 콰인(Quine)이라고 부른다. GWBASIC이라면 언어에 LIST라는 명령이 있으니 쉽겠지만, 일반적인 컴파일 기반 언어에서는 그걸 만드는 게 보통일이 아니다. 그런데 이 IOCCC 대회 입상작 중에는 A라는 코드가 있는데 그걸 실행하면 B라는 소스 코드가 출력되고, B를 빌드하여 실행하면 C라는 소스 코드가 나오고, 다음으로 C를 빌드하면 다시 A가 나오는... 중첩 콰인을 실현한 충격과 공포의 프로그램도 있었다. 그것도 A, B, C는 다 형태가 완전히 다르고 인간이 인식 가능한 아스키 아트! Don Yang이라는 사람이 만든 2000년도 입상작이다.

역대 수상작들을 보면 프로그래머로서 인간의 창의력과 잉여력, 변태스러움이 어느 정도까지 뻗칠 수 있는지를 알 수 있다. 그리고 이런 대회는 한 프로그래밍 언어의 극악의 면모를 시험한다는 점에서 전산학적으로도 나름 의미가 있다. 들여쓰기와 긴 변수명과 풍부한 주석이 갖춰진 깔끔한 코드든, 저런 미친 수준의 난독화 코드든 컴파일러의 입장에서는 어차피 아무 차이 없는 똑같은 코드라는 게 아주 신기하지 않은가?

다른 언어가 아니라 C는 시스템 레벨에서 프로그래머의 권한이 강력하다. 그리고 전처리기를 제외하면 특정 공백 문자에(탭, 줄바꿈 등) 의존하지 않는 free-form 언어이며, 언어 디자인 자체가 온갖 복잡한 기호를 좋아하는 오덕스러운 형태인 등, 태생적으로 난독화에 유리하다. 게다가 도저히 C 코드라고 볼 수 없을 정도로 코드의 형태와 의미를 완전히 엉뚱하게 뒤바꿔 버리는 게 가능한 매크로라는 비장의 무기까지 있다!

심지어는 C++보다도 C가 유리하다. 함수를 선언할 때 리턴 타입을 생략하고 함수 정의에서는 리턴 문을 생략할 수 있다. 가리키는 대상 타입이 다른 포인터를 형변환 없이 바로 대입할 수 있으며, 또한 인클루드를 생략하고 표준 함수를 바로 사용할 수도 있다. C++이었다면 바로 에러크리이지만, C에서는 그냥 경고만 먹고 끝이니 말이다. C의 지저분한 면모가 결국 더 짧고 알아보기 힘든 코드를 만드는 데 유리하다는 뜻 되겠다.

현업에서는 거의 언제나 C++만 써 와서 잘 실감을 못 했을 뿐이지, C는 우리가 생각하는 것보다 저 정도로 꽤 유연(?)한 언어이긴 하다. IOCCC 참가자의 입장에서 C++이 C보다 언어 구조적으로 더 유리한 건, 아무데서나 변수 선언을 자유롭게 할 수 있다는 것 정도일 것이다.

그러나 겨우 그 정도로는 불리한 점이 여전히 유리한 점보다 더 많은 것 같다. 생성자와 소멸자, 오버로딩, 템플릿 등으로 더 알아보기 힘든 함축적인 코드를 만드는 건 상당한 규모가 있는 큰 프로그램에서나 위력을 발할 것이고, 긴 선언부의 노출이 불가피하여 무리일 듯.

옛날에는 대회 규정의 허를 찌른 엽기적인 꼼수 작품도 좀 있었다.
이 대회는 1984년에 처음 시작되었는데, 그때 입상작 중에는 main 함수를 함수가 아니라 기계어 명령이 들어있는 배열로 선언해 놓은 프로그램이 있었다(1984/mullender). 이건 기계 종류에 종속적일 뿐만 아니라 요즘 컴파일러에서는 링크 에러이기 때문에, 그 뒤부터는 대회 규정이 바뀌어 이식성 있는 코드만 제출 가능하게 되었다.

그리고 1994년에는 콰인이랍시고 0바이트 소스 코드가 출품되었다(1994/smr). 소스가 0바이트이니, 아무것도 출력하지 않아도 콰인 인증..;; 이건 충분히 참신한 덕분에 입상은 했지만 그 뒤부터는 역시 소스 코드는 1바이트 이상이어야 한다는 규정이 추가되었다. 빈 소스 파일을 빌드하려면 빌드 옵션도 좀 미묘하게 변경을 해야 했다고 한다.

이런 코드를 작성하기 위해서는 모든 변수와 함수를 한 글자로 표현하는 것부터 시작해서 평범한 계산식을 온갖 포인터와 비트 연산자로 배배 틀기, 숫자 테이블 대신 문자열 리터럴을 배열로 참고하기(가령, "abcd"[n]) 같은 건 기본 중의 기본 테크닉이다. 그리고 그걸 아스키 아트로 바꾸는 능력이라든가, 원래 오리지널 프로그램을 기가 막히게 짜는 기술은 별개이다. 이런 코드를 만드는 사람은 정말 코딩의 달인 중의 달인이 아닐 수 없다.

이 대회는 전통적으로 외국 해커 덕후들의 각축장이었다. 그러나 지난 2012년도 대회에서는 자랑스럽게도 한국인 입상자가 한 명 배출되었는데, 본인의 모 지인이다. 그가 출품한 프로그램은 영어로 풀어 쓴 숫자를 입력하면(가령, a hundred and four thousand and three hundred and fifty-seven) 그걸 아라비아 숫자로 바꿔 주는 프로그램(104357). 코드를 보면 저게 어딜 봐서 숫자 처리 프로그램처럼 생겼는가. -_-

코드를 대충 살펴보면, long long이 바로 등장하는 데서 알 수 있듯, 나름 32비트 범위를 벗어나는 큰 자리수까지 지원한다. 문자열 리터럴을 배열로 참고하는 것도 곧바로 쓰였음을 알 수 있다.
그리고 옛날의 C 시절에 허용되었던 관행이었다고 하는데, 함수의 인자들을 아래와 같은 꼴로 선언하는 게 이 대회 출품작에서는 종종 쓰인다고 한다.

int func(a,b) int a, char *b; { ... }

하긴, C/C++이 기괴한 면모가 자꾸 발견되는 건 어제오늘 일이 아니다.
a[2]뿐만이 아니라 2[a]도 가능하다든가,
#include 대상으로 매크로 상수도 지정 가능하다든가,
C++의 default argument로 0이나 -1 같은 것뿐만 아니라 사실은 아예 함수 호출과 변수 지정도 가능하다는 것..
switch문의 내부에 for 같은 다른 반복문이 나온 뒤에 그 안에 case가 있다던가..;;

정말 약 빨고 만든 언어에다 약 빨고 코딩한 개발자라고밖에 볼 수 없다.
나로서는 범접할 수조차 없는 이상한 프로그래밍 대회에 한동안 엄청 관심을 갖더니 결국 입상해 버린 그의 오덕력에 경의를 표한다. 그저 놀라울 뿐이다. 이 정도로 소개하고 띄워 줬으니, 그분이 이 자리에 댓글로 소환되는 걸 기대해 보겠다. 아무래도 한국인 다윈 상 수상자가 배출된 것보다는 훨씬 더 자랑스러운 일을 해낸 친구이지 않은가. ㄲㄲㄲㄲㄲㄲㄲ

뭐, 입상했다고 당장 크게 부와 명예가 뒤따르는 건 아니겠지만, 팀장이나 임원이 IOCCC에 대해서 아는 개발자 출신인 회사에 지원할 때 “나 이 대회 입상자요!”라고 이력서에다 써 넣으면 그 이력서의 메리트는 크게 올라갈 수밖에 없을 것이다. 실제로 IOCCC 같은 잉여로운 대회에 참가하는 geek 중에는 구글, MS급 회사 직원도 있고, 사실 이런 대회에 입상할 정도의 guru급 프로그래머가 일자리를 못 구해 걱정할 일은 절대 없을 테고 말이다.

이런 대회에 더 관심 있으신 분은, IOCCC의 국내 저변 확대를 위해 애쓰고 있는 저 친구의 소개 페이지를 참고하시기 바란다.

Posted by 사무엘

2013/04/10 19:20 2013/04/10 19:20
, , , ,
Response
No Trackback , 6 Comments
RSS :
http://moogi.new21.org/tc/rss/response/816

Trackback URL : http://moogi.new21.org/tc/trackback/816

Comments List

  1. 김재주 2013/04/10 19:57 # M/D Reply Permalink

    맆군이군요

  2. 아라크넹 2013/04/10 23:14 # M/D Reply Permalink

    혹시나 해서 말해 두자면 사실 IOCCC 수상 경력은 취업에는 별 도움이 안 되었습니다(...) 모르는 사람이 더 많아서... 아는 사람은 뿜었지만.

  3. 사무엘 2013/04/11 10:44 # M/D Reply Permalink

    김재주: 제게는 다른 이름으로 더 친숙합니다. ㅎㅎ

    아라크넹: 뭐, 아직은 완전 생소할 수밖에.. 님이 최초 입상자이고 하고. (소환 성공ㄳ)

  4. Lyn 2013/04/11 10:22 # M/D Reply Permalink

    저 대회를 알긴 아는데...

    회사에서도 저럴까봐 거부감느껴짐

    1. 사무엘 2013/04/11 10:57 # M/D Permalink

      설마 그러겠어요. ㅎㅎ

    2. 아라크넹 2013/04/11 13:34 # M/D Permalink

      사실 일부러 저렇게 짜는 것 자체가 어려운 일이라서 돈 받고 일부러 저러고 싶은 사람은 (악감정을 가지지 않은 한) 별로 없겠죠. 위의 IOCCC 입상 코드도 수십시간을 쏟아 부어서 만든 건데 이걸 시급으로 환산하면야...

Leave a comment

열차 좌석 배당 알고리즘

열차의 승차권을 구입하면 좌석은 어떤 식으로 배당될까?
객차 하나당 좌석은 차량에 따라 60~70개 정도가 있으며, 열차 한 편성은 일반실만 생각하더라도 최하 4량부터 시작하고 KTX의 경우 거의 15량에 가깝다. 수백 개의 좌석들은 어떤 순서와 원칙대로 승객에게 팔려 나갈까?

난 철덕후로서 그 알고리즘이 예전부터 굉장히 궁금했다. 여러분은 그렇지 않은가?

버스 정도면 그냥 아무렇게나 랜덤으로 배당해도 별 무리가 없을 것이다.
우등 고속버스는 가장 쉽다. 승차 정원부터가 30명이 채 안 되는 소규모인 데다, 좌석이 구조적으로 2개짜리와 1개짜리로 나뉘어 있으니 말이다.

단독 승객에게는 진행 방향 기준으로 오른쪽의 단독 좌석부터 먼저 배당해 주고, 그게 매진되거나 2인 승객이 있으면 2인 좌석을 준다. 상석인 맨 앞자리는 약간 나중에 팔리도록 다른 가중치를 부여하고, 반대로 최악의 자리인 맨 뒷자리는 최하위 우선순위로 팔리게 하면 될 것이다.

그러나 열차는 단순하게만 좌석을 배당해서는 대략 곤란하다.
1부터 n호차까지, 그리고 진짜 무식하게 1번부터 m호석까지 앞에서 뒤로 순서대로 꽉꽉 승객을 채워 넣어서 뒤의 객차는 텅 빈 채로 달리게 할 리는 없을 테고..

그렇다고 좌석을(특히 단독 승객) 완전 랜덤으로만 여기저기 들쭉날쭉으로 배당하면 좌석의 단편화(fragmentation)가 너무 심해진다. 그래서 승객이 얼마 타지도 않은 상태인데 이따금씩 타는 2인 이상의 다수 승객은 이어진 좌석을 못 구해서 서로 찢어져서 앉아야 하는 일이 벌어질 수 있다.

결국 본인이 추측하기로는 열차의 좌석 배당은 저 양 극단의 중간을 절충하는 방식으로 이뤄질 것 같다.
두세 개의 객차를 묶음으로 나눠서 한 묶음 안에서 좌석을 무작위로 배당한 뒤, 그 묶음의 좌석이 다 매진되면 다음 묶음으로 간다. 각 묶음은 1~3호차, 4~6호차, 7~9호차 같은 규칙으로 만들 수도 있고, 반대로 1, 4, 7호차와 2, 5, 8호차, 3, 6, 9호차 같은 규칙으로 만들 수도 있다.

그리고 각 객차 안에서는 전체의 50~60% 정도는 단독 승객이 무작위로 띄엄띄엄 앉을 수 있게 배려한다. 즉, 2개짜리 좌석이라도 한 자리에 단독 승객이 있으면 거기는 일단 건너뛰고 다른 빈 자리를 찾는다는 뜻이다. 그러나 나머지 자리는 가능한 한 2인 승객이 한꺼번에 찜할 수 있게 비워 두며, 한 객차의 좌석의 10~20% 정도는 마치 KTX 동반석처럼 4인 가족이 연속해서 앉을 수 있게, 가능한 한 1~2인 승객에게 금세 팔리지 않도록 비워 둔다.

단독 승객의 경우 창측 좌석이 내측 좌석보다 먼저 팔리게 하는 건 기본이다. 또한 열차에서는 출입문과 가까운 맨 앞이나 맨 뒤 좌석이 '안 좋은 자리'이므로 이것 역시 다른 좌석이 모두 팔린 뒤에 나중에 팔리게 해야 할 것이다.
단독 승객용 좌석과 2인 이상 승객용 좌석 영역을 정하는 것 역시 '엿장수 마음대로' 무작위로 하면 되며, 그 비율 역시 평소에 승차권이 팔리는 단위 통계를 근거로 합리적으로 정하면 될 것이다.

저런 균형적인 요소에 덧붙여 환승 동선도 고려 대상이 된다.
국내의 예를 들면 KTX 천안아산 역과 장항선 아산 역은 남쪽 끝에서 만난다. 그리고 KTX는 한 편성이 무려 400m가 약간 안 되는 매우 긴 열차이다. 그렇기 때문에 경부선 KTX를 타다가 천안아산 역에서 장항선으로 환승하는 승객은 부산 방면(하행) 열차의 경우 최대한 앞쪽 객차로 좌석이 배당되고, 서울 방면 열차는 뒤쪽 객차로 좌석이 배당된다. 지하철에서 환승을 빨리 할 수 있는 객차의 위치와 정확히 같은 개념이며, 한국 철도도 그 정도 센스는 이미 갖추고 있다.

이 정도면 내가 보기에 열차 좌석 배당 전략을 짜는 건, 마치 열차 시각표를 짜는 것에 필적하는 철도 영업 기술의 결정체가 될 수도 있을 것 같다.
현실성 있는 열차 운행 시각표를 짜기 위해서는 그 나라의 철도 인프라와 지형 특성, 차량 제원, 승객 패턴 등의 알토란 같은 영업 기밀이 총동원되어야 한다. 이런 걸 계획하는 건 인원을 더 투입한다고 신속하게 되는 게 아니며, 핵심 똘똘이 인력 한두 명이 다 도맡아 한다.

좌석 배당도 마찬가지일 거라는 말이다. 철덕이라면 반드시 정복해야 하는 분야 중 하나 되시겠다.
비행기는 무게 배분이(한쪽에만 승객 무게가 지나치게 쏠리지 않게) 좌석 배당에 감안되는 요인이라고 하는데, 철도는 무게 배분 걱정은 할 필요가 없는 대신 길다는 특성상 다른 변수가 존재하는 셈이다.

자, 여기까지만 글을 쓰려고 했는데, 빈 좌석에다 승객을 일정 규칙대로 채워 넣는 과정을 생각하자니 컴퓨터그래픽에서 중요하게 다뤄지는 알고리즘 분야가 문득 떠오르더라.
바로 디더링이다.

디더링은 적은 수의 색깔을 섞어서 더 화려한 색깔을 아쉬운 대로 표현하는 기법이다. 색을 물리적으로 섞을 수는 없으니 결국 서로 다른 색깔을 번갈아가며 늘어놔야 하는데, 한 색깔이 뭉치는 게 아니라 서로 다른 색깔들끼리 최대한 고르게 퍼지도록 픽셀을 배열해야 한다.

본인은 과거에 Windows 3.x 시절에 그림판에서 임의의 RGB 값을 주면 그 색을 16컬러만으로 디더링하여 표현하는 걸 보고 무척 신기해했었다. 가령, 흑에서 백으로 단계를 증가시킬 때, 검은색에서 흰색 점이 차츰 늘어나는 순서가 어떻게 정해지는지가 무척 궁금했다.

그 규칙을 디더링에서 threshold matrix라고 부른다. 일반적인 그래픽 프로그램에서는 8*8짜리를 사용한다. (출처는 위키백과) 저기서 1부터 16까지의 점을 순서대로 채우면 25% 음영이 그려지고, 32까지 채우면 흑백이 딱 반반씩 번갈아가며 등장하는 50% 음영이 되는 식이다.

사용자 삽입 이미지
처음에는 4픽셀 간격으로 띄엄띄엄 점을 그리고, 나중에는 그 사이의 4픽셀 간격을 채우는 식으로, 점들이 뭉치지 않고 어떤 경우에도 최대한 흩어져서 퍼져 있게 한다. 임의의 격자 크기가 주어졌을 때 threshold matrix를 생성하는 프로그램을 만들 수도 있을 법해 보이는데 그리 만만한 일은 아닌 것 같다. 마방진도 아니고 말이다.

더 나아가 임의의 색을 16컬러 디더링 패턴으로 표현해 내는 프로그램을 직접 짜 보면 어떨까? 주어진 색을 가장 가깝게 표현할 수 있는 2색 또는 3색 조합을 구한 뒤, 그 비율만큼 threshold matrix를 각각의 색으로 채우면 될 것이다. 색조합을 구하는 것은 미지수의 개수가 식의 개수보다 더 많아서 답이 하나로 딱 떨어지지 않는 부등식이 될 터이니, LP(선형 계획법) 같은 계산 기법이 동원돼야 하지 않을까 싶다.

그렇게 threshold matrix만을 정석대로 적용하면 ordered dithering이 된다. 그러나 그것만으로는 그림이 칙칙하고 보기가 안 좋기 때문에, 디더링된 색깔의 픽셀이 인접 픽셀에 시각적으로 끼치는 영향을 감안하여(error diffusion) 더 정교하게 디더링을 수행하는 알고리즘이 실생활에서 쓰인다. 더 깊게 들어가는 건 이 글의 범위를 벗어나므로 자세한 설명을 생략하겠다.

뜬금없이 디더링 얘기를 꺼낸 이유는.. 저렇게 디더링 점을 찍어 나가는 게 마치 열차 좌석을 배당하는 것과 비슷한 심상이 느껴져서이다. 열차 좌석의 점유 여부를 흑백 픽셀로 표현하고 시간이 흐름에 따라 픽셀들의 상태를 표시하는 시뮬레이션을 돌려 보면 재미있을 것 같다. 한쪽은 검은 색이 듬성듬성 있고, 한쪽은 검은 색이나 흰 색이 좀 연속해서 있겠지 아마?

철도의 좌석 배당 알고리즘과 래스터 그래픽의 디더링 알고리즘은 서로 따로 생각하고 있었던 주제인데 이렇게 한 글로 연결이 됐다. 마치 예전에 내가 열차의 급행 등급과 셸 정렬을 한데 묶어서 글을 썼듯이 말이다. 참 신기한 일이 아닐 수 없다. ㅋㅋㅋㅋ

Posted by 사무엘

2013/04/08 08:18 2013/04/08 08:18
, , , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/815

Trackback URL : http://moogi.new21.org/tc/trackback/815

Comments List

  1. 김재주 2013/04/08 18:21 # M/D Reply Permalink

    흥미로운 주제로군요. 비슷하다면 비슷한데 또 다르다면 다른 주제로 동영상 압축 기법인 벡터 양자화(vector quantization)가 있습니다. 이를테면... 16x16 크기의 샘플 패턴 N개를 생성합니다. 이후 동영상의 각 프레임들을 16x16 격자로 나눈 후 거기에 대응되는 샘플 패턴의 번호로 나타내는 것이죠. 만일 패턴이 256개라면 1바이트로 표현할 수 있으니까 RGB 각 1바이트로 나타낸 색 공간에서라면 동영상은 1/3크기로 줄어들게 되겠죠.

    샘플 패턴을 어떻게 정할 것인가는 자명한 방법이 있습니다. 해당 샘플 패턴을 사용할 격자들과의 제곱오차를 최소로 하는 패턴을 사용하면 되겠죠. 다시 말해서 그 격자들의 기하평균을 구하면 됩니다.


    그렇다면 결국 각각의 격자값을 어떤 패턴에다 대응시키는 것이 화질 열화를 최소로 하는 방법인지 찾아내야 하는데 고려해야 할 변수가 많기 때문에 그리 쉽지는 않습니다. 이 경우에도 LP 등의 기법을 많이 동원하더군요. 그런데 Genetic algorithm에다가 local optimization을 동원한 알고리즘이 상당히 좋은 성능을 보인다는 얘기를 봤어요.

  2. 김재주 2013/04/08 18:26 # M/D Reply Permalink

    아, 어찌보면 엘리베이터 스케쥴링 문제와도 비슷하군요. 서울대학교 문병로 교수님의 논문을 링크합니다.
    http://soar.snu.ac.kr/papers/journals/9.pdf

    엘리베이터 이용객은 흔히 푸아송 분포를 따른다고 알려져 있는데 이를 이용해서 다양한 평가항목을 가장 잘 만족시키는 스케쥴링 규칙을 GA를 이용해서 adaptive하게 바꿔나간다는 것입니다.

    승객들의 철도 이용 행태도 거의 해마다 비슷할테니 1년 전의 데이터를 바탕으로 현재 최적이라고 할 수 있을 만한 배치 규칙을 찾아내게끔 할 수 있겠습니다. 코레일 나름대로 사용하고 있는 방법이 있겠지만, 이런 쪽으로도 한번 연구개발을 해보는 것이 어떨까 싶습니다.

    1. 사무엘 2013/04/08 22:54 # M/D Permalink

      1. 여러 흥미로운 보충 설명에 감사드립니다. 영상의 손실 압축에서 화질 열화를 최소화하는 기법에도 그런 방식의 문제가 있다는 것도 처음 알았고요. 그리고 문 교수님이 그 분야에도 손대신 적이 있다는 것도요.

      그리고 엘리베이터.. 그것도 좌석 배당만큼이나 경험적인 전략이 필요한 아주 실용적인 주제임이 틀림없어 보입니다. 아주 초창기에 1회 IOI 때 대놓고 엘리베이터 시뮬레이션 문제가 나온 적이 있었지만 그때는 너무 옛날이어서 대회 진행 방식이 정착하기 전이었고, 9회(97년) 6번 문제 컨테이너 쌓기도 비슷하다면 비슷한 주제 같습니다. 승객 대신 컨테이너이고, 좌석의 단편화 대신 스택 구조가 있는 셈이죠.

  3. 김재주 2013/04/09 13:44 # M/D Reply Permalink

    IOI 문제와는 좀 다른 것이 여러 개의 승강기가 있는 경우에 어떤 승강기를 스케쥴링할것인가 하는 문제라서요. 아무튼 열차 배치도 결국 평가함수는 수정되겠지만 거의 비슷한 접근을 할 수 있을 것 같네요.


    그리고 다시 보니까 1/3로 줄어드는 게 아니네요. 16x16격자를 대표하는 것이니까 1/3 * 1/16^2로 줄어듭니다 후덜덜..

Leave a comment

블로그 이미지

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

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2019/07   »
  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:
1220886
Today:
71
Yesterday:
474