JMK 쓸모없는 vitamin electric nihility

Another Wednesday

주말이 끝나고 내일이면 출근이라고 징징댔는데 벌써 3일이 지나가다니.. 시간 빠르다. 요즘은 회사에 있는 시간이 너무 휙휙 지나간다. 일이 재밌어서 그런가. 관심 있고 해보고 싶던 일 하니까 확실히 재미는 있다. 솔직히, 잘 하던 일 내버려 두고 다른 것 하겠다고 이러는 게 잘하는 것인가 생각이 들 때도 가끔 있긴 하지만.. 흐흐. 그렇다고 평생 변화하지 않을 것은 아니니.

오늘은 퇴근하고 곧장 차 빌려서 Oak Park 에 가서 의자를 사 왔다. 지금까지는 식탁에 딸려온 의자를 쓰고 있었는데, 집이 덥다보니.. 땀도 차고, 여러 모로 불편해서 호시탐탐 벼르고 있던 차였다. 한참 고민하고 여기저기 앉아보다가 낸 결론은 역시 그냥 에어론.. nhn 에서도, DRW 에서도 앉고 있으니 최소한 익숙하긴 하다. 의자 무지하게 튼튼한 것은 잘 알고 있는 데다, craigslist 에서 중고 사면 450불 정도면 살 수 있길래 결국 사버렸다. 어제는 TV 사고, 그제는 맥북 사고.. 지름이 그칠 날이 없구만. 잔고 완전 빵꾸났다.

집에 와서는 라면 먹으면서 벤자민 버튼의 시간은 거꾸로 간다를 봤다. 아무 생각 없이 브래드 피트 나와서 본건데 의외로 슬펐다능.... ;ㅁ; 다 보고 좀 놀다 보니 이 시간이다. 수열이는 나 씻는 사이에 잠들어 버렸다. 나도 어여 자야지.. 'ㅅ')r

AOJ 해야 할 일들 / 하고 싶은 일들

• 문제 좀 더 잘 분류할 수 있는 체계 갖추기
• 리저지 가능한 저지 구조로 변경
• 문제 삭제 및 publish 지원, 레퍼런스 솔루션 별도 업로드 등등...
• sqlite 외에 멀티스레드 지원하는 db 로 변경
• ABCs: 팀 노트북용 라이브러리 테스트 문제들: 이분매칭, 넷웍 플로, MCMF, convex hull...
• 알고스팟 공식 ICPC 소스코드 리포지토리 (?)
• Contest mode, virtual contest mode 추가

SRM447 Practice

A match sponsored by Facebook. Simple simulation 250, Graph + Bipartite Matching 500. I wasn't sure about whether bipartite matching could be the right solution for 500 (I'm so rusty.. of course, this is a classic example of Konig's theorem.) About 1000, so far no idea.

(more)

SRM449 practice

A simple geometry 250, counting 550 and quite tricky 950. I thought I didn't have a chance writing both 550 and 950 in time, and wasted some time looking and thinking about both problems. I finally went for 550 - that proved to be easier than I thought. So the score is not great... but anyway.

Ah, and the source code for this match was committed with revision 1000 of my personal SVN repository.

(more)

Adaptive Simpson's Method

Simpson's Rule 은 적분이 들어가는 모든 문제에 캡숑 유용하게 쓰이는 방법이다. 목적함수를 2차함수로 근사하기 때문에, 실제 목적함수의 차수가 2차 이하의 다항식인 경우에는 귀찮게 손으로 적분할 필요 없이 정확한 답을 구할 수 있다. 당연하지만 이 이외의 경우 -목적함수가 다항식이 아니거나 한 경우-에는 오차가 매우 커진다.

알고스팟 모의고사 준비하면서 sqrt(r^2 - x^2) 를 적분할 일이 있었다. 물론 닥치고 울프람 형아 적분헤 주떼영 하면 되지만 나도 남자의 자존심이 있어서 그건 싫고 -_- 해서 numerical method 를 쓸 양으로 Simpson's rule 을 써 보았다.

lang:py
def f(x):
    return sqrt(1 - x*x)
def simpson(a, b): 
    c = (a+b)/2.0
    h3 = abs(b-a) / 6.0 
    return h3 * (f(a) + 4.0*f(c) + f(b))

하고, -1 부터 1 까지 적분하면 반원의 넓이니까 pi/2 가 나와야겠지.

In [2]: print simpson(-1,1)
------> print(simpson(-1,1))
1.33333333333

깨갱 -_- 0.2나 차이나네; 이렇게 되면 질수없다. 인터벌을 1000개로 나눠서 각각 구간에서 simpson's rule 을 돌리기로 한다.

In [9]: xs = arange(-1,1,0.002)
In [10]: sum([simpson(xs[i],xs[i+1]) for i in range(len(xs)-1)])
Out[10]: 1.5707083802290707

오 꽤 정확해짐. 하지만 아직도 오차 범위가 1e-5 라서 많이 부족하다. (대개 프로그래밍 대회에서는 1e-7 이하의 정확도를 요구한다.) 인터벌을 몇개로 늘리면 될까. 1만개로 테스트.

In [13]: xs = arange(-1,1,0.0002)
In [14]: pi/2-sum([simpson(xs[i],xs[i+1]) for i in range(len(xs)-1)])
Out[14]: 2.7818300534221407e-06

아니 시발 이게 뭐야 -_-; 결국 테스트를 해보니 5만개 정도로는 나눠야 1e-7 정확도를 얻을 수 있다. 물론 일루옹이 낸 문제답게 n 이 작지도 않고.. 이대로는 절대 시간 안에 안나온다. 그래서 써먹은 것이 Adaptive simpson's method.

기본 규칙은 매우 간단하다. 이 함수가 생긴 모양을 봐서 2차 함수로 적절히 근사가 된다 싶으면 그냥 simpson's rule 을 써서 근사하고, 아니면 절반으로 나눠서 divide & conquer. 위키피디아 엔트리 링크

lang:py
def adaptive(a, b, sum, eps):
    c = (a+b) / 2.0 
    left = simpson(a, c)
    right = simpson(c, b)
    if abs(left + right - sum) <= 15 * eps:
        return left + right - (left + right - sum) / 15
    return adaptive(a, c, left, eps/2) + adaptive(c, b, right, eps/2)

15 로 나누는 부분이 매우 맘에 걸리지만 지금은 수치해석시간이 아니니 자세한 분석은 넘어가기로 하고.. (나 수치해석 학점 B 다..) 말할 것 없이 돌려보면

In [31]: pi/2 - adaptive(-1, 1, simpson(-1, 1), 1e-8)
Out[31]: 7.0505905558349014e-09

실제 simpson() 함수가 계산되는 회수를 세어보면 800회정도밖에 안된다. 우훗! 물론 이거야 이 함수가 매우 스무스하게 생긴거라 그러니 오해하면 안됩니다. 여튼 적분하기 싫은 여러분, 이렇게 이겨냅시다 [....]

다시, 월요일

• 6시에 칼퇴근해서 집에 오니 6시 20분. CTA 만세.
• 부인님이 해 주신 크림소스 스파게티를 먹고 설거지를 하고 나니 어느덧 여덟 시. 탑코더를 하고 싶었지만 너무 졸려서 침대에 잠깐 누웠다 깜빡 잠들었다.
• 9시에 일어나서 SRM 449 연습 ㅋ 그냥 550 쭉 풀걸 괜히 950 가서 고민하다가 돌아옴. ㅡㅡ 그래도 패스 패스 ㅠ.ㅠ
• 집에 인터넷이 너무 느려서 인터넷을 별도로 신청함. 한참 리서치했지만 결론은 컴캐스트.. 15Mbps 따위가 이렇게 비싸다니. 지금은 2009년이란 말이다..
• 결국 신청하고 전에 일본 마켓에서 사온 밤빵에 맥주 한잔 하고 이제 잘 예정. 오늘부터 다시 원고하려 그랬는데 흑 내가 그렇지 머 'ㅡ')r

포스팅 제목은 롤러코스터 노래.. 지만 저노래를 별로 좋아하진 않는데 흠...

A Halloween Class Video

Augmented Reality PWNS kkkkkkkkkkkkkkk

주말

금요일 저녁쯤엔 알고스팟 모의고사 마무리 준비하느라고 정신이 없었다. 내가 이번에 거의 진행을 못하고 리베 혼자 진행했는데, 덕분에 리베 유키 일루옹 셋이서 밤새고 나는 회사에서 [....] 문제 번역하고 솔루션 짰다.; 버스 타고 퇴근해서 마무리 준비 열심히 하고.. 대회 시작하고 관전 모드로 저녁을 보냄. 그 와중에 부인님께서 해주신 닭도리탕도 먹었다. 맛있음 <3 대회는 리베의 드림걸이 선전한 코넬의 승리로 끝나고;; 열한신가 열두신가 자러 갔다.

토요일은 월동 준비를 모토로 겨울옷 쇼핑하러 갔다. 시카고는 눈이 많이 내려서 waterproof boots 가 필요하다고 한다. 또 집카빌려서 ikea 가서 러그 교환하고 (보라색 러그 샀음, 지금 깔려있다) 아울렛 가서.. 부츠 사고, 스웨터 하나 사고, 쭉티 쓸어담고 그랬다. 쇼핑 다하고 집카 시간이 다되가서 서둘러 차로 돌아와 시동 걸려는데 시동이 안걸린다. batt low.. 아놔. 집카에 전화하니 다음 reservation 뒤로 미루고, 우리 시간 늘려주고, jumpstart 할 support 를 보내준다고 한다. 와 집카 짱임. 삼십분 동안 차안에서 중부시장에서 점심으로 먹고 남은 깐풍기를 먹으며 기다렸다. 집에 돌아오니 아마존에서 샀던 머신러닝 책이랑 vi/vim 레퍼런스가 와 있다. 이것도 며칠전에 USPS 에서 배송중에 분실되어서, 이메일 보냈더니 삼십분만에 공짜로 one-day replacement order 보내준다고 했던 것이다. 와 아마존 짱임. 그 외에 새로 산 모니터에 white spot 있어서 newegg 에 메일 보냈더니 곧장 RMA 하라고 approval 왔음. 와 newegg 짱임..... 미국 시스템의 긍정적인 면을 많이 보고 있다.

아 여튼 그러고 RPC 하다가 잠. H 미워요 엉엉. G 못푼거는 안습. 전날 다트 문제 validation 하던 기억이 자꾸 나서, 적절하게 그림을 그려서 풀려고만 했던 것이 실수인듯. 그냥 program level optimization 으로 n^3 으로 내리면 된다. C 는 problem statement 문제였고. 역시 페널티로는 존내 짱먹음. 저지가 늦게 되어서 그렇지, 초반 두시간 정도는 일등이었을듯. 물론 결과는 일루옹에게 쳐발림. ㅠ_ㅠ

일요일은 일어나서 하루종일 집에서 뒹굴거림. 원고도 안하고 공부도 안하고 회사에서 갖고온 q 레퍼런스도 안읽고, vim 책이나 좀 읽었다. 내가 모르는 기능 캐많음... 역시.. ㅠㅠ 그렇게 놀다가 세시쯤 나가서 베스트바이 가서 TV 구경. 삼성 52인치 LCD 로 가기로 마음을 정했습니다 ㄳ. 어디서 살지는 좀 더 공부해보기로 하고, 크레잇 앤 배럴 가서 반찬통이랑 과일 포크 등을 쓸어담음. 의자 몇개 앉아봤는데, 영 신통찮은 것들도 400불씩 한다. 이돈이면 에어론을 사겠다 젠장. 치즈케잌 팩토리 가서 케잌 두조각 사왔다가, 이상하게 너무 피곤해서 소파에서 잠듬. 일어나니 아내님께서 저녁식사를 주셔서 맛있게 잘먹고, 설거지 하고, 가십걸 두편 보고 (....) 이러고 있다.

이제 11월, 정착과 고난의 시기였던 10월이 지나가고 본격적으로 "일상" 으로 돌아오는 시기다. right track 을 타도록 열심히 노력해 보아야지.

아 일기 기네

파이썬 중독

lang:cpp
vector<int> range(int n)
{   
    vector<int> ret(n);
    for(int i = 0; i < n; ++i)
        ret[i] = i;
    return ret;
}   

일요일

러그와 기타 잡동사니를 사러 Ikea 에 들렀다가 H마트에 가서 김치와 각종 먹거리를 사오고, 저녁에는 갈비찜을 해먹겠다는 야심찬 각오로 집을 나선 구종만 (27), 하수열 (27) 커플. 생각보다 따뜻한 날씨에 룰루랄라하며 zipcar 를 타고, 대구 매운탕까지 먹고 이케아로 향했는데.... 지난 3주 동안 밥먹고 쇼핑만 했는데 왜 아직도 이렇게 살것이 많은지.. 살림을 차리는 것은 실로 힘들다. 결국 zipcar 밤 열한시까지 연장하고 열심히 샀다. 마지막에 산 TV장이 차에 안들어가서 십분동안 낑낑대고 결국 상자를 전부 해체해서 넣었음. -_-;

저녁을 먹으려고 근처에 있는 일본 마켓에 가서 돈코츠 라멘을 먹고 (찻슈덮밥 하악하악) 좀 기운이 나서 마켓 식료품 코너를 돌아보니 와 이곳은 신천지 +_+ 먹고 싶은게 왜이리 많은지;;; 한참 과자와 팥빵과 카스테라와 등등;; 을 쓸어담고 이미 꽉찬 차에 비닐봉지를 꾸역꾸역 채워넣고 기십마일을 운전해 시카고로 돌아왔다는 훈훈한 스토리...

집에 오자 마자 짐 올리고 죽도록 짐 정리하고, 사온 커피 테이블이랑 책상 오거나이저 조립하고 나니 기운이 하나도 없어서 모니터 앞에서 맥주와 함께 도라야키를 먹고 있다는 스토리였습니다. 야 신난다.

SRM451 - BrickPuzzle

어제 못푼 그문제.

어제 코딩하다가 너무 졸려서 잠들고, 아침에 침대에서 비몽사몽간에 일어나서 컴퓨터 앞으로 기어와 간신히 풀었음. N 이 작았으면 사용했을 O(2^N * N^2) 어프로치를 최적화해서 푸는 것이 포인트.. 였는데, 아레나에서 1.93초 나오네... 역시 인생은 아슬아슬한 게 맛이라능.. -_ -;; 가능한한 모든 것을 Precalc 했다. 가능한한 메인 루프에 들어가는 내용을 줄이는 것이 포인트. unsigned 를 써서 -1 과 INF 를 같이 쓰는 전법; 을 사용해 보았는데 생각보다 쉽게 되더라는..

눈물의 소스 코드 ...