JMK 쓸모없는 vitamin electric nihility

시개작 환송회

약 한달 반 전쯤 되나? 인사동에서 모였을 때의 사진. 하드 정리하다 찾아서 올려본다. 이렇게 사진을 보고 있노라면 집을 떠나왔다는 게 실감나곤 한다. 아 그리고 사진 업로드 졸라 느릴때도 실감난다.

애플+일기

수열이가 맥북프로를 쓰기 시작한지 3일째. 나는 노트북은 쓸 일도 없을 뿐더러, 처음 써보는 맥 잡으면 적응하느라 한참 짜증날 걸 알면서도 역시 탐이 난다. 블링블링한 인터페이스를 보고 있으면 단축키 설정하느라 그나마 있던 특수효과도 다 꺼버리고, 종종 폰트 렌더링도 정말 구린 투박한 리눅스 데스크탑이 갑갑하기조차 할 정도. 하여간 이쁜건 정말 중요하다. 애플이 정말 물건은 이쁘게 잘 만드는구나. 아이팟에 아이폰에 맥북까지 샀으니 이제 나도 장호형처럼 27인치 아이맥사면 애플 덕후 인증인가...

사실 요즘 리눅스 데탑에서 뭐 좀 안되서 짜증날 때면 내가 뭐하러 이 삽질을 하고 있나 싶을 때도 있긴 하다. -_-; 그래도 개발은 리눅스에서 해야하니까. (뭐 그렇다고 요즘 딱히 뭐 개발하는건 아니다..) 오늘은 노트북 쿨러를 사와서 예전에 쓰던 R6 에 물리고 외장하드 두개를 끼워서 삼바 서빙용 홈서버로 만들었다. 우분투는 예전에 듀얼 부팅으로 깔아놓았고, 토렌트랑 파일 서빙만 하더라도 남는 장사인 것 같아서. 노트북 사실 쓰지도 않고 열도 좀 있어서 팔아버릴까 생각했지만, 이런 물건 팔릴지도 모르겠고 (나같아도 넷북 사겠다...) 이거 팔면 또 베어본 시스템 사서 셋업하느라 삽질해야 되잖아. .. 그런이유로 2년간 잘쓴 내 노트북은 TV밑에서 오늘도 열심히 가십걸 새 에피소드를 받고 있다. 그런 셋업 하고 외장하드 정리하느라 오늘 저녁이 날아감.

오늘 회사에서 너무 피곤해서 오늘은 기필코 일찍 자리라 했는데 또 열한시 반이다. 주여!

PKU3740 Time Attack: gradual optimization

어제 자기 전에 IRC 에 가보니 사람들이 열심히 pku 문제 하나 를 잡고 숏코딩과 타임어택을 하고 있었다. 숏코딩은 whitespace 포함 가장 작은 소스코드로 문제를 푸는 것이고, 타임어택은 가장 짧은 시간 걸려서 문제를 푸는 것. 아기 코끼리 덤보마냥 귀를 팔락거리면서 말려서 결국 타임어택에 도전했다. 641ms 였던 프로그램을 16ms 로 낮추면서 가장 낮은 시간 중 하나 가 됨. pku 저지의 timing resolution 때문에 아마 이보다 낮은 시간은 puts("output file"); 아니면 불가능하지 않을까 생각됨.

비교적 가장 단순하고 무식한 코드에서 시작해서 bottleneck 을 없애고 알고리즘을 최적화하는 방식으로 진행했기 때문에, 나름대로 재미있을 것 같아서 각 단계별로 소스코드를 모아보았다. ...

잠이 안 온다

괜히 치킨이 먹고 싶어서 파파이스에서 치킨이랑 샌드위치를 사 왔다가, 샌드위치만 먹고 치킨은 느끼해서 못먹고 다 버렸다. 그리고 소파에 잠깐 누워서 Doron 이 빌려준 Elements of Statistical Learning 읽다가 깜빡 잠들었다. 정신 차려보니 열 시. 온 몸에 기운이 하나도 없는 게, 피곤하긴 피곤하구나 싶었다. 겨우겨우 일어나서 컴퓨터를 켰지만 뭐 제대로 된 일을 할 기운도 없고.. 해서 일찍 누웠는데, 영 잠이 안 온다. 오랜만에 기름기 많은 것을 먹어서 그런가.

하여간 열심히 시간낭비 하다가 와서 일기써본당

.vimrc

(more)

최근 듣는 노래들

• W&Whale
• 아웃사이더
• 이승환 옛날 노래들
• 두번째달
• 브로콜리너마저
• 허경영 -_-;

SRM440 연습

250 열어보니 이전에 돌았던 셋 같은 느낌이 강하게 들었지만 그냥 돌았음. binary search 250 과 DP 500, 그리고 DP 1000 으로 구성된 셋. 500 은 느리긴 느렸는데 풀긴 풀었고, 1000 은 한참 헤매다가 설마 이게 될까? 하고 1시간 17분째에 냈다. 결론은 PPP ㅠ 만세

(more)

SRM 446 연습

안드로.txt

250 을 쉽게 푼건 좋았는데, 500 에서 사상 최대의 삽질 시나리오.

• string 출력이라, 답의 범위는 long long 이지만 bigint 인 줄 알았다.
• 존내 고생해서 bigint 로 O(lgT * n^2) 솔루션을 짬.
• 문제 잘못 읽음. matrix 고쳐서 walkaround 만듬.
• 너무 느리다.
• 존내 최적화.
• long long 인걸 커피가 가르쳐줌 => long long 으로 변경
• 틀림.
• 1에서 1로 가는 사이클 길이가 음수일 때도 그냥 끝내는 게 나을 수 있다는 점을 신경 못썼음.

.. 뭐 이런 시나리오. 1k 는 일단 어떻게 푸는지 감도 안오고.. 소스코드가 맘에 안들어서 다시 매크로를 쓰지 말까 하는 생각을 하고 있음.

(more)

UVA10403; Escape From Tut's Tomb

문제 링크: 몇년째 풀진 못하고 고민만 하던 문젠데, 결국 탑코더 포럼에 올려서 질문하자, "백트래킹으로 되요" 라는 대답이... 헐... 난 왜 이렇게 할 생각을 못해봤을까. (당연히 시간 안에 안나올 줄 알았지. orz) 자료구조도 모호하게밖에 생각 안 나고.. 해서 그냥 냅뒀는데, 이렇게 간단하게 풀릴 줄이야. ㅠㅠ

막상 짜보니 랭크리스트 1등.... orz

(more)

Linear Fractional Programming

After ACM ICPC Seoul Regional 2009, I hear problem D could easily modeled as a Linear Fractional Programming problem; lewha0 pointed me to the solution of this kind of problem before - here's a brief review of the solution.

Problem

Given a sequence of 0 and 1's, return a continuous subsequence with maximal average. The subsequence must not be shorter than L.

Solution

I am aware of two approaches.

1. Try every length up to 2L: given a subsequence of length 2L, by pigeonhole principle, one of the two L-length halves has the same or better average.
2. Generalize the problem and use LFP.

LFP can solve this generalized version of the problem: Given A[] and B[], return max interval (i, j) where (A[i]+..+A[j])/(B[i]+..+B[j]). In this problem, A[] is either 0 or 1, and B[] is always 1.

Let's start with a guess; will the final solution be smaller than x? Let us assert x is an upper bound of sum(A[i..j])/sum(B[i..j]), for all possible interval,

Rearranging, we get

So is an upper bound if and only if for every possible interval , the above equation is positive. We can easily check this by calculating the vector and find the interval with minimum sum - and see if it's less than zero. If it is greater than zero, is indeed an upper bound.

Now, we can easily do binary searching over possible ranges of .

source code follows ...