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

디지털 컴퓨터는 전자 신호로 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 사무엘

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

지금으로부터 수십 년 전에는 동네마다 컴퓨터 학원이 있었고, 꼬꼬마가 프로그래밍을 공부하겠다고 하면 으레 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 사무엘

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

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

곱을 전부 합하면 진짜로 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 사무엘

한자어로 '원'이라고 부르는 동그라미라는 도형은 시각적으로나 수학적으로나 아주 신기한 도형이다.
둥글다는 게 무슨 의미인지 기계가 계산으로 표현할 수 있을 정도로 엄밀하게 정의하자면 결국 '어떤 점에서 거리가 같은 점들의 집합'이라는 정의가 등장하게 되고, 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;
    }
}

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

※ 들어가는 말

정렬은 검색과 더불어 컴퓨터가 인간에게 유용한 결과물을 내놓기 위해 내부적으로 가장 빈번히 수행하는 계산 동작에 속한다. 다른 알고리즘의 내부 과정으로 즐겨 쓰이기도 하고 말이다. 전산학 내지 컴퓨터 과학에서 정렬 문제가 얼마나 중요한지에 대해서는 더 말이 필요하지 않다.

정렬은 문제의 목표가 너무나 명확하고 실용적이며, 다양한 관점에서 문제의 접근이 가능하고 좋은 알고리즘과 나쁜 알고리즘의 차이도 아주 드라마틱하게 알 수 있기 때문에... 예로부터 그 특성과 해법이 연구될 대로 연구되어 왔다. 시간 복잡도 관념이 없던 초짜 프로그래머가 O(n^2)와 O(n log n)의 어마어마한 차이를 깨우치는 계기도 대체로 정렬 알고리즘을 공부하고부터이다.

n개의 원소에 대한 정렬 작업은 n개의 원소를 임의의 방식으로 늘어놓는 n!가지의 순열 중에, 원소들의 값 순서가 오름차순이나 내림차순이 유지되는 순열을 선택하는 작업이라고 볼 수 있다. 그리고 일반적인 정렬 알고리즘은 임의의 두 원소와의 비교를 통해 거기서 가능한 선택의 범위를 좁혀 나간다.

이런 원론적인 분석을 통해, 비교 연산 기반 정렬 알고리즘의 시간 복잡도는 아무리 기가 막힌 알고리즘을 고안하더라도 O(n log n)보다는 결코 더 좋을 수가 없다는 것이 증명되어 있다. 그리고 정렬 알고리즘 중, 제자리(in-place)라는 특성을 지닌 알고리즘은 교환(swap)이라는 동작도 공통적으로 사용하게 된다.

정렬 문제는 NP 완전 문제라고 알려져 있는 외판원 문제(TSP)에서 정점(vertex)들이 일렬로 쭉 나열되어 있는 특수한 경우라고 볼 수도 있다. 가까운 순서대로 순서대로 방문하는 게 정답일 테니 결국 정점들이 정렬된 것이나 마찬가지이다. 비록 domain이 1차원이 아닌 2차원 이상으로 가면 난이도가 곧바로 안드로메다 급으로 치솟지만 말이다.

※ O(n^2) 또는 O(n log n)인 비교 기반 알고리즘

역사적으로 굉장히 많은 수의 정렬 알고리즘이 고안되었으며 이들은 제각기 장단점과 특성이 있다. 알고리즘을 평가하는 주 잣대로는 자료 개수 n에 대한 시간 복잡도와 공간 복잡도가 있으며, 이들도 평균적일 때와 최악의 상황일 때를 따로 평가한다. 이 외에도 자료의 상태에 성능이 민감하게 달라지는지, 그리고 값이 같은 원소의 상대적인 순서가 보존되는지를 나타내는 순서 안정성(stability)을 따지기도 한다.

시간 복잡도가 O(n^2)에 속하는 정렬 알고리즘은 일명 '발로 짠 알고리즘'에 속한다. 직관적이고 구현하기 매우 쉬우나 성능이 쥐약이라는 뜻.
거품 정렬, 선택 정렬, 삽입 정렬이 대표적인데, 거품의 경우 배열이 아니라 아예 random access가 불가능한 연결 리스트 같은 컨테이너에다가 적용해도 좋을 정도로 바로 옆 원소와의 비교와 교환밖에 하지 않는다. 그 때문에 성능이 대단히 나쁘다.

선택 정렬은 비교에 비해 대입 연산이 적고 자료의 상태에 그리 민감하지 않은 게 특징이다. 그에 반해 삽입 정렬은 자료 상태에 따른 성능 편차가 크고 O(n^2) 알고리즘 중에서는 성능이 나은 편이기 때문에, 작은 범위의 입력에 한해서 종종 쓰이는 경우가 있다. 실제로 비주얼 C++의 qsort 함수 구현을 보면, 퀵 정렬을 쓰다가 구간이 8개 이하의 원소로 감소하면 거기는 삽입 정렬로 때운다.

O(n^2) 알고리즘들은 원리가 간단하기 때문에 공간 복잡도는 대체로 O(1)인 in-place이다. 한 쌍의 원소를 그때 그때 교환하기 위한 고정된 크기의 메모리밖에 쓰지 않는다는 뜻 되겠다. 시간이 비효율이면 공간 오버헤드라도 없어야 하지 않겠는가.

이론적인 시간 복잡도에 부합하는 O(n log n)급 알고리즘으로는 힙, 병합, 퀵 등이 있다. 이들은 시간 복잡도만 동일할 뿐 내부적인 특징은 정말 제각각이다.

일단 힙 정렬은 위의 세 알고리즘 중에서 유일하게 메모리 복잡도가 O(1)인 검소한 녀석이다. 그 대신 한 배열 안에서 왔다 갔다 하는 작업이 많아서 그런지 속도는 미세하게 다른 알고리즘보다 더 느린 편. 한 배열 안에서 heap 자료구조를 만든 뒤, 이것으로부터 정렬된 형태의 배열을 역순으로 만드는 두 단계의 과정이 무척 기발하며, 인간의 머리로 어째 이런 걸 생각해 낼 수 있는지 놀라움을 느낀다.

병합 정렬은 동급 시간 복잡도 알고리즘 중에서는 꽤 직관적인 편이고 또 유일하게 안정성도 있어서 좋다. 그러나 FM대로 구현한 녀석은 배열 복사본이 하나 더 필요하기 때문에 메모리 복잡도가 O(n)이나 되며, 대입에 대한 비용이 큰 자료구조에 대해서는 성능 하락의 폭이 큰 게 흠이다.

※ 퀵 정렬

한편, Tony Hoare이라는 영국의 전산학자가 1960년대에 20대 중반의 나이에 고안한 퀵 정렬은 정렬 알고리즘계의 종결자, 야생마, 이단아 같은 존재이다. pivot이라 불리는 중간값을 설정하여, 주어진 구간을 “pivot보다 작은 값, pivot, pivot보다 큰 값” 조건을 만족하게 swap 연산을 통해 바꾼다. 그 뒤, pivot을 기준으로 구간을 양분하여 양 구간도 재귀적으로 똑같은 작업을 한다. 알고리즘도 너무 명쾌하고 깔끔하지 않은가?

이 알고리즘은 대충 부분적으로 정렬되었거나 아예 완전히 무작위인 데이터에 대해서 매우 대단히 좋은 성능을 자랑한다. 그러나 pivot을 어떻게 정하느냐에 따라서 알고리즘의 성능이 크게 좌지우지되며, 자료의 상태에도 매우 민감해진다는 점이 간과될 수 없는 특성이다.

pivot이 데이터의 적당한 중간값으로 설정되지 못하고 하필이면 최소값이나 최대값으로 설정된 경우, 알고리즘 수행 후에도 구간은 깔끔하게 양분되지 못하고 하나씩만 줄어들게 된다. 이 경우 알고리즘의 수행 시간은 O(n log n)이 아니라 O(n^2)에 가까워진다! 역순으로 정렬된 데이터를 정렬하는데 구간의 맨 앞이나 맨 뒤의 값을 pivot으로 쓴다고 생각해 보자.

문제는 이때 시간 복잡도만 늘어나는 게 아니라는 것이다. 분할 정복법을 쓴다는 특성상 퀵 정렬은 재귀호출을 써서 구현되는데, 구간이 반씩 시원하게 안 쪼개지고 하나씩만 쪼개지면 재귀호출의 깊이도 자칫 n회가 될 수 있다는 뜻이다. 이 경우 프로그램은 stack overflow 오류가 발생하며, 이는 프로그램의 보안에도 악영향을 끼치게 된다.

다만, 쪼개진 구간 중에 원소 수가 많은 구간이 아니라 의도적으로 적은 구간부터 골라서 재귀적으로 처리하는 경우, 메모리 복잡도는 O(log n)으로 원천적으로 줄일 수 있다. 퀵 정렬 함수의 구현체 자체에 딱히 동적 배열 같은 게 없더라도 재귀호출 때문에 메모리 복잡도가 올라가며, 원소들이 정확하게 반씩 분할될 경우에 log n에 해당하는 깊이까지 간다는 뜻이다.

일반적으로 퀵 정렬의 구현체는 그냥 구간의 정중앙에 있는 원소만 pivot으로 지정하는 게 보통이다. 이렇게만 하더라도 O(n^2)의 최악 시간 복잡도를 만드는 입력 데이터를 일부러 만들기란 대단히 어려우며, 수학적으로 발생하기도 불가능에 가까운 건 사실이다.

하지만 공격자가 퀵 정렬 구현체의 알고리즘을 알고 있는 경우, 의도적으로 해당 알고리즘이 pivot을 요청할 만한 위치에 일부러 구간의 최대값이나 최소값을 집어넣어서 매 단계별로 퀵 정렬을 엿먹이는 게 불가능하지는 않다! 세상엔 그것만 전문적으로 연구한 사람도 있다. anti quick sort라고 검색해 보셈.. 이것이 퀵 정렬의 진정 오묘하고 이상한 면모라 하겠다.

이걸 이용하여 비주얼 C++의 qsort 함수로 테스트하면, 평소 같으면 인텔 i5 기준 눈 깜짝할 사이에 끝나는 정수 10만 개의 정렬이 수 초 대로 떡실신하는 기현상이 벌어지는 걸 볼 수 있다. 그런데 xcode의 C 라이브러리가 제공하는 qsort는 퀵 정렬을 쓰지 않는지 그런 것의 영향을 받지 않더라..

※ C/C++ 언어에서의 지원

C 라이브러리에 있는 qsort 함수는 콜백 함수에 전달해 줄 사용자 데이터--가령, 비교 옵션 같은 것--를 받는 부분이 없어서 무척 불편하다. 그래서 별도의 사용자 데이터는 전역 변수나 TLS(thread local storage)를 통해 얻어 와야 하는 번거로움이 있다. 이것이 비주얼 C++ 2005부터 도입된 qsort_s에서는 개선되었다.

한편, C++ 라이브러리에도 잘 알다시피 std::sort라는 함수가 있다. C 함수보다 type-safe할뿐만 아니라 iterator를 통해 포인터보다 더 추상적인 자료형도 정렬할 수 있으며, 비교도 직관적인 비교 연산자 아니면 functor로 편리하게 지정할 수 있어서 좋다. 또한 이건 템플릿 형태이기 때문에 정렬 코드가 해당 프로그램의 번역 단위에 최적화된 형태로 embed된다는 것도 더욱 좋다.

C의 경우 비교 연산 함수의 리턴값은 뺄셈 연산을 모델로 삼아서 '음수, 0, 양수' 중 하나를 되돌리게 되어 있다. 그러나 C++ 버전은 < 연산을 모델로 삼아서 그냥 true/false boolean값만 되돌리면 된다는 차이가 있다. 사실, 그것만 있어도 정렬이 되니까 말이다.

C++ 라이브러리에는 sort뿐만이 아니라 stable_sort도 있다. 하지만 실생활에서 꼭 stable_sort를 써야만 할 상황이 있는지는 모르겠다. 실제로 정렬 성능은 굳이 안정성이 지켜지지 않아도 되는 sort가 더욱 뛰어나다.

※ 기타 정렬 알고리즘

정렬 알고리즘의 시간 복잡도는 굳이 O(n^2) 아니면 O(n log n) 중 하나로만 떨어지는 게 아니다. 그 범주에 속하지 않는 대표적인 알고리즘은 셸 정렬이다. 고안자의 이름을 따서 명명된 이 알고리즘은 삽입 정렬이 대충 정렬된 자료에 대한 성능이 뛰어나다는 점을 응용하여, 삽입 정렬을 일정 구간별로 띄엄띄엄 반복해서 적용해 준 뒤 최종적으로 삽입 정렬을 full scale로 한번 돌려서 정렬을 끝낸다.

퀵 정렬이 pivot을 정하는 것이 판타지라면, 셸 정렬은 그 구간을 정하는 방식이 판타지이다. 셸은 분명 O(n^2)보다는 훨씬 더 뛰어난 성능을 보이지만 그렇다고 O(n log n)급은 아니다. 사실, 셸은 구간을 어떻게 설정하느냐에 따라서 시간 복잡도를 계산하기가 대단히 chaotic하고 어렵다.

구간을 두 배씩 좁히는 게 제일 나쁜 방법이이기 때문에 최악의 경우 도로 O(n^2)까지 떨어져 버리나, 약간 머리를 쓰면 O(n^1.5) 정도는 된다. 구간을 가장 잘 잡았을 때 최대 O(n (log n)^2)까지는 갈 수 있다는 것이 알려져 있다. 그래도 셸은 메모리 복잡도가 깔끔한 O(1)이고, 코딩이 상당히 짧고 간결하면서도 O(n^2)보다는 성능이 확실히 낫다는 데 의의가 있다.

앞서 말했듯이 정렬 알고리즘의 시간 복잡도의 한계가 O(n log n)이라는 것은 비교 연산을 사용하는 일반적인 알고리즘이 그렇다는 소리이다. 그런 방식으로 정렬을 하지 않는 알고리즘의 경우, O(n)짜리 알고리즘도 충분히 존재할 수 있다.

가령, 데이터의 도메인이 메달이어서 '금, 은, 동'이라는 세 종류밖에 없는 경우, 자료를 일일이 뒤져 볼 필요 없이, 각 메달의 개수를 세어서 금 a개, 은 b개, 동 c개라고 써 주기만 하면 될 것이다. 부동소숫점이나 문자열처럼 도메인이 굉장히 넓은 자료형은 그런 식으로 정렬할 수 없겠지만, 좁은 범위의 정수 정도면 그런 식으로 발상을 전환하여 비교 연산을 요청하지 않는 정렬 알고리즘을 쓸 수도 있다.

여기에 속하는 대표적인 알고리즘은 기수(radix) 정렬이며, 이 외에도 유사한 전략을 사용하는 알고리즘이 더 있다.

정렬 알고리즘에 대해서는 메아리 풉에도 수학적으로 더 엄밀한 개념 기술이 있으므로 참고하시고, 또 이 홈페이지에는 이미 아시는 분도 있겠지만 본인이 학부 시절에 정렬 알고리즘 모음집이라는 간단한 프로그램을 짜서 올려 놓은 게 있다. 일부 검색엔진에서는 '사이트'로도 등록되어 있다. ㅎㅎ 관심 있으신 분은 거기 소스도 참고하시기 바란다.

* 여담이지만, 전산학 덕후와 해커들의 머리 싸움 덕질에는 끝이 없는지라, 퀵 정렬뿐만 아니라 hash 알고리즘을 엿먹이는 연구도 이미 될 대로 돼 있다.. 특정 해싱 알고리즘에 대해서 충돌만 골라서 일으키는 입력을 생성하는 것 말이다.

Posted by 사무엘

굳이 전산학이나 컴퓨터과학· 공학의 전공자가 아니어도, 그리고 현업 프로그래머가 아니더라도 조금만 기계 다루는 것에 조예가 있는 컴덕후라면 요즘 컴퓨터의 발전 추세가 어떤지는 다들 알 것이다. 사실은 <날개셋> 한글 입력기의 개발자인 본인보다도 더 잘 알 것이다.

튜링 완전하며 메모리로부터 프로그램을 읽어 와서 구동하는(프로그램 내장 방식) 범용 컴퓨터가 발명된 지가 아직 100년은커녕 반세기 남짓밖에 지나지 않았다. 그러나 컴퓨터의 속도와 메모리 용량은 가히 넘사벽급으로 발달했다. 컴퓨터는 지난 수십 년 동안 자연이 아니라 인간의 발명한 물건의 내부에서, 시간에 따른 지수함수 스케일의 발전을 볼 수 있던 얼마 안 되는 엄청난 분야였다.

그러나 그것도 한계는 있어서 컴퓨터 성능의 대표적인 지표이던 클럭 속도가 2003년 즈음에 놀랍게도 지수함수적인 성장이 멈췄다. 10년까지는 아닌 거 같다만 8, 9년 전의 PC나 지금의 PC나 다 3GHz대이다. 오늘날과 같은 반도체 회로라는 근본적인 패러다임이 바뀌지 않는 한, 전력 소모와 발열 때문에 컴퓨터의 기본 동작 자체만의 속도가 더 빨라질 수는 없다.

우리가 다루는 컴퓨터는 생각보다 굉장히 정밀하고 빡세게 만들어져 있다. 예전부터 파이프라인, pre-fetching 등 온갖 있는 테크닉, 없는 꼼수를 다 동원해서, 어떻게든 낭비되는 자원이 없이 모든 자원이 계산에 동원되고, 1ms라도 속도를 더 올리려고 공돌이들의 온갖 공밀레 연구가 동원되었다. 이런 수직적인 성장이 한계에 달하니 요즘 컴퓨터는 코어 수를 늘려서 분업이라는 수평적인 성장을 추구하고 있다.

100이라는 일이 있어서 이게 2GHz짜리 컴으로 다 처리하는 데 10이라는 시간이 걸린다면, 1GHz짜리 컴으로는 20만큼의 시간이 걸릴 것이다. 그러나 1GHz 짜리 컴이 2개 있어서 그 일을 정확히 50씩 분담할 수 있다면, 각각의 컴퓨터의 최대 속도는 비록 1GHz밖에 안 되더라도 10에 가까운 시간 만에 일을 끝마칠 수 있어서 2GHz에 준하는 효과를 낼 수 있다. 이것이 기본적인 아이디어이다.

물론, 딱 10으로 줄이지는 못한다. 일을 분할하고 두 대의 컴퓨터를 세팅하고 굴린 후, 두 컴퓨터(코어)가 내놓은 결과를 취합하는 오버헤드가 역시 결코 작지 않기 때문이다. 그리고 세상에 상호 의존성이 없이 역할을 저렇게 딱 분담할 수 있는 작업이란 흔치 않다.

방대한 계산이 필요한 작업을 다수의 컴퓨터 기계들을 여러 대 동원해서 수행하는 건, 분산 컴퓨팅이라 하여 예전부터 그리 생소한 개념이 아니었다. 3D 그래픽으로 영화를 만드는 업계에서는 rendering farm이라 하여 수많은 컴퓨터들을 농장에다 비유할 정도로 열나게 굴려서 영상을 만들어 낸다. 빌드 속도가 느린 걸로 악명 높은 C++ 언어를 위해서 Incredibuild라는 이스라엘산 분산 빌드 시스템도 있다.

그런 것처럼 개개의 컴퓨터도 이제 코어가 여러 개 돌아가고 멀티스레딩 능력이 충분히 뛰어나니, 이제는 프로그램 차원에서 멀티코어-aware한 개발이 필요해졌다. 왜냐하면 분산 처리 시스템을 설계하는 건 정말 머리가 뽀개질 정도로 복잡하기 때문에 컴퓨터나 컴파일러가 자동화를 해 줄 수 없다. 예전 계산 결과에 의존적인 다음 계산을 병렬로 동시 수행시킬 수는 없는 노릇이니까 말이다.

그렇기 때문에 멀티코어-aware하지 않은 옛날 프로그램은 컴퓨터가 언제나 최악의 case로 가정하고 보수적으로 돌려서 코어를 하나만 할당하여 돌아가게 된다. 한 프로그램이 while(1); 만 하고 가만히 있다 해도 CPU 사용률이 100%로 치솟지 않는다.

특히 C/C++의 포인터는 그야말로 아무 메모리 주소나 가리킬 수 있고, *a, *b가 있으면 둘이 가리키는 주소가 같을지 아닐지 등 최적화나 병렬화를 할 여지가 없을 정도로 너무 generic하기 때문에 오히려 처리가 어렵다고 한다. 파스칼이나 포트란처럼 언어 표현력이 C/C++보다 부족한 대신에 컴파일러가 소스 코드만 보고서 그 복잡도를 어느 정도 파악할 수 있는 언어가 병렬화에는 오히려 더 유리하다고.

그래서 소스 코드의 특정 구간에 대해서 컴파일러나 CPU가 안심하고 병렬화를 할 수 있게 중간 중간에 부가정보를 인위적으로 넣어 줄 필요가 생겼는데, 이런 부가정보를 기술하는 표준 규격 중 하나가 그 이름도 유명한 OpenMP이다. #pragma omp 같은 컴파일러 지시자도 있고, OpenMP 라이브러리보부터 호출해서 쓰는 함수도 있다.

옛날에 C언어가 처음 발명되던 시절엔 최적화를 위해서 변수를 가능한 한 레지스터에 올려라고 지시하던 register라는 카워드가 있었는데, 앞으로 C/C++ 같은 네이티브 코드 언어는 멀티코어를 언어 차원에서 수용하는 규격이 덩달아 생겨야 할 것이다.

물론, CreateThread 같은 함수를 써서 코드의 로직 차원에서 대놓고 여러 작업 스레드를 만들었다면, 단일 프로세스가 여러 개의 코어를 자연스럽게 점유하는 게 응당 가능하다. 그러나 디자인의 성격상, 멀티스레딩은 보통 일하는 스레드, 사용자 UI 스레드, 입출력 신호를 기다리는 스레드처럼 용도별로 달리 배당하는 게 바람직하지, 동일한 일을 하는 코드 내부에서 굳이 다중 코어 활용을 위해 스레드를 분할하기에는 동기화를 비롯해 일이 너무 복잡해진다. 서버 같은 게 아니라면, 제각기 CPU를 full로 사용하는 여러 작업 스레드를 만들 일 자체가 매우 드물다.

이때 멀티코어 프로그래밍을 잘 하면 이런 단일 코드가 명시적인 스레드 생성을 하지 않고도 CPU의 자원을 골고루 전부 활용해서 고성능으로 돌아가게 된다. 다만 앞서 말했듯이 이렇게 작업을 분할하는 오버헤드부터가 큰 편이기 때문에, 소규모 작업보다는 동영상 인코딩이나 대용량 파일 압축이나 컴파일 같은 진짜 방대한 작업에서 멀티코어의 진가는 더욱 두드러질 것이다.
일례로, 비주얼 C++은 2005부터 빌드할 때 병렬 컴파일이 수행된 경우, 빌드 로그에 해당 빌드를 수행한 코어의 번호가 뜬다.

O(n^3)짜리 행렬 곱셈은 워낙 단순 무식하고 복잡한 의존도 따위도 없는 순수 노가다이다 보니, “나 병렬화 해 주세요”라고 온몸으로 외치는 문제라고 볼 수 있다. 퀵 정렬이나 병합 정렬처럼 구간이 딱딱 나뉘는 알고리즘이 병렬화에도 적합한 구조일 것 같긴 하다만, 요즘 컴퓨터의 성능이라면 겨우 internal sort 규모의 정렬 작업은 굳이 멀티코어를 쓸 필요도 없을 정도로 금방 끝날 듯.

요컨대 이제는 고성능 컴퓨터를 쓰는 것만으로 프로그램의 수행 속도가 저절로 올라가는 시대는 끝났다. 그 다음으로 레지스터 배당이라든가 캐시나 파이프라인 적중률 같은 건 CPU 설계에 맞춰 컴파일러가 더 똑똑해야 하는 영역인데, 이 역시 튜닝의 수준은 예술의 경지에 도달해 있다. 그리고 그 다음으로 필요해진 것이 코드에 등재되어 있는 병렬화 가능성 정보라고 생각하면 되겠다. 멀티코어는 프로그래머가 잘 숙지하고 있어야 하는 프로그래밍 패러다임이 되었음이 틀림없다.

Posted by 사무엘

전산학 전공자 내지 IT 분야 종사자에게는 상식으로 통용되는 당연한 개념이다만..
오늘날 범용(generic-purpose) 컴퓨터에서 돌아가는 소프트웨어는 크게 세 가지 형태로 나뉜다.

1. 로컬

흔히들 PC로 대표되는 컴퓨터에서 stand-alone으로 동작하는 전통적인 프로그램이다. Windows야 그렇다 치더라도 오피스, 비주얼 스튜디오 같은 업무용 프로그램은 아직 로컬 프로그램의 아성을 무너뜨릴 영역이 없다.
가장 역사가 길고, 가장 빠르고 효율적으로 동작하며, 특정 컴퓨터 아키텍처(기계어)와 운영체제의 실행 파일 포맷에 종속적이다. 그래서 이쪽 개발 환경은 전통적으로 C/C++ 같은 저수준 최적화 언어가 강세이다.

물론 클라이언트가 아닌 서버 프로그램은 성격이 약간 다르긴 하나, 서버 프로그램 자체는 역시 서버라는 로컬 컴퓨터 자신의 자원만을 이용하여 동작한다. 여객 운송과 화물 수송의 차이와 비슷한 맥락이다. 그리고 사실은, 다음에 설명할 2.웹 프로그램을 돌려 주는 기반도, 클라이언트든 서버든 1.로컬 프로그램들이 다 마련해 주고 있다. 그러니 로컬 프로그램은 앞으로도 없어질 수는 없다. 단지 전체 소프트웨어에서 차지하는 비중이 줄어들 뿐이다.

옛날에는 불특정 개인 사용자를 대상으로 하는 상업용 제품은 패키지 형태로 발매되곤 했지만, 오늘날은 인터넷의 발달과 극심한 불법 복제로 인해 이런 전통적인 형태의 배포의 비중이 굉장히 줄어들었다. 오늘날 국산 패키지 소프트웨어는 아래아한글과 V3 말고 있나? -_-;; 또한 보안 위협으로 인해 이런 프로그램 역시 한번 설치하고 끝이 아니라 끊임없는 보안 패치와 업데이트의 필요성이 커져 있기도 하다.

2. 웹

개인용 컴퓨터의 성능이 굉장히 향상되고 그에 따라 웹 표준이 발달하면서 웹브라우저, 정확히 말해 WWW는 단순히 그림과 하이퍼링크가 동원된 문서라기보다는 거의 프로그래밍 플랫폼처럼 오래 전부터 바뀌었다.

웹 프로그래밍의 최대 매력은 로컬을 월등히 능가하는 범용성과 기계 독립성, 생산성이다. 브라우저에서 사이트 접속만 하면 바로 실행..;; 마치 게임처럼, 클라이언트와 서버, 코딩과 디자인 등을 두루 아우르는 종합 예술처럼 보이기도 한다. 가령, 옛날에는 GWBASIC이나 LOGO로 어린 학생들에게 그래픽 프로그래밍 교육을 시켰다면, 지금은 그냥 HTML5만 써도 될 것이다.

물론, 로컬 개발에 비해서는 혼자 독립적인 작품을 만든다는 느낌이 좀 덜 들며-_-, 기술이 아직까지 안정화해있지 않은 면모가 있고, 로컬 컴퓨터 자체를 세밀하게 제어할 수 없으며 성능이 떨어진다는 한계도 있다. 가령, 오피스 제품군이 웹 애플리케이션으로 완전히 대체될 날은 과연 글쎄?
그러나 앞으로 웹 프로그래밍의 비중은 절대 무시 못 할 것이고 수요도 없어지지 않을 것이다.

3. 앱

스마트폰에서 동작하는 '로컬' 프로그램이라고 볼 수 있지만, 그 성격이 역시 1과는 사뭇 다르다.
스마트폰 자체는 PC보다 성능이 떨어지기 때문에, 로컬에서 모든 처리를 마친다기보다는 서버에다 input을 보내서 받은 output을 보여주는 형태의 앱이 많다. 또한 스마트폰은 화면이 작고 PC 같은 빠른 문자 입력을 할 수 없기 때문에, PC와는 다른 독자적인 GUI가 필요하다. 터치스크린은 마우스와 완전히 동일한 포인팅 UI가 아니다. (대표적으로 hovering이란 게 없다) 다만, PC에는 없는 기울임, 흔들림, 방향, 현재 위치 같은 특수한 입력을 받아들일 수 있다.

스마트폰은 PC만치 사용자가 컴퓨터 내부를 완전히 손쉽게 제어할 수 있는 물건은 아니다. 그래서 PC용 프로그램보다는 더 엄격한 과금 체계를 갖추고 프로그램을 배포하여 수익을 낼 수 있다.
스마트폰 앱은 역사가 짧기 때문에 PC 같은 지저분한 호환성 잔재 같은 게 덜하고, 일찍부터 자바든 C#이든 객체지향 언어와 가상 기계 바이트코드 기반의 프로그래밍 환경이 잘 구축돼 있다. 깔끔한 최신 프로그래밍 인프라가 기본으로 제공된다는 뜻이다.

오늘날 스마트폰 CPU는 ARM 아키텍처밖에 없지만, 그래도 커널 말고 다른 응용 프로그램들은 네이티브 코드가 아니다. 그런 .NET이나 자바 같은 가상 기계 자체가, 1~3(로컬, 웹, 앱) 사이의 이질감을 낮추고자 만들어진 것이기도 하고 말이다.
아울러, CPU의 성능이 좋아졌을 뿐만 아니라 LCD 디스플레이 소자가 보편화하고 통신 기술이 발달하면서 스마트폰 같은 물건도 대중화될 수 있었다.

20세기 중반까지만 해도 컴퓨터는 곧 메인프레임-단말기 모델이었다.
컴퓨터라는 게 무진장 비싼 물건이고 자원이 귀하다 보니, 모든 처리는 중앙 컴퓨터에다 맡기고 각 사용자는 단말기로 서버에 접속해서 명령 프롬프트에서 서버의 기능을 사용하곤 했다. 그때는 컴퓨터는 대학, 연구소, 정부 기관, 군대의 전유물이었고, 개인용 컴퓨터라는 개념을 감히 떠올리기조차 쉽지 않았었다. (알파넷이 미국이 아닌 소련에서 발명되었다고 생각해 보자. 그게 오늘날의 인터넷으로 발전할 수 있었을까? -_-)

그러다가 20세기 말에는 PC가 대세가 되었다. 개인용 컴퓨터 하나만으로 어지간한 일은 다 할 수 있게 되었다. 비유하자면, 만원버스에 시달리면서 출퇴근하다가 번듯한 자가용이 생긴 셈.
PC의 사고방식으로는 소위 PC 통신은 어쩌다 한 번씩만 다른 컴퓨터에 접속하는 특별한 작업이며, 웹브라우저 역시 오피스 패키지처럼 별도로 구입해서 사용하는 특수한 프로그램일 뿐이다.

그 후 오늘날 대세라고 회자되고 있는 건 일명 클라우드 컴퓨팅이다. 개인용 컴퓨터가 무진장 작아지고 통신 인프라가 발달한 덕분에, 예전처럼 부족한 자원을 공유하려고 컴퓨터들을 연결하는 게 아니라 진짜 유비쿼터스 세상이 돼서 컴퓨터들을 연결한다. PC 통신 시절에만 해도 하이텔 단말기가 있었는데 오늘날의 스마트폰에 비하면 얼마나 격세지감인가!

전세계 컴퓨터가 다 인터넷에 연결되고 클라이언트와 서버의 구분이 무의미해지고, 궁극적으로는 (거의) 모든 작업이 웹 프로그램만으로 해결되고 모든 자료가 웹에 저장되는 세상이 온다. 예전에는 PC끼리 자료 전송을 위해서 플로피 디스켓이나 USB 메모리를 썼는데, 이제는 사용자의 로컬 컴퓨터나 스마트폰 그 자체가 플로피 디스켓이나 USB 메모리와 마찬가지가 된다는 뜻.

이걸 역시 자동차에다 비유하자면 이렇다. 사람이 직접 자가운전을 하니까 교통사고가 발생하고 도로가 막히고 여러 문제가 생기다 보니, 전세계 도로가 한데 통제되고 지능형 임대 자가용이나 궤도 교통수단이 생겨서 모든 사람들이 그걸 간단히 이용하는 형태가 된 셈이다.
물론 이게 온전히 실현되려면 시스템적으로나, 보안 쪽으로나 해결해야 할 문제가 많다.

Posted by 사무엘

아래 코드를 실행하면 놀랍게도..
입력된 숫자에 대한 팩토리얼 값이 출력된다. 단, 플랫폼은 x86 한정으로..;;
(뭐, 컴퓨터가 돌아가는 원리를 아는 사람이라거나 맨날 기계어 코드 들여다보는 게 직업인 사람이라면 전혀 새삼스러운 일이 아니겠지만)

비주얼 C++뿐만이 아니라 도스용 DJGPP로도 프로그램이 잘 동작하는 걸 확인했다. 둘 다 IA32 아키텍처인 건 동일하니까 이는 당연한 귀결.

int main(int argc, char* argv[])
{
 BYTE instrs[]={
  0x55,
  0x8B,0xEC,
  0x83,0xEC,0x08,
  0xC7,0x45,0xFC,0x01,0x00,0x00,0x00,
  0x8B,0x45,0xFC,
  0x89,0x45,0xF8,
  0xEB,0x09,
  0x8B,0x4D,0xF8,
  0x83,0xC1,0x01,
  0x89,0x4D,0xF8,
  0x8B,0x55,0xF8,
  0x3B,0x55,0x08,
  0x7F,0x0C,
  0x8B,0x45,0xFC,
  0x0F,0xAF,0x45,0xF8,
  0x89,0x45,0xFC,
  0xEB,0xE3,
  0x8B,0x45,0xFC,
  0x8B,0xE5,
  0x5D,
  0xC3
 };

 PVOID pv = instrs;
 int (*pfn)(int) = reinterpret_cast<int (*)(int)>(pv), y;
 while(1) {
  printf("? "); scanf("%d", &y); if(y<1) break;
  printf("%d\n", pfn(y));
 }
 return 0;
}

프로그래밍 언어의 인터프리터 내지 just-in-time 컴파일러를 만든다거나,
가상 기계 에뮬레이터를 만드는 것은 어렵지 않다.
결국 핵심이 뭐냐 하면 컴퓨터가 직통으로 실행하는 코드 자체를 실행 시간에 메모리에다 생성하는 건데,
함수 포인터가 가리키고 있는 게 바로 저런 것들이다.

물론, 위에서처럼 실행해야 할 코드가 완전히 고정돼 있는 경우라면
소스 코드에다 인라인 어셈블리를 집어넣으면 되겠지만, 그 코드는 데이터 영역에 들어가는 게 아니라 소스 코드(text) 영역에 그대로 포함되어 버리게 될 것이다.

위의 팩토리얼 함수는 물론 컴파일러가 생성해 준 코드를 복사한 것이다.
최적화를 안 한지라, 간단한 for 루프 하나밖에 없는 함수가 코드 길이가 꽤 길다.
최적화를 하고 나면 정상적인 함수 입출력 껍데기에 해당하는 코드조차도 거추장스러운지 생성되지 않아서
그걸 저렇게 따로 떼어내서 쓸 수가 없었다.

Posted by 사무엘

오늘날, 어떤 데이터(개념상 Document라고 불리는)를 메모리에 완전히 읽어들여서 사용자가 그 데이터를 편집할 수 있는 업무용 프로그램에는... 거의 필수로 undo 기능이 있다.
이건 우리가 잘 실감을 못 해서 그렇지 사용자에게 심리적으로 굉장한 안정감을 주는 편리한 기능이다. 뭘 잘못해서 망쳐 놓더라도, '미리 저장 -> 지금 문서를 저장 안 하고 예전 문서를 다시 불러오기' 같은 뻘짓을 안 해도 Ctrl+Z만 누르면 만사 OK.

소프트웨어 GUI 가이드라인 교과서를 보면, 소프트웨어는 사용자에게 '용서'(forgiveness)라는 덕목을 발휘해야 한다는 말이 나온다. 사용자가 아무리 바보짓을 하더라도 이를 최대한 추스리고 수습하고 원상복귀 할 수 있어야 한다는 뜻.
컴퓨터 프로그램은 기독교의 하나님 같은 존재가 아니다. “자유 의지가 있으니, 하늘나라든 지옥이든 선택에 따른 책임도 전적으로 네 몫이다” 주의가 아니다. 그러니 인간의 삶에도 Undo가 있으면 참 좋을 텐데 현실은 그렇지 못하니 참으로 안습이다. 오히려 '말은 하고 못 줍는다', '엎질러진 물', '소 잃고 외양간 고친다' 같은 냉정한 속담만이 있을 뿐이다.

잡설이 길어졌다만,
역사적으로 Undo라는 개념이 허접하게나마 가장 일찍부터 존재한 분야는 그래픽 프로그램이었다.
걔네들은 원래부터 문화가 좀 독특해서 마우스의 비중이 매우 높으며, 우클릭이 Context menu의 의미로 쓰이지도 않을 정도이다.
그리고 근본적으로 마우스라는 게 키보드보다 실수를 훨씬 더 하기 쉬운 입력 장비이고, 한 번의 동작으로 수백· 수천 개의 픽셀이 한꺼번이 바뀔 수 있기 때문에 Undo가 없으면 안 된다.

문득 든 생각: 그래픽 프로그램을 이용해서 마우스로 Freehand drawing을 하는 도중에 bksp 키를 누르면.. 직전의 수 픽셀 단위로 곡선을 철회하는 기능이 있으면 좋을 것 같다. 정교한 도트 노가다 할 때 유용할 것 같다. 보통 Ctrl+Z 누르면 그렸던 선 전체가 한 방에 날아가 버리잖아?

물론 Undo라는 건 그렇게 쉽게 구현할 수 있는 기능이 아니며 메모리 오버헤드가 크다.
더구나, 과거에 Undo 기능이 있던 프로그램은 딱 한 단계밖에 취소가 되지 않았었다. Ctrl+Z를 누르면 직전 작업을 취소했다가, 다시 살렸다가 하기만을 반복할 뿐이었다. (메모장.. 정확히 말하면 윈도우 운영체제의 에디트 컨트롤도 딱 그 수준의 1단계 Undo를 지원한다.)
수십, 수백 단계의 작업을 고스란히 취소하고 취소 내역을 다시 철회(redo)까지 하는 command history 수준의 multi-level undo 기능은 1990년대까지만 해도 MS 워드 같은 소수의 상업용 대형 프로그램에서나 볼 수 있었다.

이런 프로그램은 Document의 내용을 변형하는 모든 명령들이 체계적으로 분류가 돼 있다. 그래서 편집 메뉴를 열어 보면 단순히 '실행 취소 / 재실행'이라고만 돼 있는 게 아니라 '삭제 취소 / 취소된 자동 완성 재실행'처럼, 무슨 명령이 직전에 취소되었고 무엇을 재실행할지 명령의 이름까지 메뉴에 친절하게 표시돼 있기도 한다.
그 반면, Undo/redo를 염두에 두지 않고 Document를 고치는 코드가 제멋대로 섞여 있던 프로그램에다가 어느덧 갑자기 multi-level Undo/redo 기능을 최초로 추가할 일이 생겼다면 아마 십중팔구 코드를 다 갈아엎는 대공사를 해야 할 것이다.

컴퓨터의 성능이 열악하던 도스 시절엔, Undo와 Redo가 모두 존재하는 프로그램은 매우 드물었다.
아래아한글 1.x는 좀 특이한 경우인데, 줄 끝까지 지우기· 단어 지우기 같은 몇몇 지우기 명령으로 인해 지워진 텍스트만을 1회에 한해 되살리는 Undo 기능이 있었다.
그 후 아래아한글 2.0에서 97은 그 Undo의 단계가 3회로 늘었을 뿐이었다. 내 기억이 맞다면, 이 기능은 최근 3회의 주요 지우기 단축키(메뉴에 등재되지 않은)에 의해 지워졌던 텍스트 중 하나를 골라서 커서가 있는 곳에다 삽입해 주는 기능에 불과했다. 원래 있던 위치에 되돌려 놓는 것도 아니고... -_-

Ctrl+X(오려두기)야 본문이 클립보드에 고스란히 들어가 있으니 별도의 Undo 버퍼에다 저장할 필요가 없고,
Ctrl+E(지우기)로 지워진 텍스트는 의도적으로 되살리기가 전혀 되지 않는다고 도움말에 친절하게 안내까지 돼 있었다. ^^;;
그것 말고 문서나 표 레이아웃을 잘못 건드려서 망쳤다거나 하는 더 중요한 기능에 Undo 따위는.. “Undo 뭥미? 그거 먹는겅미? 우걱우걱...”이었다. 그냥 이전 문서를 새로 불러오는 수밖에..
이런 불편한 프로그램을 옛날 사람들은 어떻게 쓰고 지냈을까?

그래서 아래아한글 2002는 256단계 undo가 지원된다고 잔뜩 광고를 하고 다녔었다. MS 제품들은 진작부터 지원한 기능인데도 말이다. 하긴, 그것 말고도 글자 크기 제한이 드디어 없어지고 글자색 제한이 없어진 것도 개인적으로 무척 마음에 들긴 했다. better late than never이다.

<날개셋> 한글 입력기의 편집기 프로그램은 1.x와 2.x 시절에는 Undo 비슷한 기능도 전혀 없었다. 3.0에 가서야 32단계의 multi-level undo가 추가되기는 했으나... 글자 하나, 한글 낱자 하나 입력되는 모든 단계가 histroy에 기록된지라 실용성이 시원찮았다.
그것이 지금의 형태로 개선되 것이 4.2 버전부터이다. 연속된 에디팅 동작뿐만이 아니라 불연속적인 에디팅 동작을 한 history로 통합하는 기능까지 추가되어, 여러 블록을 동시에 삭제한 것이나 Replace All 명령을 내린 것도 한 번에 취소가 가능해졌다.

사실 <날개셋> 편집기의 에디팅 엔진은 아직 좀 효율적이지 못한 구석이 있다. Undo/redo 명령을 내리면 그 부분이 아무리 사소하더라도 문서 전체의 레이아웃을 싹 다시 하고, 화면 전체를 새로 그린다. 그렇기 때문에 수~수십 MB짜리 텍스트를 연 뒤에 Ctrl+Z를 꾹 누르고 있기가 겁난다. 본인은 이 프로그램을 만든 사람이고 프로그램의 내부 디테일이 어떤지를 잘 알기 때문에 그러기가 더욱 꺼려진다.

2004년에 만든 3.0 이래로 그냥 brute-force 알고리즘을 그 부분만은 아직까지 최적화를 못 했다. 한글 입력 부분과 직접적인 관계가 없고, 딱히 크게 티가 나는 부분이 아니다 보니 지금까지 방치되어 온 것이다. <날개셋> 한글 입력기 6.0의 다음 버전은 이 부분을 개선하여, 이제 안심하고 Ctrl+Z를 꾹 누를 수 있는 프로그램이 될 것이다.

Undo 기능과 관련된 얘깃거리를 두 가지만 더 꺼내고 글을 맺겠다.

첫째, 예전에 한번 언급한 적이 있듯이, 프로그램들이 Undo는 거의 예외 없이 Ctrl+Z로 정착해 있는 반면 Redo는 단축키가 프로그램마다 일치하지 않는 경우가 있다. MS의 관행은 Ctrl+Y인 듯하지만 Ctrl+Shift+Z인 프로그램도 있다.
아래아한글은 도스 시절에 Ctrl+Y가 지우기 명령의 일종이기 때문에 주의해야 한다. Redo를 생각하고 눌렀다가는 Redo는커녕 텍스트를 지우면서 후폭풍으로 기존 Undo history까지 모두 날려 버리기 때문이다!

둘째, Multi-level undo를 잘 구현한 프로그램이라면, 문서의 modified 플래그 처리도 잘 되어야 한다. 무슨 말이냐 하면, 문서를 저장했다가 어딘가를 건드린 후(= modified 플래그 켜짐), Ctrl+Z를 눌러 그 작업을 철회한다면 문서는 당연히 다시 unmodified 상태로 바뀌어야 한다.
그리고 반대로, 저장한 문서에 대해서 Undo를 해서 modified 상태가 됐더라도, 그걸 다시 Redo로 철회했다면 문서는 unmodified로 되돌아가야 한다. 논리적으로 당연한 얘기이다. <날개셋> 편집기는 multi-level undo가 처음으로 지원되기 시작한 3.0 때 이거 하나는 아주 철저하게 잘 구현해 뒀다.

비주얼 C++ 에디터, 그리고 국산 에디터인 EditPlus는 이 플래그 처리가 잘 된다. MS 오피스 제품도 마찬가지.
그러나 AcroEdit는 이게 되지 않아서 불편하며, 아래아한글도 2007은 처리가 되지 않는다. WordPad 역시 지원 안 함.

Undo나 Redo 같은 Command history 기능은 문서의 modified 상태까지 예전으로 되돌리는 명령이기 때문에 문서를 건드리는(modified 플래그를 언제나 켜는) 동작보다 상위에서 돌아가야 할 텐데, 이 점을 미처 고려를 못 한 것 같다. Undo나 Redo나 문서를 고치는 기능인 건 매한가지이기 때문에 무조건 modified 상태로. ^^

Posted by 사무엘