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

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

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

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

열차의 승차권을 구입하면 좌석은 어떤 식으로 배당될까?
객차 하나당 좌석은 차량에 따라 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 사무엘

※ 들어가는 말

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

정렬은 문제의 목표가 너무나 명확하고 실용적이며, 다양한 관점에서 문제의 접근이 가능하고 좋은 알고리즘과 나쁜 알고리즘의 차이도 아주 드라마틱하게 알 수 있기 때문에... 예로부터 그 특성과 해법이 연구될 대로 연구되어 왔다. 시간 복잡도 관념이 없던 초짜 프로그래머가 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 사무엘

이 광근 교수는 프로그램의 정적 분석 분야에서는 아마 우주괴수급의 전문가가 아닌가 여겨지는 분이다.
카이스트 교수로 첫 부임했다가 2003년부터 서울대로 이직했다. 학부 출신 역시 서울대. 1983년에 입학 당시 자연과학 단과대 수석을 차지했으며, 재학 성적 역시 내내 최상위권이던 수재였다.
사진을 보면 알겠지만 이 교수는 상당한 동안이고 학생 시절 모습이 어땠을지가 상상이 된다.

개교 초창기부터 딱부러지게 전산학과가 있었던 카이스트와는 달리, 서울대는 198, 90년대엔 이과에 속한 계산통계학과와 공과에 속한 전자계산기공학과로 컴퓨터 쪽 학과 계열이 므흣하게 나뉘어 있었다. 통합된 컴퓨터공학부라는 게 생긴 것은 1990년대 말 내지 21세기에 들어와서이다. 덧붙이자면, 연세대 역시 컴퓨터과학과라는 이름이 생긴 건 2005년부터이고 그 전엔 정보산업공학이라고 하여 이쪽으로의 분류가 모호했다.
IT 붐과 함께 지금은 당연시되고 있는 학과 이름이 비교적 최근까지도 일류대급에 속하는 대학에도 없었던 게 의외이다. 어쨌든, 이 교수 역시 당시는 서울대 계산통계학과를 졸업했다.

이분의 설파 교리(?)와 연구 분야는 이러하다.
먼저, 기계 중심적이지 않고, 수학적으로 더 엄밀하며 인간의 사고와 논리를 더 자연스럽게 표현할 수 있는 프로그래밍 언어를 지향한다. 사실, C/C++이나 자바는 오늘날의 최신 프로그래밍 언어 이론이나 방법론이 반영된 깨끗한 언어가 아니다.

그래서 이런 전산학 순수주의자(?)는 특별히 람다 대수에 기반한 OCaml이나 최소한 Scheme 같은 함수형 언어를 선호한다. 함수가 마치 일반 상수처럼 코드 중간에서 별다른 작명 없이도 자유롭게 만들어지고 값처럼 다뤄질 수 있다.
이게 좋은 패러다임이기 때문에 심지어 C++도 C++0x에서는 함수 포인터를 대체할 만한 람다 대수 문법이 추가되었으며, 비주얼 스튜디오 2010에서는 F#이라는 함수형 프로그래밍 언어가 새로 도입되었다. 이것은 의미심장한 변화이다.

그리고 이 교수가 연구하는 정적 분석이란, 프로그램을 실제로 실행해 보지 않고, 그 구조를 뜯어보기만 하고서 이 프로그램이 잠재적으로 배열 첨자 초과 오류나 메모리 누설 따위가 발생할 수 있겠다고 진단을 내리는 기술을 말한다. 사실, 좋은 프로그래밍 언어란, 컴파일러만 통과한 프로그램이라면 뻗지 않고 잘 돌아간다는 보장이 되어야 하고 컴파일 시점 때 해당 코드에 존재하는 잠재적인 모든 문제를 찾아낼 수 있어야 한다는 것이 이분의 지론이다.

이게 가능할까? 입력은 키보드나 파일로 들어오고 메모리 할당과 해제가 일어나는 통로가 주어져 있을 때, 복잡한 루프와 배열, 함수 재귀호출, 다중 포인터 로직을 추적하면서(프로그램을 실행하는 게 아니고!) 딱 보고 이 코드는 구조적인 문제가 있다는 걸 찾아내는 게 과연 쉬운 일일까? ㅋㅋ

당연히 머리가 터져나가게 어려운 일일 것이다.
하지만 그게 가능하기만 하다면 프로그램을 일일이 실행해 보는 것보다 훨씬 더 꼼꼼하고 확실한 검증이 행해질 수 있다. 자동차를 실제로 만든 뒤에 충돌시켜서 부숴 보지 않고도 디자인만 딱 보고 운전자의 안전에 어떤 문제가 있겠는지 예측하는 것과 비슷한 맥락이지 않은가.

사실, 프로그램 정적 분석과 뿌리를 공유하는 가장 원초적인 문제는, 바로 전산학에서 다루는 정지 문제(halting problem)이다. 이는 오늘날의 컴퓨터 모델인 튜링 기계에서는 100% 완벽하게 푸는 게 애시당초 불가능하다는 게 증명되어 있다.

이런 맥락에서 프로그램 정적 분석기 또한 100% 완벽하고 정확하게 동작하는 건 불가능하다. 실제로는 문제가 있는 부분이 아닌데 문제가 있다고 진단하는 false alarm도 존재한다. 그 이상 더 정밀하게 동작할 수는 없기 때문.

그래도 이것만으로도 어디냐. C/C++은 성능이 무지막지하게 좋은 대신, dangling pointer, memory leak, buffer overflow 등 이름만 들어도 치를 떨 무시무시한 버그와 보안 문제들에 무방비로 노출되어 있는 chaotic한 언어가 아니던가? 전산학 전공자는 소프트웨어 공학 시간에 익히 배워 알듯, 소프트웨어 개발이란 건 그렇잖아도 작업의 절대적인 양과 질을 측정하기가 어려운 분야이다. 그러니 소스 코드를 정적 분석으로 검증하는 시스템이 없이는 IT 산업계가 제대로 돌아갈 수가 없다. 그렇지 않으면, 어디서 뻑이 날지 모르는 C/C++ 언어로 의료 기기나 우주선 같은 크리티컬 시스템을 만들거나 사용하려면 미리 보험이라도 들어 놔야 하지 않을까 싶다. 진짜로. -_-;;

이런 복잡도를 제어하는 시스템을 연구하는 게 이 광근 교수의 목표이다.
그분은 이걸로 이미 저명한 학술지에 적지 않은 논문을 냈고, 소프트웨어 검증 솔루션을 개발하여 기업체에 납품했다.

사실, 비주얼 스튜디오도 일반인이나 학생이 사용하는 라이선스 말고 제일 비싼 엔터프라이즈급 라이선스 제품을 써 보면, 소스 코드 정적 분석 기능이 들어있다.
기회가 되면 내가 개발한 프로그램도 그런 걸로 한번 좀 분석해 봐야 할 텐데 말이다. 메모리나 GDI 개체, 커널 핸들 등 해제가 필요한 자원들은 전부 클래스 소멸자가 처리하게 바꾸고, 지속적인 개량과 코드 리팩터링을 해 왔기 때문에 그런 초보적인 실수는 이제 없으리라 여겨진다만, 이걸 시스템 차원에서 깔끔하게 입증을 못 하고 있다는 게 문제이긴 하다.

코드를 실행하지 않고 척 들여다보기만 한 뒤 그 코드로부터 문제될 만한 부분을 알아서 찾아 내는 것은 활용 가능성이 굉장히 많다. 마치 공항 검색대가 가방을 열어 보지 않고 사생활 침해 걱정이 없이 비행기에 실을 수 없는 물건을 찾아내는 것처럼 말이다. 이 얼마나 유용한 기술인가?

이 광근 교수는 자기 연구 분야를 차치하고라도, 독특한 스타일의 강의 자료나 여러 글들을 읽어 보면, 가히 공부의 본질을 아는 사람이며 정말로 보통사람이 아니다 싶은 면모가 여럿 느껴진다. 특히 이분은 우리말로 학문하기에 대한 관념이 굉장히 투철한 걸로 잘 알려져 있다.

• “MIT라는 이름은 본토 사람들이 보기에는 그냥 황해도 과기원 정도로밖에 들리지 않으며, 떼제베도 프랑스 원어민에게 다가오는 의미는 단지 매우 빠른 열차일 뿐이다. 우리만 혼자 폼나 보인다고 외래어 알파벳을 남발하고 있다.”
• “비록 어떤 개념이나 기술이 외국에서 유래되었다 하더라도, 그 원판을 능가하는 학문적 성과는 언제나 모국어를 통해서만 이뤄져 왔다.”

외래어는 싹 다 배격하고 정확· 엄밀함을 희생해서까지 무조건 뭉뚱그려서 순우리말만 쓰자는 국수주의 주장이 절대 아니며, 오히려 완전히 다른 차원에서의 주장이다.
작년에 한창 카이스트가 자살과 영어 강의 때문에 시끄럽던 시절에 이분은 자기의 지론을 다시 한데 정리한 개념글을 하나 교수신문에다 기고했다. 그 후 이 글은 전산 비전공자, 심지어 인문학 하는 사람들에게서도 인용되고 폭풍처럼 칭송받고 있는 중이다.

IT 쪽 최정상에 앉아 있는 사람이 이례적으로 용어 순화와 모국어 강의를 옹호하니 뜻밖이지 않은가? 저 글에 딱히 정치색이 있는 건 물론 전혀 아니지만, 영어 강의, 세계화 이런 것들을 반대하고 이념적으로 진보 성향이 좀 있는 사람들이 더욱 지지를 하는 경향이 있었다. 예를 들어 조 국 교수도 그 글을 완전 극찬한 바 있다.

카이스트 교수 부임 시절에 이 교수는 학과 이름을 전산학과에서 컴퓨터xx학과로 바꾸는 것도 괜히 쓸데없는 일이라고 만류한 적이 있다. ACM, IBM의 M은 완전 구닥다리 용어인 '기계'라는 뜻이지 않냐고 말이다.

그리고 대학 캠퍼스 내부의 건물들을 초행자도 식별하기 쉽게 번호가 좀 있어야 한다고 제안하신 바 있다.
그 제안 때문인지 이분이 서울대로 전근 가신 뒤에 얼마 안 되어(2004~2005년쯤 아마?) 카이스트도 건물들에 N0, E0, S0 같은 식으로 번호가 붙었다.
서울대는 워낙 건물이 많고 내부가 복잡해서 진작부터 그런 게 있다.
연세대는 그런 거 없다. 본교 도입이 시급합니다.

지금이야 카이스트 전산학동이 수 년 전부터 몇 층 더 증축되었지만, 그 당시에 이 광근 교수는 아마 공간 부족으로 인해 전산학동이 아닌 이웃 산업공학동에 연구실이 있었다. 그리고 이런저런 어른들의 사정이 더해져서 그분은 서울대로 전근을 가신 걸로 추정된다. 비슷한 시기에 전산학과의 김 태환 교수도 서울대로 가셨다.

이분의 수업은 진짜 그냥 온갖 기호와 공식, 증명이 즐비한 수학 덕후식이며 빡세다..;;;
그래서 카이스트 재학 시절, 내게는 좀 굴욕적인 기억이 있다.
C++의 사고방식에 완전히 중독되다시피하던 내 머리 구조로는 nML이네 뭐네 하는 “프로그래밍 언어 PL” 수업을 도저히 따라갈 수가 없어서... 전공 필수 과목일 뿐만 아니라 전근을 앞둔 스타 교수의 마지막 수업을 드랍하고 말았다. 2003년 봄 학기의 일이다. 그것도 수강 변경도 아닌 철회 기간에 출혈을 감수하며 드랍.

난 그 당시 <날개셋> 한글 입력기 2.x와 3.0의 개발과 직접적인 관련이 있지 않은 복잡한 추상화 계층이나 뜬구름 잡는 이론에는 머리가 전혀 돌아가지 않던 시절이었다. 동기 부여를 받으면 철도 덕후 수준으로 머리가 미쳐 돌아가지만, 동기 부여가 없는 곳에는 난 담을 확 쌓아 버리고 죽어도 관심 안 보인다. 역시 난 프로그래밍으로 다른 창의적인 작품을 만드는 게 삶의 목적이지, 프로그래밍 패러다임 자체를 바꾸는 일은 내 적성이 아니라는 걸 알 수 있었다. C++보다 더 엄밀하고 깔끔한 프로그래밍 언어로 수학 덕질하는 것보다는, 당장 윈도우 API로 옛한글과 세벌식 모아치기를 구현하는 것에만 온통 관심이 쏠려 있어서..

그래서 나중에 한 태숙 교수의 PL을 다시 들었다. 이분의 PL 수업이 그나마 내가 생각했던 PL 수업에 더 근접한 평범한(?) 것이었고, 들을 만했다.;; 각종 프로그래밍 언어들의 특성과 개념, 값의 평가 시기, LL 파서, LR 파서, garbage collector의 동작 원리 등등.. 참고로 덧붙이자면, 내가 예전 글에서도 소개한 적이 있듯 한 교수 역시 왕년에 1등을 놓친 적이 없었고 대입 학력고사 전국 수석을 차지했던 공부 만렙 괴물이다.;;

현재는 카이스트 전산학과의 류 석영 교수가 과거 이 광근 교수의 제자이며, 그분 뒤를 이어 카이스트 프로그래밍 언어 연구실을 공동 운영하고 있다(한 태숙, 최 광무 교수와 같이).
류 교수의 증언에 따르면 이 교수 연구실은 말도 못 하게 무지막지하게 빡세기 때문에, (그 대신 잘 적응하면 얻는 것도 많겠지);; 어지간한 각오가 돼 있지 않다면 그분 연구실로 대학원 진학을 하는 건 비추라고 한다. =_=;;;
그래도, 좀 까칠한 것만 빼면 교수님은 학자로서 정말 좋은 분이라고.. ㅜㅜ

어쨌든 이 광근 교수. 수업 하나 들은 적도 없이 헤어졌지만, 이런 식으로 내 기억에 남아 있다.
본인이 이분에 대해 수집한 모든 정보들의 출처는 당연히 그분의 공식 홈페이지이므로, 관심 있으신 분은 방문해 보시라.

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

오랜만에 알고리즘 얘기.
정보 올림피아드 공부를 한 적이 있는 분이라면, 제목에 등장한 용어가 아주 친숙할 것이다. 앞으로 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 증가시켜 놓고 말이다.

오프셋	0	1	2	3	4	5	6	7	8	9	10
n	3	2	1	4	5	2	3	5	3	6	4
LIS길이	1	1	1	2	3	2	3	4	3	5	4
이전오프셋	-1	-1	-1	0	3	2	5	6	5	7	6

위와 같은 표가 완성되고 나면, 그 후 개수가 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 사무엘