Welcome 2013

악몽 같았던 2012년이 드디어 지나갔다.

2013년엔 제발 정상적인 일들만 일어나길.

절망

과정이 공정하지 못했다고 말하고 싶은 것은, 결과가 정의롭지 못한 이유가 과반수의 국민이 너무나도 멍청한 바보이기 때문이라는 것을 도저히 인정하고 싶지 않기 때문일 것이다.
어쨌건 대한민국은 가장 훌륭하고 탁월한 나라가 될 수 있던 기회를 걷어차고 미래가 없는 나락을 선택했다. 대다수의 국민이 어리석은 경우, 민주주의는 실패한다는 교훈만을 남겨두고.

바보

버스를 타야하는데
아무 생각없이
지하철역을 향해 걸었다.

어깨엔 한가득
짐을 지고.

그러면서 생각했다.
지하철역으로 가는
지름길을 알고 있다니,
나는 너무 멋져.

하인리히 슐리만의 외국어 공부

하인리히 슐리만이라는 사람이 있다. 트로이 유적을 발굴한 것으로도 유명하지만 외국어 하나를 유창할 정도로 익히는데 6주 정도면 됐다는 걸로도 유명하다. 그가 쓴 자서전 중 외국어 공부에 해당하는 일부를 발췌해서 누군가 인터넷에 올려놓은 것을, 어떤 한국사람이 한국말로 번역해서 또 인터넷에 띄워놓았고, 그래서 꽤 널리 그 글이 퍼나르기 형태로 인터넷에 퍼진 듯 하다. 나는 처음에 영어로 된 발췌문을 접했고, 오래지 않아 한국어로 번역된 것도 접했었다.

인터넷에 뒤져보면 거의 대동소이한 내용만을 볼 수 있는데, 여기에는 다른 발췌문에 비해 꽤 자세한 내용이 소개되어 있다. 아마도 국내에 번역되어 판매된 슐리만의 자서전을 직접 읽고 발췌/요약한 것 같다.

그 언어로 된 책을 거의 통째 암기했다고 하니 그 집중력과 노력이 혀를 내두를 지경이지만 (저 정도 공부했는데 마스터 못 하면 이상하지.. 하고 금방 수긍하게 된다고나 할까), 인터넷을 아무리 뒤져봐도 슐리만과 동일한 방식으로 외국어를 마스터했다는 사람을 찾을 수가 없다. 애시당초 불가능한 일이 아닐까 할 정도로.

그러나 어째건, 그의 방식이 큰 참고가 됨에는 틀림이 없다. 슐리만 그가 6주가 걸렸다면, 나는 6개월 만에 될 수 있을까? 만약 그렇다면, 앞으로 6개월 동안 그의 흉내를 한번 내보는 건 어떨까.

코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이 (2)

factorial_10000

앞에서의 문제를 남들은 별 해괴한 언어로 풀길래, 나도 한번 똑같은 문제를 C 언어를 사용해서가 아닌 좀 다른 언어를 사용해서 만들어보았다.  바로 graphical language 라고 할 수 있는 simulink 이다.

별 문제 없이 슥슥 만들 수 있을 줄 알았는데 왠걸, 예상보다 상당히 오래 걸렸다. 기존의 절차형 프로그래밍과는 미묘하게 다른 제어용 프로그래밍인데다가, simulink 의 while 문이 익숙지 않아서 (리얼타임 제어에서 while 문을 써 봤을 리가-_-) 헤매다가 에잇 때려치워 하고는 마구잡이로 만들어버렸다 (…)

자세한 건 좀 이따 말하기로 하고, 일단은 실행화면이다. 첫번째 문제, 2012! 구하기.


답으로 0이 501개, 0이 아닌 마지막 수 8이 잘 출력된 걸 알 수 있다. 그다음 문제, 10000! 구하기 스샷.

0이 2499개, 0이 아닌 마지막 숫자 8이 제대로 출력된다.

전체 simulink 모델이야 위 스샷에 이미 다 나와있고, sub block 들은 다음과 같이 작성했다.

글자 그대로 factorial 을 계산하는 블럭이다. 출력1을 feedback 해서 입력2로 넣어주면 되는 구조이다. 물론 이 프로그램에서는 그대로 입력으로 넣어주지 않고 숫자를 줄이기 위한 트릭을 사용한다.

입력의 숫자에서 뒤에 0이 몇 개인지 보고 0의 갯수와 0을 잘라내고 남은 갯수를 구해내는 블럭이다. 이 sub model 이 제일 아쉬운데, is remnant zero 블럭을 1개만 써서 만들어보고 싶었지만 잘 되질 않아서 저렇게 만들어버리고 말았다. 향후 수정이 필요하다. (흑흑)

위 zero truncate 블럭의 sub block 이다. C 언어로 치자면 % 연산을 해서 0으로 나눠 떨어지는지 여부를 알려주고 / 연산의 값을 출력한다. simulink 내에서 matlab 서브루틴을 사용하면 간단히 되겠지만 이번에는 simulink 를 고집했기 때문에 이렇게 만들었다.

이건 큰 숫자에서 연산으로써 의미가 있는 뒷자리만 잘라내는 블럭이다. 그리고 프로그램 종료까지 확인해준다. 이것도 switch 블럭을 마구 쓰지 않고 뭔가 쌈빡하게 하는 방법이 있을텐데, 귀차니즘의 발동으로 그냥 저렇게 만들어버렸다. (뭐 어때! 돌아가기만 하면 되지! 주의랄까 -_-)

프로그램이란 것이 만들어놓고 나면 항상 아쉬운 법이라, 언제 한번 시간을 내서 좀 더 멋지게 다듬어볼 생각이다. 버뜨 회사 프로젝트 마감일이 목을 졸라와서-_- 일단은 이정도로 만족하기로 한다.

코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이

도서출판 인사이트에서 진행하는 알고리즘 코딩 이벤트 문제가 재밌어보여서 집에 와서 잠깐 만들어보았다. 문제는 다음과 같다:

자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예]

input n: 15
output: 3 8

[설명]

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

(전체 문제는 여기를 참조.)

별로 어려울 것은 없었지만, 초반에 약간의 시행착오가 있었다. 좀 궁리해봤더니,

“임의의 수x와 n 자리수의 값의 곱을 y라고 할 때, y의 n자리수에 영향을 미치는 x의 자리수는 n”

이라는 것을 알 수 있었다.

즉, 12345 * 99 = 1222155 이지만, 결과값의 마지막 두 자리수 55를 얻어내려면 12345의 마지막 두 자리 수, 즉 45만 사용해도 된다는 것이다. 45 * 99 = 4455 로 마지막 두자리 수 55를 얻어내는 데는 충분하다.

수학적으로 잠시 증명하자면, 위의 경우 12345 는 12300 + 45 로 따로 생각할 수 있기에 12345 * 99 = 12300 * 99 + 45 * 99 가 되는데, 12300 * 99는 이미 마지막 두 자리수에 영향을 주지 못하므로 45 * 99 만 계산하면 된다는 걸 알 수 있다.

어째건간에 위의 성질을 이용하면 100보다 작은 수를 곱할 때는 곱해지는 수는 마지막 두 자리수만 고려하면 되고, 마찬가지로 1000보다 작은 수를 곱할 때는 마지막 세 자리수만 고려하면 되고, 10000보다 작은 수를 곱할 때는 마지막 네 자리수만 고려하면 된다. 아 물론, 10보다 작은 수를 곱할 때는 마지막 한 자리수만 고려하면 된다.

프로그램은 C로 작성했다. 프로그래밍 자체는 별다른 트릭이 없다. C 언어에서는 함수 리턴값이 하나로 제한적이므로 재귀호출을 좀 더 멋지게 사용하지 못하고 전역변수를 써버린게 좀 억울하달까. 파이썬으로 했으면 좀 더 멋지게 했겠지만, 집에서 쓰는 컴에는 파이썬을 깔아놓질 않았다;

자 이제 쏘스 난무다.

#include <stdio.h>
#include <stdlib.h>

int last_facto = 1, num_zeros = 0;

void factorial(int num)
{
if(num == 1)
{
last_facto = last_facto % 10;
return;
}

last_facto = num * last_facto;

while(last_facto % 10 == 0)
{
num_zeros++;
last_facto = last_facto / 10;
}

if(num < 10)
{
last_facto = last_facto % 10;
}

else if(num < 100)
{
last_facto = last_facto % 100;
}

else if(num < 1000)
{
last_facto = last_facto % 1000;
}

else if(num < 10000)
{
last_facto = last_facto % 10000;
}

factorial(num – 1);
}

void main(void)
{
int num;
printf(“input n: “);
scanf(“%d”, &num);

factorial(num);

printf(“output: %d %d\n”, num_zeros, last_facto);
return;
}

문제에서 요구하는 결과인 2012!는 끝의 0의 갯수 501, 0 이전의 마지막 수 8이고, 10000!은 끝의 0의 갯수 2499, 0 이전의 마지막 수 8이다.

실행 결과 화면

희랍어 공부

여름 휴가 시작과 함께 희랍어 공부를 중단하고는, 여름 휴가가 끝난지가 언젠데 아직까지 공부를 손 놓고 있었다. 어제 겨우 겨우 책을 집어들었는데, 한 달 가까이 공부를 쉬었더니 기억 안 나는 단어가 왜 이렇게 많은지… (한숨)

희랍어 공부가 아무리 재밌어도 (실제로도 재밌다), 매일 꾸준히 공부를 계속 한다는 건 대단한 자신과의 싸움이다. 사실 희랍어 공부 외에도 세상에 재밌는 일은 너무나 많기 때문에. 사람이 금욕하면서 살 수는 없겠지만, 될 수 있으면 다른 곳에서 재미를 찾지 않고 공부에서 재미를 찾도록 해야겠다.

희랍어가 좀 수월하게 읽히기 시작하면 좀 나아질텐데. 그 날이 어서 오기를 기대해본다.