Tour de IOCCC: 1988/litmaath
main(argc, argv)
int argc;
char **argv;
{
while (*argv != argv[1] && (*argv = argv[1]) && (argc = 0) || (*++argv
&& (**argv && ((++argc)[*argv] && (**argv <= argc[*argv] ||
(**argv += argc[*argv] -= **argv = argc[*argv] - **argv)) &&
--argv || putchar(**argv) && ++*argv--) || putchar(10))))
;
}
두 개의 변수만 쓰는 것도, 그리고 그 변수가 하필 argc와 argv인 것도 도저히 그냥 넘어 갈 수 없는 코드입니다.
뭘 하는 프로그램인가?
언제나 그렇듯 컴파일해 봅시다. 이 때 주의할 점은, 이 프로그램은 컴파일 옵션에 따라 다르게 동작할 수 있다는 것입니다. 만약 아래와 같은 출력이 나타나지 않는다면 다른 최적화 옵션을 줘서 테스트해 보시길 바랍니다.1
$ gcc -O1 litmaath.c -o litmaath
$ ./litmaath eschew obfuscation
ceehsw
abcfinoostu
문자열 단위로 뭔가를 하는 것 같으니 좀 더 긴 단어를 넣어 볼까요?
$ ./litmaath floccinaucinihilipilification antidisestablishmentarianism
aaccccffhiiiiiiiiilllnnnooptu
aaaabdeehiiiiilmmnnnrssssttt
그렇습니다. 이 프로그램은 입력된 단어 별로 글자들을 정렬해서 보여 주는 프로그램입니다.
이 프로그램의 주된 사용 용도로 아나그램(anagram; 같은 문자들로 이루어진 다른 단어)이 있습니다. 서로 아나그램이 되는 단어를 찾기 위해서는 각 단어 별로 나타나는 문자와 그 빈도로 키값을 만든 뒤 키가 같은 것들을 모아야 하는데 이 프로그램이 그런 작업을 해 줄 수 있습니다.
어떻게 동작하는가?
코드를 정리하면서 설명을 시작하겠습니다.
main(argc, argv)
int argc;
char **argv;
{
while (
*argv != argv[1] &&
(*argv = argv[1]) &&
(argc = 0) ||
(*++argv &&
(**argv &&
((++argc)[*argv] &&
(**argv <= argc[*argv] ||
(**argv += argc[*argv] -= **argv = argc[*argv] - **argv)
) &&
--argv ||
putchar(**argv) &&
++*argv--
) ||
putchar(10)
)
)
);
}
일단 대강 보이는 대로 정렬해 놓긴 했지만, &&가 ||보다 먼저 결합한다는 걸 생각하면 이해를 위해 괄호를 더 달아 주고 제대로 정렬하는 게 낫겠습니다.
main(argc, argv)
int argc;
char **argv;
{
while (
(*argv != argv[1] &&
(*argv = argv[1]) &&
(argc = 0)
) ||
(*++argv &&
((**argv &&
(((++argc)[*argv] &&
(**argv <= argc[*argv] ||
(**argv += argc[*argv] -= **argv = argc[*argv] - **argv)
) &&
--argv
) ||
(putchar(**argv) &&
++*argv--
)
)
) ||
putchar(10)
)
)
);
}
루프 정리하기
while 문에 내용물이 전혀 없군요. 다른 말로 하면 저 거대한 while의 조건식을 풀어 써야 한다는 얘기가 되겠습니다. 그리고 전통적인 K&R 함수 선언도 현대적인 선언으로 바꾸도록 하겠습니다.
int main(int argc, char **argv)
{
int ret;
do {
ret =
(*argv != argv[1] &&
(*argv = argv[1]) &&
(argc = 0)
) ||
(*++argv &&
((**argv &&
(((++argc)[*argv] &&
(**argv <= argc[*argv] ||
(**argv += argc[*argv] -= **argv = argc[*argv] - **argv)
) &&
--argv
) ||
(putchar(**argv) &&
++*argv--
)
)
) ||
putchar(10)
)
);
} while (ret);
return 0;
}
모든 &&와 || 연산은 if 문을 사용해서 고칠 수 있습니다. 왜냐하면 이들 논리 연산자는 왼쪽 피연산자를 평가한 뒤 그 값에 따라 그 다음 피연산자를 평가할 지 결정하기 때문이지요. 기본적으로,
c = a() && b();는c = a(); if (c) c = b();로 바꿀 수 있습니다.c = a() || b();는c = a(); if (!c) c = b();로 바꿀 수 있습니다.
만약 &&나 ||가 둘 이상 연달아 나오면 어떻게 될까요?
d = a() && b() && c();는 다음과 같이 바꿀 수 있습니다.d = a(); if (d) { d = b(); if (d) d = c(); }하지만 마지막
if (d) d = c();는 바깥으로 빼 낼 수 있습니다. 왜냐하면,a() && b() && c()는(a() && b()) && c()와도 같기 때문이지요. (실행되는 순서도 같습니다.) 따라서,d = a(); if (d) d = b(); if (d) d = c();로 고칠 수 있습니다.
d = a() || b() || c();도 같은 방법으로 다음과 같이 바꿀 수 있습니다.d = a(); if (!d) d = b(); if (!d) d = c();
위에 나온 대로 재귀적으로 식을 정리하면 다음과 같이 됩니다.
int main(int argc, char **argv)
{
int ret;
do {
ret = (*argv != argv[1]);
if (ret) ret = (*argv = argv[1]);
if (ret) ret = (argc = 0);
if (!ret) {
ret = *++argv;
if (ret) {
ret = **argv;
if (ret) {
ret = (++argc)[*argv];
if (ret) {
ret = (**argv <= argc[*argv]);
if (!ret) ret = (**argv += argc[*argv] -= **argv = argc[*argv] - **argv);
}
if (ret) ret = --argv;
if (!ret) {
ret = putchar(**argv);
if (ret) ret = ++*argv--;
}
}
if (!ret) ret = putchar(10);
}
}
} while (ret);
return 0;
}
루프 안의 첫 네 줄은 다음과 같습니다.
ret = (*argv != argv[1]);
if (ret) ret = (*argv = argv[1]);
if (ret) ret = (argc = 0);
if (!ret) ...
세번째 줄을 잘 살펴 봅시다. 만약 ret가 참이면, argc는 0이 되고 ret도 0이 됩니다. ret가 거짓이라면 변화가 없고요. 어떤 경우라도 ret는 거짓이 되므로 네번째 줄의 조건은 필요가 없게 됩니다. 따라서 최초의 ret 체크는 그냥 일반적인 문장으로 정리할 수 있습니다.
int main(int argc, char **argv)
{
int ret;
do {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
ret = *++argv;
if (ret) {
ret = **argv;
if (ret) {
ret = (++argc)[*argv];
if (ret) {
ret = (**argv <= argc[*argv]);
if (!ret) ret = (**argv += argc[*argv] -= **argv = argc[*argv] - **argv);
}
if (ret) ret = --argv;
if (!ret) {
ret = putchar(**argv);
if (ret) ret = ++*argv--;
}
}
if (!ret) ret = putchar(10);
}
} while (ret);
return 0;
}
다음으로 살펴 볼 것은 ret가 조건인 첫번째 if 문입니다. 이 안의 코드는 대략 다음과 같이 되어 있습니다.
ret = *++argv;
if (ret) {
ret = **argv;
if (ret) ...;
if (!ret) ret = putchar(10);
}
마지막 if 문에서는 ret가 거짓이면 개행 문자('\n', ASCII 코드 10)를 출력한 뒤 ret에 putchar의 반환값을 설정합니다. 이 함수는 출력된 문자를 그대로 돌려 주기 때문에 ret는 항상 10, 즉 참으로 평가되고, 따라서 처음의 if 문 안에 일단 들어 가면 루프 조건이 충족되는 셈입니다. 이걸 반영하도록 코드를 고치면,
int main(int argc, char **argv)
{
int ret;
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
if (!*++argv) break;
ret = **argv;
if (ret) {
ret = (++argc)[*argv];
if (ret) {
ret = (**argv <= argc[*argv]);
if (!ret) ret = (**argv += argc[*argv] -= **argv = argc[*argv] - **argv);
}
if (ret) ret = --argv;
if (!ret) {
ret = putchar(**argv);
if (ret) ret = ++*argv--;
}
}
if (!ret) putchar(10);
}
return 0;
}
가 됩니다. ret이 맨 처음에 거짓일 때 바로 루프를 빠져 나가도록 한 것을 눈여겨 보시길 바랍니다.
이런 류의 코드는 심심찾게 찾아 볼 수 있습니다. 예를 들어 argv는 코드 상에서 절대로 바로 대입되지 않고 증가하거나 감소만 하므로, ret = --argv;라는 문장은 항상 참이 될 수 밖에 없습니다. 따라서,
int main(int argc, char **argv)
{
int ret;
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
if (!*++argv) break;
ret = **argv;
if (ret) {
ret = (++argc)[*argv];
if (ret) {
ret = (**argv <= argc[*argv]);
if (!ret) ret = (**argv += argc[*argv] -= **argv = argc[*argv] - **argv);
}
if (ret) {
--argv;
} else {
ret = putchar(**argv);
if (ret) ret = ++*argv--;
}
}
if (!ret) putchar(10);
}
return 0;
}
두 변수를 맞바꾸는 여러 가지 방법
이제 남아 있는 문장들 중에서 가장 복잡해 보이는 다음 코드를 분석해 봅시다.
ret = (**argv += argc[*argv] -= **argv = argc[*argv] - **argv);
이 코드는 다음과 같이 괄호를 칠 수 있습니다.
ret = (**argv += (argc[*argv] -= (**argv = argc[*argv] - **argv)));
각 대입문의 결과값은 대입된 값이므로, 여러 개의 문장으로 나누도록 합시다.
**argv = argc[*argv] - **argv;
argc[*argv] -= **argv;
**argv += argc[*argv];
ret = **argv;
**argv와 argc[*argv]가 나타나는데, 이를 각각 x와 y라고 하고 코드를 정리하면,
x = y - x;
y = y - x;
x = x + y;
ret = x;
이것은 다음과 같은 코드와 유사한 역할을 합니다.
x = x ^ y;
y = x ^ y;
x = x ^ y;
ret = x;
두 코드는 모두 임시 변수 없이 두 변수를 바꿔 치는 코드입니다. (후자는 XOR 교체 알고리즘이라고 따로 부릅니다.) 이게 왜 가능한지 각 줄 별로 변수의 값을 추적해 봅시다.
/* 본래 x = x0, y = y0 */
x = y - x; /* x = y0 - x0 */
y = y - x; /* y = y0 - (y0 - x0) = x0 */
x = x + y; /* x = (y0 - x0) + x0 = y0 */
/* 이제 x = y0, y = x0 */
이제 이해가 가지요? XOR을 사용한 바꿔 치기도 이와 유사합니다.
원래 코드는 크게 두 가지 문제를 가지고 있는데, 한 가지는 표준 C에서 동작을 보장하지 않는 코드라는 것입니다. 예를 들어 제가 가진 컴파일러는 -O0으로 컴파일하면 잘못된 결과를 내뱉었습니다. 그것도 제가 이 글을 쓰고 있는 시점에서 최신인 컴파일러(GCC 4.3.2)인데도요. 이것은 한 문장 안에서 같은 변수를 두 번 바꾸려고 하고 있기 때문에 생기는 문제입니다.
C 표준은 컴파일러가 최적화를 할 여지를 최대한 보장해 주기 위해서 함수 호출과는 별개로 수식이 평가되는 순서를 특정한 시점 빼고는 마음대로 정할 수 있도록 했습니다. 여기서 "특정한 시점"을 시퀀스 포인트(sequence point)라고 하는데, 예를 들어서 우리가 보통 보는 다음과 같은 문장은:
*ptr++ = getchar();
단 한 개, 즉 세미콜론(;)만이 시퀀스 포인트이며, 따라서 ptr이 증가되는 연산과 getchar 함수 호출은 어느 쪽이든 먼저 실행될 수 있습니다. 두 시퀀스 포인트 사이에서는 결과를 변형시키지 않는 한 마음대로 실행 순서를 바꿀 수 있기 때문입니다. 그러나 getchar이 사실은 ptr을 참조하고 있었다면 이 코드는 문제가 생길 것이고, 따라서 컴파일러는 마음대로 순서를 바꿀 수 없겠지요. 이런 상황을 해결하기 위해서 C 표준은 두 시퀀스 포인트 사이에서 한 변수는 많아야 단 한 번만 대입될 수 있으며, 한 번만 대입된다더라도 대입 전의 값이 대입 후에 읽힐 수 없다고 규정하고 있습니다. 따라서 컴파일러는 안심하고 위의 코드를 최적화할 수 있습니다.
이제 두번째 문제를 생각해 봅시다. 만약 **argv와 argc[*argv]가 같은 메모리를 참조한다면 어떻게 될까요?
/* 본래 x = y = x0 */
x = y - x; /* x = y = x0 - x0 = 0 */
y = y - x; /* x = y = 0 */
x = x + y; /* x = y = 0 */
/* 이제 x = y = 0... 어?! */
그렇습니다. 이 코드는 두 변수가 같은 메모리를 참조하면 두 메모리를 모두 날려 버리는 무시무시한 문제가 있습니다. 그렇기 때문에 XOR 교환 알고리즘 같은 것들은 일반적으로 사용하지 않아야 하고, 심지어 그냥 임시 변수를 써서 교환하는 방법이 더 빠른 경우도 적지 않게 많습니다.
...문제를 너무 길게 설명한 것 같은데 하여간 그래서 원래 코드는 다음과 같은 의미를 가집니다.
char tmp;
assert(&**argv != &argc[*argv]); /* 같은 메모리를 참조할 수 없음 */
tmp = argc[*argv];
argc[*argv] = **argv;
**argv = tmp;
ret = **argv;
중간에 단언(assertion)이 실제로 항상 성립하는지는 코드를 더 읽어 보면서 확인하도록 하겠습니다.
앞쪽 putchar 호출도 확인해 봅시다. 이 문장에서 ret는 **argv의 값으로 설정되어야 합니다. 그런데 **argv가 실행되는 과정을 살펴 보면, 이 코드는 맨 처음에 **argv가 참일 때 실행되는 부분에 있으며, *argv는 이 문장 뒤에서야 바뀝니다. 따라서 우리는 안심하고 맨 마지막 putchar(10) 호출을 else 절에 넣을 수 있습니다.
#define SWAP(x,y) \
do { \
char tmp = (y); \
(y) = (x); \
(x) = tmp; \
} while (0)
int main(int argc, char **argv)
{
int ret;
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
if (!*++argv) break;
if (**argv) {
ret = (++argc)[*argv];
if (ret) {
ret = (**argv <= argc[*argv]);
if (!ret) {
assert(&**argv != &argc[*argv]);
SWAP(**argv, argc[*argv]);
ret = **argv;
}
}
if (ret) {
--argv;
} else {
putchar(**argv);
++*argv--;
}
} else {
putchar(10);
}
}
return 0;
}
좀 전에 설명한 변수 교환 코드도 비슷한 부분을 담고 있습니다. 마지막에 ret에는 **argv가 저장되는데, 이 값은 교환 전에는 argc[*argv]였던 코드죠. 그런데 이 코드는 (++argc)[*argv]가 참일 때 실행되는 if 문에 들어 있기 때문에 항상 참으로 처리됩니다. 따라서,
#define SWAP(x,y) \
do { \
char tmp = (y); \
(y) = (x); \
(x) = tmp; \
} while (0)
int main(int argc, char **argv)
{
int ret;
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
if (!*++argv) break;
if (**argv) {
ret = (++argc)[*argv];
if (ret) {
if (!(**argv <= argc[*argv])) {
assert(&**argv != &argc[*argv]);
SWAP(**argv, argc[*argv]);
}
ret = 1;
}
if (ret) {
--argv;
} else {
putchar(**argv);
++*argv--;
}
} else {
putchar(10);
}
}
return 0;
}
와 같은 코드가 되며, 조건문을 정리하고 항상 실행되는 부분(ret = 1; 문장을 생각해 보면 그 다음 if 문은 이 안에 들어 와도 되겠죠?)을 옮기면 다음과 같은 ret가 사라진 코드를 볼 수 있습니다.
#define SWAP(x,y) \
do { \
char tmp = (y); \
(y) = (x); \
(x) = tmp; \
} while (0)
int main(int argc, char **argv)
{
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
if (!*++argv) break;
if (**argv) {
if ((++argc)[*argv]) {
if (**argv > argc[*argv]) {
assert(&**argv != &argc[*argv]);
SWAP(**argv, argc[*argv]);
}
--argv;
} else {
putchar(**argv);
++*argv--;
}
} else {
putchar(10);
}
}
return 0;
}
삼중 루프
이제 본격적으로 알고리즘을 분석하기에 앞서 포인터 연산들을 모두 정리해 보겠습니다. 일일이 설명하기 복잡하므로 아래의 코드에서 주석으로 어떻게 바뀌었는지 설명하겠습니다. (이 코드 이후로 SWAP 매크로는 글을 짧게 하기 위해 생략합니다.)
#define SWAP(x,y) \
do { \
char tmp = (y); \
(y) = (x); \
(x) = tmp; \
} while (0)
int main(int argc, char **argv)
{
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
/* 체크하기 전에 증가시키므로 별도의 문장으로 가능 */
++argv;
if (!*argv) break;
/* **argv == (*argv)[0] */
if ((*argv)[0]) {
/* (++argc)[*argv] == (*argv)[++argc] */
if ((*argv)[++argc]) {
/* argc[*argv] == (*argv)[argc], 이하 동일 */
if ((*argv)[0] > (*argv)[argc]) {
assert(&(*argv)[0] != &(*argv)[argc]);
SWAP((*argv)[0], (*argv)[argc]);
}
--argv;
} else {
putchar((*argv)[0]);
/* argv는 원래 문장이 실행된 뒤에 감소하므로 별도로 분리 */
++*argv;
--argv;
}
} else {
putchar(10);
}
}
return 0;
}
겹치는 코드를 더 정리하면,
int main(int argc, char **argv)
{
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
++argv;
if (!*argv) break;
if ((*argv)[0]) {
++argc; /* 별도로 분리 */
if ((*argv)[argc]) {
if ((*argv)[0] > (*argv)[argc]) {
/* argc는 "항상" 양수이므로 다음 단언문은 항상 참. */
/*assert(&(*argv)[0] != &(*argv)[argc]);*/
SWAP((*argv)[0], (*argv)[argc]);
}
} else {
putchar((*argv)[0]);
++*argv;
}
--argv; /* 중복 코드를 바깥으로 빼냄 */
} else {
putchar(10);
}
}
return 0;
}
이제 argv가 어떻게 변하는지 생각해 봅시다. argv를 설정하는 곳은 코드 상에서 세 군데 있습니다.
- 처음에 시작할 때,
- 루프 조건을 검사하기 바로 직전의
++argv;, (*argv)[0]이 참일 때 맨 마지막에 실행되는--argv;.
코드가 실행되는 경로를 잘 생각하면 ++argv;와 --argv; 사이의 코드에서는 argv가 잠시 1 증가했다가 다시 원래대로 돌아 오는 걸 알 수 있습니다. (*argv)[0]이 거짓일 경우에만 argv가 1 증가한 뒤 원래대로 돌아 오지 않는다는 걸 생각하면, 해당 문장들을 지우고 그 사이의 코드에서 *argv를 *(argv+1), 즉 argv[1]로 고쳐도 되겠습니다.
int main(int argc, char **argv)
{
while (1) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
if (!argv[1]) break;
if (argv[1][0]) {
++argc;
if (argv[1][argc]) {
if (argv[1][0] > argv[1][argc]) {
SWAP(argv[1][0], argv[1][argc]);
}
} else {
putchar(argv[1][0]);
++argv[1];
}
} else {
++argv; /* 이 경우 argv는 원래대로 복구되지 않으므로 */
putchar(10);
}
}
return 0;
}
다음으로 할 일은 프로그램 구조를 전체적으로 재구성하는 것입니다. 원래 코드가 대략 다음과 같았음을 생각합시다.
while (1) {
if (*argv != argv[1]) {
/* (1) *argv == argv[1] 조건이 성립하게 만든다. */
}
if (!argv[1]) break;
if (argv[1][0]) {
/* (2) argv[1]을 가지고 뭔가를 한다. */
} else {
/* (3) argv를 증가시킨다. */
}
}
일단 (1)에서 argv[1]을 바꾸지 않기 때문에 그 뒤에 나오는 루프의 종료 조건은 맨 위로 옮길 수 있습니다.
while (1) {
if (!argv[1]) break;
if (*argv != argv[1]) {
/* (1) *argv == argv[1] 조건이 성립하게 만든다. */
}
if (argv[1][0]) {
/* (2) argv[1]을 가지고 뭔가를 한다. */
} else {
/* (3) argv를 증가시킨다. */
}
}
물론 다음과 같이 while 조건식으로 옮기는 게 더 괜찮겠지만요.
while (argv[1]) {
if (*argv != argv[1]) {
/* (1) *argv == argv[1] 조건이 성립하게 만든다. */
}
if (argv[1][0]) {
/* (2) argv[1]을 가지고 뭔가를 한다. */
} else {
/* (3) argv를 증가시킨다. */
}
}
또 하나 중요한 것은 (2)번에서는 상황에 따라 *argv == argv[1] 조건이 깨질 수도 있고 그대로 유지될 수도 있지만, (3)에서는 "항상" 깨진다는 것입니다. C 표준은 argv 배열의 각 문자열이 공유될 수 없다고 규정하기 때문에2 서로 인접한 두 argv 문자열들이 같을 수 없습니다.
따라서 만약 while 루프 안에 다른 루프를 넣는다면, 이 루프에는 (1)과 (2)가 들어 갈 수 있지만 (3)은 루프 바깥에서 실행되어야 할 것입니다. (사실 루프의 지속 조건이 바로 argv[1][0]이 되어야 합니다.) 이를 반영하면 다음과 같이 됩니다.
while (argv[1]) {
while (argv[1][0]) {
if (*argv != argv[1]) {
/* (1) *argv == argv[1] 조건이 성립하게 만든다. */
}
/* (2) argv[1]을 가지고 뭔가를 한다. */
}
/* (3) argv를 증가시킨다. */
}
다행히 (1)은 argv[1]을 건들지 않기 때문에 루프의 조건식은 그대로 유지할 수 있습니다. 원래 코드를 반영하면,
int main(int argc, char **argv)
{
while (argv[1]) {
while (argv[1][0]) {
if (*argv != argv[1]) {
*argv = argv[1];
if (argv[1]) argc = 0;
}
++argc;
if (argv[1][argc]) {
if (argv[1][0] > argv[1][argc]) {
SWAP(argv[1][0], argv[1][argc]);
}
} else {
putchar(argv[1][0]);
++argv[1];
}
}
++argv;
putchar(10);
}
return 0;
}
이제 *argv의 역할은 argv[1]이 바뀌었는지 바뀌지 않았는지 체크하기 위함임이 분명해졌습니다. 그럼 *argv를 쓰는 대신에, argv[1]이 바뀔 때마다 초기화를 수행하도록 하겠습니다. 또한 *argv != argv[1] 조건은 맨 처음에 프로그램이 실행되었을 때도 적용되기 때문에 프로그램의 맨 처음에 적절한 초기화도 필요합니다. 이를 반영하면 다음과 같은 코드가 됩니다.
int main(int argc, char **argv)
{
argc = 0;
while (argv[1]) {
while (argv[1][0]) {
++argc;
if (argv[1][argc]) {
if (argv[1][0] > argv[1][argc]) {
SWAP(argv[1][0], argv[1][argc]);
}
} else {
putchar(argv[1][0]);
++argv[1];
argc = 0;
}
}
++argv;
putchar(10);
}
return 0;
}
거의 끝이 나 가는군요. 이제 argv를 직접 고치는 대신에 argv[i] 식으로 접근하고 i를 변경하도록 바꿔 보겠습니다.
int main(int argc, char **argv)
{
int i = 1;
argc = 0;
while (argv[i]) {
while (argv[i][0]) {
++argc;
if (argv[i][argc]) {
if (argv[i][0] > argv[i][argc]) {
SWAP(argv[i][0], argv[i][argc]);
}
} else {
putchar(argv[i][0]);
++argv[i];
argc = 0;
}
}
++i;
putchar(10);
}
return 0;
}
마찬가지 이유로 argc 대신에 별도의 변수 k를 접근하게 합니다. 또한 argc는 사용되기 전에 항상 1 증가되기 때문에, ++argc; 코드를 사용 이후로 옮기고 초기화를 미리 1로 하도록 바꾸겠습니다. 물론 초기화되는 코드 경로에서는 ++argc;가 실행되면 안 되겠지요.
int main(int argc, char **argv)
{
int i = 1;
int k = 1;
while (argv[i]) {
while (argv[i][0]) {
if (argv[i][k]) {
if (argv[i][0] > argv[i][k]) {
SWAP(argv[i][0], argv[i][k]);
}
++k;
} else {
putchar(argv[i][0]);
++argv[i];
k = 1;
}
}
++i;
putchar(10);
}
return 0;
}
또 하나 고려해야 할 것은 이중 while 문 안에 들어 있는 ++argv[i];라는 코드입니다. 이 코드는 argv[i][k]가 참이 아닐 때만 실행되는데 아까 전에 하나의 while 문을 이중 while로 고친 것과 똑같은 상황이 되었군요. 한 번 while 문을 하나 더 넣도록 하겠습니다.
int main(int argc, char **argv)
{
int i = 1;
int k = 1;
while (argv[i]) {
while (argv[i][0]) {
while (argv[i][0]) {
if (argv[i][k]) {
if (argv[i][0] > argv[i][k]) {
SWAP(argv[i][0], argv[i][k]);
}
++k;
} else {
putchar(argv[i][0]);
++argv[i];
k = 1;
break; /* 세번째 루프를 리셋함 */
}
}
}
++i;
putchar(10);
}
return 0;
}
세번째 while 문은 두번째 while과 조건식이 똑같습니다만 안에 들어 있는 break; 때문에 의미가 바뀝니다. 사실 조건식이 같으니 argv[i][k]가 참인 경우에 break;를 넣어도 똑같은 결과가 됩니다만, 루프를 리셋하는 것보다 루프를 그냥 진행하는 경우가 더 많이 나타나니까 이 쪽이 더 정리하기 편하겠지요.
break; 앞에 있는 코드들을 바깥으로 빼 내도 영향이 없으므로 옮기겠습니다.
int main(int argc, char **argv)
{
int i = 1;
int k = 1;
while (argv[i]) {
while (argv[i][0]) {
while (argv[i][0]) {
if (argv[i][k]) {
if (argv[i][0] > argv[i][k]) {
SWAP(argv[i][0], argv[i][k]);
}
++k;
} else {
break;
}
}
putchar(argv[i][0]);
++argv[i];
k = 1;
}
++i;
putchar(10);
}
return 0;
}
즉, 세번째 루프는 argv[i][0] 뿐만 아니라 argv[i][k]도 참이어야 지속됩니다. 다행히 이 세번째 루프 안에서는 argv[i][0]이 바뀌지 않고, 두번째 루프에서 이미 참임을 알고 있으므로 후자의 조건만 유지해도 충분합니다.
int main(int argc, char **argv)
{
int i = 1;
int k = 1;
while (argv[i]) {
while (argv[i][0]) {
while (argv[i][k]) {
if (argv[i][0] > argv[i][k]) {
SWAP(argv[i][0], argv[i][k]);
}
++k;
}
putchar(argv[i][0]);
++argv[i];
k = 1;
}
++i;
putchar(10);
}
return 0;
}
아까 살펴 보기 시작한 ++argv[i];를 덜어 내기 위해서, 모든 argv[i][...]를 argv[i][...+j]로 고치고 j를 대신 증가시키기로 합시다. 따라서 j는 원래 argv[i]의 위치와 현재 argv[i]의 위치 사이의 차이를 나타냅니다. 당연히 시작할 때 j는 0이어야 하고, argv[i] 자체가 바뀌는 경우, 즉 i가 바뀌는 경우에도 초기화되어야 합니다.
int main(int argc, char **argv)
{
int i = 1;
int j = 0;
int k = 1;
while (argv[i]) {
while (argv[i][j]) {
while (argv[i][j+k]) {
if (argv[i][j] > argv[i][j+k]) {
SWAP(argv[i][j], argv[i][j+k]);
}
++k;
}
putchar(argv[i][j]);
++j;
k = 1;
}
++i;
j = 0;
putchar(10);
}
return 0;
}
이제 모든 while 문을 for 문으로 고치겠습니다. 이 과정에서 j = 0과 k = 1 같이 두 번 나오는 루프 초기화 문장도 하나로 합쳐야 합니다. 순서를 잘 고치면,
int main(int argc, char **argv)
{
int i = 1;
int j;
int k;
while (argv[i]) {
j = 0;
while (argv[i][j]) {
k = 1;
while (argv[i][j+k]) {
if (argv[i][j] > argv[i][j+k]) {
SWAP(argv[i][j], argv[i][j+k]);
}
++k;
}
putchar(argv[i][j]);
++j;
}
++i;
putchar(10);
}
return 0;
}
이 됩니다. 즉, k = 1; while (...) { ... k = 1; } 같은 코드를 while (...) { k = 1; ... }로 고쳤다고 생각하면 됩니다. (일단 루프가 끝나면 j와 k는 아웃 오브 안중이니 이런 변형이 가능합니다.) 이제 for문으로 모두 고치면,
int main(int argc, char **argv)
{
int i, j, k;
for (i = 1; argv[i]; ++i) {
for (j = 0; argv[i][j]; ++j) {
for (k = 1; argv[i][j+k]; ++k) {
if (argv[i][j] > argv[i][j+k]) {
SWAP(argv[i][j], argv[i][j+k]);
}
}
putchar(argv[i][j]);
}
putchar(10);
}
return 0;
}
선택 정렬의 구현
위의 코드에서 안쪽의 두 루프가 눈에 익지 않나요? 이 코드는 다음과 같은 선택 정렬과 완벽하게 일치합니다.
for (i = 0; i < n; ++i) {
/* arr[i]부터 arr[n-1]까지 가장 작은 원소를 찾는다. */
for (j = i + 1; j < n; ++j) {
/* 현재까지 알려진 가장 작은 원소(arr[i])와 현재 원소를 비교한다.
* 더 작은 원소가 있으면 서로 바꿔치기. */
if (arr[i] > arr[j]) SWAP(arr[i], arr[j]);
}
/* 결과적으로 arr[i]에는 (i+1)번째로 작은 원소가 들어 간다. */
}
단지 변수 이름이 다르고, 길이가 명시적으로 주어진 것이 아니라 해당 문자가 널 문자인지 아닌지를 체크해서 루프를 끝낸다는 차이만이 있을 뿐입니다. 또한 맨 안쪽 루프가 끝날 때마다 남은 원소들 중에서 가장 작은 원소를 찾아 내기 때문에, 루프가 끝나는 즉시 해당 원소를 출력하면 결과적으로 정렬된 목록을 출력하게 될 것입니다.
따라서 지금까지 분석하던 코드는 다음과 같이 정리됩니다.
#include <stdio.h>
#define SWAP(x,y) \
do { \
char tmp = (y); \
(y) = (x); \
(x) = tmp; \
} while (0)
int main(int argc, char **argv)
{
int i, j, k;
for (i = 1; argv[i]; ++i) {
for (j = 0; argv[i][j]; ++j) {
for (k = j + 1; argv[i][k]; ++k) {
if (argv[i][j] > argv[i][k]) {
SWAP(argv[i][j], argv[i][k]);
}
}
putchar(argv[i][j]); /* 남은 글자들 중 가장 작은 글자 */
}
putchar('\n');
}
return 0;
}
아니면 모든 과정이 끝난 뒤 argv[i]는 정렬된 문자열을 들고 있다는 점에서 그냥 printf를 써도 되겠습니다. (다만 이렇게 했을 경우 문자열 리터럴이 나타나기 때문에 덜 복잡해 보이겠지요.)
#include <stdio.h>
#define SWAP(x,y) \
do { \
char tmp = (y); \
(y) = (x); \
(x) = tmp; \
} while (0)
int main(int argc, char **argv)
{
int i, j, k;
for (i = 1; argv[i]; ++i) {
for (j = 0; argv[i][j]; ++j) {
for (k = j + 1; argv[i][k]; ++k) {
if (argv[i][j] > argv[i][k]) {
SWAP(argv[i][j], argv[i][k]);
}
}
}
printf("%s\n", argv[i]);
}
return 0;
}
마지막으로 드는 의문은 과연 다른 정렬 알고리즘도 main 등의 재귀 없이 변수 두 개(그 중 하나는 argv지만)로 구현할 수 있느냐는 것입니다. 퀵 정렬이나 힙 정렬 같이 재귀적으로 구현되는 알고리즘은 아무래도 어렵겠지요. 혹시 구현하셨다면 저에게 연락해 주시면 감사하겠습니다. :p
만약 최적화 옵션을 고쳐도 해결되지 않는다면 다음 코드를 대신 사용하길 바랍니다.
↩main(argc, argv) int argc; char **argv; { while (*argv != argv[1] && (*argv = argv[1]) && (argc = 0) || (*++argv && (**argv && ((++argc)[*argv] && (**argv <= argc[*argv] || (**argv = argc[*argv] - **argv, argc[*argv] -= **argv, **argv += argc[*argv])) && --argv || putchar(**argv) && ++*argv--) || putchar(10)))) ; }ISO C 표준의 5.1.2.2.1장을 참고합시다. 엄밀히 말하면 표준에서는 각 문자열 포인터가 같을 수 없다고 명시적으로 말하는 게 아니라, argv가 가리키는 문자열들을 바꿀 수 있고 그 값이 유지되어야 한다고 말하고 있습니다만, 이러려면 당연히 argv가 가리키는 문자열들이 서로 유일해야 겠지요. ↩