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

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

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

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

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

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

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

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

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

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

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

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

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

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

Posted by 사무엘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Posted by 사무엘

등산 이야기만 몇 콤보로 계속되는 와중에 오랜만에 또 프로그래밍 얘기를 좀 하겠다.

본인은 예전에 열차나 건물(대표적으로 영화관)에서 좌석 배당 알고리즘이 어떻게 될까 궁금해하면서 이와 관련된 썰을 푼 적이 있다. 그리고 이와 비슷한 맥락에서, 점을 최대한 균등하게 순서대로 뿌리는 ordered 디더링의 가중치, 다시 말해 흑백 음영 단계 테이블은 어떻게 만들어지는 것일까 하는 의문을 제기했다. 그 당시엔 의문 제기만 하고 더 구체적인 해답을 얻지는 못했다.

그래픽 카드가 천연색을 표현할 수 있게 되면서 이제 컴퓨터에서 선택의 여지가 없는 '생존형'(?) 디더링의 필요성은 전무해졌다. 비디오보다는 아주 열악한 네트워크 환경에서 그래픽의 용량을 극도로 줄일 필요가 있을 때에나 특수한 용도로 제한적으로 쓰이는 듯하다. 색상뿐만 아니라 해상도도 왕창 올라가면서 이제는 글꼴의 힌팅조차 존재감이 많이 위태로워졌을 정도이니 세상이 참 많이도 변했다.

하지만 ordered 디더링이라는 건 점을 평면이나 공간에 최대한 골고루 질서정연하게 뿌리는 순서를 구하는 문제이다 보니, 계산 알고리즘의 관점에서는 실용적인 필요성과는 별개로 굉장히 흥미로운 문제인 것 같다.

흑과 백이 정확하게 반반씩 있는 50% 경우를 생각해 보면, 당연한 말이지만 흑과 백은 대각선으로 엇갈린 형태로 존재한다. 수평선이나 대각선 형태가 아니다. ▤나 ▥가 아니라 ▩에 가까운 것이다.

그러므로 아주 간단한 2*2 크기의 음영이라면
(1 4)
(3 2)

가 된다. 수평선인 (1 2)(3 4)나 수직선인 (1 4)(2 3)이 아니라, (1 4)(3 2)라는 것이다.
그러니 태극기의 괘는 패턴이 (3 5)(4 6)이기 때문에 수직선에 가깝다. 그리고 이거 무슨 승용차에서 운전사가 있을 때와 없을 때, 좌석의 위치별로 상석에서 말석 순서 테이블과 비슷하다는 느낌도 든다.. -_-;;

시작점인 1은 언제나 좌측 상단으로 고정해서 생각해도 일반성을 잃지 않는다. 그럼 다음 2의 위치는 1에서 가장 멀리 떨어진 대각선이므로 역시 자동으로 결정된다.
그럼 (1 4)(3 2) 대신 (1 3)(4 2)는 불가능한 방향이 아니긴 하지만, 관례적으로 2 다음에 위쪽이 아니라 왼쪽에다가 3을 찍는 걸 선호하는 듯하다.

자, 그럼 얘를 조금 더 키워서 4*4 음영은 어떻게 될까?

(1 ? 4 ?) - (1 ? 4 ?) - (1 13 4 16)
(? * ? *) - (? 5 ? 8) - (9 5 12  8)
(3 * 2 ?) - (3 ? 2 ?) - (3 15 2 14)
(? * ? *) - (? 7 ? 6) - (11 7 10 6)

테이블의 크기가 딱 두 배로 커지면 새로운 숫자들은 언제나 기존 테이블의 틈바구니에 삽입된다. 그래야 균형이 유지될 수 있다.
각각의 틈바구니에 대해서 원래 칸의 대각선 아래 (+1, +1), 그리고 바로 아래 (0, +1), 바로 옆 (+1, 0)의 형태로 (5~8), (9~12), (13~16)이 매겨진다. 그랬더니 무슨 짝수 마방진 같은 복잡난감한 퍼즐이 채워졌다.

컴퓨터그래픽에서 실용적으로 가장 많이 쓰이는 음영은 8*8 크기이다. 모노크롬/16색 시절에 단색 패턴 채우기 함수들은 전부 8*8 패턴을 사용했다. 그러므로 얘는 음영을 64단계까지 표현할 수 있다.

8*8 패턴은 역시 4*4 패턴의 틈바구니에 삽입된다. 16 다음에 17이 들어가는 위치는 어디일까? 1과 2 사이에 5가 삽입되었던 것처럼 1과 5의 사이에 17이 삽입된다. 그리고 패턴 크기의 절반인 4픽셀 단위로 n, n+1, n+2, n+3이 (x,y), (x+4,y+4), (x,y+4), (x+4,y)의 순으로 번호가 매겨지는 건 변함없다.

거의 난수표 수준의 복잡한 테이블이 완성됐다. 규칙성이 뭔가 감이 오시는지? 그래픽 라이브러리들은 마치 삼각함수 테이블만큼이나 미리 계산된 디더링 테이블을 내장하고 있다.
그런데 이런 식으로 16*16 256단계 음영 테이블은 어떻게 만들 수 있을까?
각 구간을 순서대로 각개격파하는 게 아니기 때문에 분할 정복이나 재귀호출은 아닌 것 같다.

이런 숫자를 생성하는 코드를 작성하기 위해, 먼저 다음과 같은 변수들을 클래스나 전역변수 형태로 정의하자.

int mtrix[N][N]; int cs, ce;
static const POINT PTR[4] = {
    {0,0}, {1,1}, {0,1}, {1,0}
};

void Draw(int y, int x, int delta)
{
    for(int i=0;i<4;i++)
        mtrix[y+PTR[i].y*delta][x+PTR[i].x*delta]=ce++;
}

Draw는 특정 지점에서 n 간격으로 (0,0), (n,n), (0,n), (n,0)의 순으로 ce부터 ce+3까지 번호를 매겨 주는 역할을 한다.
이를 이용하면 2*2의 경우는 Draw(0, 0, 1)을 통해 간단히 만들 수 있다.

void Case2()
{
    cs=2; ce=1; memset(mtrix, 0, sizeof(mtrix));
    Draw(0, 0, 1);
}

앞서 살펴보았던 4*4는 이런 형태가 되고..

void Case4()
{
    cs=4; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0;a<4;a++)
        Draw( PTR[a].y, PTR[a].x, 2 );
}

더 복잡한 8*8은 Draw를 어떤 순서대로 호출해야 할지 따져보면 결국 규칙성이 도출된다.
그렇다. 2중 for문이 만들어지며, 16*16은 3중 for문이 될 뿐이다.

void Case8()
{
    cs=8; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0; a<4; a++)
        for(int b=0; b<4; b++)
            Draw(PTR[a].y + PTR[b].y*2, PTR[a].x + PTR[b].x*2, 4);
}

void Case16()
{
    cs=16; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0; a<4; a++)
        for(int b=0; b<4; b++)
            for(int c=0; c<4; c++)
                Draw(PTR[a].y + (PTR[b].y<<1) + (PTR[c].y<<2),
                    PTR[a].x + (PTR[b].x<<1) + (PTR[c].x<<2), 8);
}

바로 이것이 우리가 원하는 정답이었다. 식을 도출하고 보니 규칙은 허무할 정도로 너무 간단하다. n중 for문을 재귀호출이나 사용자 스택 형태로 정리하는 건 일도 아닐 테고.
이 정도면 평면이 아니라 3차원 공간을 점으로 촘촘하게 채우는 것도 생각할 수 있다. PTR 테이블은 (0,0,0), (1,1,1)부터 시작해서 정육면체의 꼭지점을 순회하는 순서가 되므로 크기가 8이 될 것이다.

그리고 참고로 8*8 음영 행렬은 아래의 코드를 실행해서 생성할 수도 있다.

int db[8][8];
for (int y = 0; y < 8; y++)
    for (int x = 0; x < 8; x++) {
        int q = x ^ y;
        int p = ((x & 4) >> 2) + ((x & 2) << 1) + ((x & 1) << 4);
        q = ((q & 4) >> 1) + ((q & 2) << 2) + ((q & 1) << 5);
        db[y][x] = p + q + 1;
    }

내가 처음에 for문을 써서 작성한 코드는 함수로 치면 일종의 매개변수 함수이다. (t에 대해서 x(t)는 얼마, y(t)는 얼마)
그런데 저건 그 매개변수 함수를 y=f(t) 형태로 깔끔하게 정리한 것과 같다. 식이 뭘 의미하는지 감이 오시는가?

이런 걸 보면 난 xor이라는 비트 연산에 대해 뭔가 경이로움, 무서움을 느낀다.
덧셈이야 "니가 아무리 비비 꼬아서 행해지더라도 까짓거 덧셈일 뿐이지. 결과는 다 예측 가능해" 같은 생각이 드는 반면, xor에다가 비트 shift 몇 번 하고 나면 도저히 예측 불가능한 난수 생성 알고리즘이 나오고 암호화/해시 알고리즘이 만들어지기 때문이다. 지극히 컴퓨터스러운 연산이기 때문에 속도도 왕창 빠르고 말이다.

2002년에 우리나라에서 열렸던 국제 정보 올림피아드에서도 'xor 압축'이라는 제출형 문제가 나온 적이 있다. 임의의 비트맵 이미지가 주어졌을 때, 이걸 사각형 영역의 xor 연산만으로 생성하는 순서를 구하되, 연산 수행을 최소화하라는 게 목표이다.

한 점에 대해서 가로/세로로 인접한 점 3개를 추가로 조사하여 흑백 개수가 홀수 개로 차이가 나는 점을 일종의 '모서리'로 간주하여 각 모서리들에 대해 plane sweeping하듯이 xor을 시키면 그럭저럭 괜찮은 정답이 나온다. 단, 이것이 이론적인 최적해와 동일하다는 것은 보장되지 않는다. 그렇기 때문에 문제가 제출형으로 출제된 것이다.

재미있는 것은 모서리 판정도 xor로 하면 간단하게 해결된다는 것이다.
(pt[x][y]==1)^(pt[x+1][y]==1)^(pt[x][y+1]==1)^(pt[x+1][y+1]==1) 같은 식. 이유는 조금만 생각해 보면 알 수 있다.

난 Bisqwit이라는 필명을 쓰는 이스라엘의 무슨 괴수 그래픽 프로그래머의 코딩 동영상에서 저 코드가 흘러가는 걸 발견하고 가져왔다. 흐음..;; Creating a raytracer for DOS, in 16 VGA colors 뭐 이런 걸 올려서 시청자들을 경악시키는 분이긴 한데, 물론 레알 16비트 도스용 Turbo C나 QuickBasic 컴파일러로 저런 걸 돌린다는 소리는 아니다. 그건 알파고 AI를 개인용 데스크톱 컴퓨터로 돌리는 것만큼이나 불가능한 일이니 너무 쫄지 않아도 된다. (VGA 16색인 건 맞지만 메모리와 속도는 그 옛날 기계 기준이 결코 아님.)

엑셀에다가 저 16*16 음영 테이블을 입력한 뒤, 수식을 이용해서 숫자 n을 입력하면 그에 해당하는 음영이 생성되게 워크시트를 만들어 보니 재미있다. 이번에도 흥미로운 덕질을 했다.

Posted by 사무엘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Posted by 사무엘

※ 컴퓨터 & 프로그래밍

1.
예전에 본인은 시스템 종료 중에라도 사용자가 무슨 동작을 취하면, 컴을 아주 꺼 버리는 시스템 종료가 아니라 그 뒤 '재시작'으로 종료 모드를 바꾸는 기능이 있으면 좋겠다는 제안을 한 적이 있다. 그것과 비슷한 제안인지도 모르겠는데, 또 하나 아이디어를 내자면 이렇다. 사용자가 한동안 컴퓨터를 건드리지 않아서 모니터가 꺼지거나 컴퓨터가 절전· 최대 절전· 종료 등으로 바뀌게 되면, 그 모드로 진입하기 전에 화면에 10초나 5초 정도 카운트다운을 좀 띄웠으면 좋겠다.

프레젠테이션을 할 때처럼 화면을 빤히 보고 있으면서 키보드· 마우스만 안 건드리고 있는데 화면이 갑자기 꺼져 버려서 당황한 적이 여러 번 있었다. 화면 보호기 정도는 카운트다운 없이 바로 진입해도 상관 없겠지만 아예 하드웨어적인 변동이 생기는 저런 모드는 예고가 있으면 좋겠다.

2.
동영상 엔진인 '코덱'과 과거의 컴퓨터 통신 장비인 '모뎀'이 정확히 같은 조어법에 의해 거의 같은 구조의 이니셜을 가진 단어이구나.

3.
식당에서 주문을 한 뒤에야 "아 손님, 죄송하지만 재료가 떨어져서 그 메뉴는 지금 제공이 안 됩니다" 이런 메시지를 받으면 허탈하잖아. 애초에 메뉴판에 그런 메뉴는 disable된 상태로 시각 피드백이 있으면 좋겠다.

4.
공동 작업을 하는 코드의 명칭에 영어 스펠링이 틀린 게 많아서 작업에 지장을 적지 않게 받은 적이 있었다. 검색이 안 되기 때문이다. 이쯤에서 분명 availableItem이런 단어가 있는 걸 봤었는데 나중에 보니 avalible이라고 돼 있는 식.
이건 당장 버그나 성능 같은 동작과 직접적인 관련이 있지는 않지만, 그래도 또 다른 형태의 민폐이다. 도서관으로 치면, 책을 보고 나서는 자기 분류 코드상으로 있어야 할 곳이 아닌 엉뚱한 곳에다 책을 꽂은 것과 같다. "잘못 꽂힌 책은 없는 책과 같습니다. 정리는 사서가 알아서 할 테니까 열람하신 책은 그냥 여기에 놔 두세요" ;;;;

5.
관광 가이드를 매뉴얼과 스케줄 대로 승객들을 안내하는 컴퓨터 프로그램에다가 비유한다면, 이 사람이 수행하는 프로그램의 소스 코드는 정말 그야말로 try ... catch문으로 빽빽이 무장하고 있어야겠구나 하는 생각이 들었다.
누군가가 갑자기 아플 때, 뭔 물건을 놔 두고 왔을 때, 여권을 잃어버렸을 때, 긴급한 사고가 발생했을 때, 일행 중 일부가 없어져서 못 찾을 때 등등.. 그 어떤 예외 상황에서도 패닉과 스케줄 펑크를 최소화하는 방향으로 의연히 대처가 가능해야겠다.

6.
Windows 환경에서 응용 프로그램이 자기 영역으로 사용할 수 있는 메모리 주소는 64KB 이상부터이다. NULL 포인터인 0자체뿐만이 아니라 첫 64KB는 가상 메모리 영역 설계 차원에서 봉인되어 있으며, 이 주소에 메모리를 읽거나 쓰는 건 무조건 에러가 난다. 사실, 0 자체뿐만 아니라 64KB 정도까지는 막혀 있어야 NULL포인터 자체뿐만 아니라 NULL로부터 구조체 멤버를 참조한 포인터도 에러로 처리될 수 있을 것이다. ((POINT *)NULL)->y처럼.

아울러, 과거의 Windows 9x는 이보다 제약이 더 커서 64KB가 아니라 상위 4MB까지가 추가로 막혀 있었다. 64K부터 4M까지의 영역은 16비트 프로그램(도스용 & Windows용 모두)이 사용한다. (☞ 이에 대한 더 자세한 설명)

이런 이유로 인해 전통적으로 32비트 Windows 프로그램들은 시작 주소(preferred base)가 딱 4MB로 맞춰지곤 했다. NT 계열에서는 꼭 4MB가 아니라 64KB 이상 아무 지점이어도 상관이 없지만, 4MB 이상이어야 윈도 9x와 NT계열에서 모두 실행 가능하기 때문이다.

그런데 이건 오늘날까지도 하드디스크가 C로 시작하는 디스크 드라이브 관행과도 정확히 일치하는 것 같다.
플로피 디스크가 완전히 없어졌음에도 불구하고 A, B 드라이브는 사실상 결번으로 남아 있으니 말이다. 요즘은 하다못해 USB 메모리 드라이브를 거기에다 할당해도 될 것 같은데!

※ 알고리즘

7.
longest common subsequence를 구하는 문제와 longest increasing subsequence를 구하는 문제는 서로 관련이 있는 무척 흥미로운 문제인 것 같다.
가만히 생각해 보니, 후자는 임의의 sequence와, 그 입력을 오름차순으로 정렬한 sequence와의 longest common subsequence를 구하는 것과 같다. 그러므로 후자는 전자 문제로 다항 시간 만에 변환 가능한 special case이다.

두 문제는 일단 다이나믹 프로그래밍으로 O(n^2)의 복잡도로 풀 수 있지만, 더 작고 특수한 케이스인 후자는 O(n log n)의 해법도 있다.
전자 문제는 문장의 정확도를 구하는 알고리즘, 소스 코드의 diff 툴 등 활용되는 분야가 굉장히 많다. 지금은 어떤가 모르겠는데 내 때에는 국제 정보 올림피아드의 첫째 날 1번 문제가 해법이 이 형태로 귀착되는 경우도 종종 있었다. 1999년도의 꽃병 문제는 대놓고 저런 타입이었고, 2000년도의 palindrome 문제도 자신과 자신을 역순으로 뒤집은 단어와의 longest common subsequence를 구하는 것과 동일하다.

8.
엑셀에서 파이 모양 차트를 그리면 아이템별로 파랑, 빨강, 주황 등 알록달록한 색깔이 배당되어 차트가 그려진다.
그런데 최초의 색깔인 파랑부터 아이템 N에 이르기까지, 색깔을 선별하는 방식이 과연 무엇일까?
Office 2003까지는 뭔가 보라색 위주의 우중충하고 칙칙한 색깔 위주였는데 2007부터는 그래도 예전보다 훨씬 더 세련되게 바뀌었다.

이건 뭔가 RGB나 hue 같은 색공간에서 최대한 균등하게, 마치 흑에서 백으로 디더링 픽셀을 하나씩 채워 나가듯이 색깔을 뽑아낸 것 같다(관련 링크). 그 구체적인 알고리즘이 궁금하다.
그리고, 이런 픽셀 채우기 문제의 domain을 2차원 평면이 아니라 3차원 공간으로 확장하면 문제의 난이도가 어찌 되는지도 궁금하다.

※ 자동차

9.
자동차 차량 취급 설명서의 각종 선택사양에만 적용되는 설명들은 C/C++ 코드에서 #if #endif 전처리기에 대한 아주 좋은 예시라 여겨진다.

10.
오늘날 "일찍 나는 새가 벌레를 잡는다"보다 훨씬 더 현실적으로 와 닿는 말은 "일찍 움직이는 차가 주차 자리를 차지한다"라고 해도 과언이 아닐 것이다.

※ 기타 미분류

11.
공항 안에 개인 물품 보관함 같은 게 있으면 단독 여행 시에 유용하겠다는 생각이 든다. 이곳과 계절이 크게 다른 지역을 여행 갈 때 지금 입은 옷을 보관해 놓는다거나, 반입 금지 내지 무게 제한에 걸린 물건을 귀국 때까지 임시로 보관할 수 있게 말이다. 물론 후자의 경우는 당사자가 보관함까지 갔다가 돌아오는 게 곤란하니, 추가 비용을 부담해서 보관 대행을 맡길 수 있어야 하겠다.

12.
비행기와 열차의 큰 차이:
열차는 출발 15분 전부터 승강장으로 입장이 가능한 반면, 비행기는 출발 15분 전에 탑승이 종료된다는 것이다.
그리고 여담인데, 내 경험상 인천 공항을 출발한 비행기는 견인차에 끌려 터미널을 떠난 순간부터 활주로에 진입하여 이륙을 시작할 때까지도 거의 정확히 15분이 소요된다.

13.
"바탕체 레귤러"라는 서체 이름을 보고는 바탕체 볼드가 아니라
"바탕체 라지"가 순간적으로 먼저 떠올랐다.
요즘 커피를 너무 많이 마셨나 보다....? =_=;;
하긴, 아메리카노가 생각이 안 나서 순간 "아프리카노요"라고 주문을 했다는 사람 얘기도 있으니..;;

14.
몇 년 전부터 우리나라에서는 우측통행, 도로명 주소 등 일상생활과 직접적인 관계가 있는 여러 규범이 바뀌었으며, 이런 차원에서 단위도 비표준 단위가 통상적으로 쓰이던 곳까지 SI 단위가 강제 추진되었다.
고기의 무게는 오래 전부터 '근'이 거의 전멸하고 100그램 단위로 다 정착을 한 것 같지만 여전히 오락가락하는 곳은 부동산에서 다루는 건물이나 땅의 면적이다.

그런데 내가 보기에도 '1평'을 '3.3제곱미터'로 바꿔서 실생활에서 유리한 게 없다. 부자연스러울 뿐만 아니라 음절수도 너무 많아서 발음하기가 불편하다. 바꿀 거면 사람이 실제로 생각하는 넓이의 덩어리도 1제곱미터나 10제곱미터 단위로 업데이트가 돼야 할 텐데.
참, 그나저나 화면의 크기를 표기할 때 으레 쓰이는 '인치'는 센티미터로 바뀌기라도 했는지 궁금하다. 여기도 평이나 근 만만찮게 좀 이상한 단위가 관습적으로 쓰여 온 곳이니까 말이다.

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

오랜만에 알고리즘 얘기.
정보 올림피아드 공부를 한 적이 있는 분이라면, 제목에 등장한 용어가 아주 친숙할 것이다. 앞으로 LIS라고 줄여 일컫겠다.

어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 것이 목표이다.
가령, {3, 2, 1, 4, 5, 2, 3, 5, 3, 6, 4} 같은 수열이 있으면
1, 2, 3, 5, 6이 가장 긴 solution이 된다. {3, 2, 1, 4, 5, 2, 3, 5, 3, 6,  4} OK?
정렬만큼이나 알고리즘 기초를 다지는 데 도움이 되는 흥미로운 문제이다.

이 문제는 간단하게 생각하면 다이나믹 프로그래밍(동적 계획법)을 적용한 O(n^2)의 시간 복잡도로 풀 수 있다. 작은 set에 대한 답을 구한 뒤 그 결과를 저장해 놓고, 그 set의 크기를 차츰 키우면서 작은 solution들을 종합하여 최종 solution을 구하는 방식.

매 원소에 대해서 자기까지 왔을 때 존재 가능한 subsequence의 최대 길이와, 그 subsequence 상에서 자기 앞 원소의 위치를 적어 놓는다. 그러면 다음 원소 차례가 됐을 때는 자기 앞 원소들을 일일이 탐색하여, 자기보다 값이 작으면서 잠재적 subsequence 길이가 최장으로 설정되어 있는 원소에다 자기를 연결해 놓는다. 물론 자기의 subsequence 길이는 1 증가시켜 놓고 말이다.

위와 같은 표가 완성되고 나면, 그 후 개수가 5로 가장 큰 9번 오프셋부터 시작하여 이전 참고 위치를 따라 역추적을 하면 LIS가 구해진다.

그런데 이걸 구하기 위해서 꼭 O(n^2)이나 되는 계산량이 필요할까? 더 효율적인 알고리즘은 없을까?
답은 ‘있다’이다. 물론 메모리 복잡도도 아까처럼 O(n)으로 완전히 동일하고 말이다.
이 새로운 알고리즘은 역시 길이가 n인 버퍼에다가 작업을 하는데, 버퍼의 용도가 아까와는 살짝 다르다.

이 버퍼 A[i](1<=i<=n)의 의미는, 길이가 i인 LIS를 구한다고 쳤을 때 존재 가능한 가장 작은 LIS 마지막 원소(와 그 원소의 위치)이다. 즉, 이 버퍼는 구해진 LIS의 길이만큼만 사용된다.

위의 예제 수열에서 매 원소가 들어올 때마다 버퍼는 다음과 같이 바뀌게 된다. 뒤에 새로운 원소가 추가되거나 이미 있는 값의 업데이트만 발생하지(O(1)), 배열 원소들을 전부 하나씩 밀어야 하는 삽입이나 삭제(O(n))가 발생하지는 않음을 염두에 두기 바란다.
3: 3
2: 2
1: 1
4: 1 4
5: 1 4 5
2: 1 2 5
3: 1 2 3
5: 1 2 3 5
3: 변화 없음
6: 1 2 3 5 6
4: 1 2 3 4 6

즉, 버퍼가 가리키고 있는 것은 각 길이별로 가장 작은 수일 뿐이다. 그러나 버퍼가 가리키는 순서대로 배열을 참조하면 수열이 언제나 오름차순, 즉 정렬이 돼 있다는 게 보장된다.
최소값을 갱신할 위치를 찾는 것은 이분 검색(binary search)으로 할 수 있다. 이 덕분에 작업이 O(n^2)에서 O(n log n)으로 줄어들 수 있게 된다. 정확하게 말하면 O(n log k)(k는 LIS 길이)이니 더욱 빠르다. worst case로 증가 수열을 만들 수가 없는 내림차순 수열을 던져 주면, 거의 O(n)이나 다름없는 속도로 금방 실행이 끝난다는 뜻이다.

물론, 이 버퍼에는 각 길이별로 가장 작은 증가 수열을 구하는 힌트만 들어있을 뿐, 가장 긴 LIS를 추적하는 정보는 전혀 들어있지 않다. 그렇기 때문에 추적 순서는 역시 별도의 배열에다 따로 보관해 놔야 하며 이 역시 그리 어렵지 않게 구현할 수 있다. 심심하신 분은 이 알고리즘을 직접 코딩해 보기 바란다.

정보 올림피아드를 공부하던 시절엔 이런 유형의 문제도 재미있었다. 뭐, 본인은 머리싸움에 쥐약인 타입인지라 경시 부문에서는 별 재미를 못 보고, 대박은 공모 부문에서 다 냈지만 말이다.

- 양수와 음수가 뒤섞인 n개의 수열이 있을 때 합이 가장 큰 구간을 O(n) 시간 만에 구하기
- 위와 비슷한 예로, 0.x와 n.x가 뒤섞인 n개의 수열이 있을 때 곱이 가장 큰 구간을 역시 O(n) 시간 만에 구하기
- x*y 2차원 배열이 있을 때, 이런 조건을 만족하는 가장 넓은 면적을 구하기 (1999년도 IOI의 공항 건설 부지 찾기 같은)

알고리즘이라는 게 OR(operations research)과 밀접한 관계가 있는 것 같다. 선형 계획법, 동적 계획법 같은 개념도 원래는 그 분야에서 유래되었기 때문에 용어에서 그다지 전산학적인 어원은 찾을 수 없다.
덧. algorithm인데 왜 다들 알고리듬이라고 적지 않고 알고리즘(=algorism?)이 보편화해 있는 걸까?

Posted by 사무엘