구사과

알고리즘을 모델링하는 여러 방법 중 하나는 Decision Tree이다. Decision Tree에서 알고리즘은 입력의 특정 부분을 읽어서 읽은 결과에 따라 YES / NO verdict를 결정하고, 비교 결과에 따라서 두 상태 중 하나로 분기한다. 예를 들어서 비교 정렬에서는 $x_i, x_j$ 를 읽은 다음에, $x_i - x_j$ 의 부호에 따라서 YES / NO verdict를 결정하고, 이 결과에 따라서 두 개의 자식 상태 중 하나로 분기한다.Decision Tree의 최대 깊이는 보통 알고리즘 시간 복잡도의 lower bound를 구성하는데 자주 쓰인다. 비교 정렬에서는 결과 상태가 최소 $n!$ 개이니, 최대 깊이가 적어도 $\log_2 (n!) = O(n \log n)$ 이고, 그래서 모든..

Part 3. Oregon Coast보스턴으로 가는 비행기가 밤 11시 정도로 잡혀 있어서 Oregon Coast를 크게 한 바퀴 돌고 올 계획을 짰다. Oregon Hwy 34가 뭔가 구불구불하고 재밌어 보여서, 그 길로 서쪽으로 들어간 다음에 해안을 따라 북쪽으로 올라오고, 남는 시간에 따라 적당히 포틀랜드로 복귀할 생각을 대충 했다.가는 길에 Alsea Falls라고 하는 곳을 들렀다. 작은 강이 폭포를 이루고 있다.몰랐는데 이 지역은 rainforest가 형성되어 있어서 특이한 이끼가 낀 나무들을 많이 볼 수 있었다. 올림픽 반도 같은 곳에만 있는 줄 알았는데, 오리건 해안가에도 rainforest가 있다고 한다.더 달려서 해안가에 도착했다. Hwy 34는 그냥 나무가 많고 되게 구불구불했다. 추..

Part 1: San Francisco, CA7.18이 전날 밤에 하루 종일 잠을 못 자고 밤을 샜다. 생활 패턴 문제가 아니라 누워서 못 잔 것이고, 잠을 못 잘만한 개인적인 이유도 있었다. 당연히지만 뜬 눈으로 밤을 지새우니 고문이 따로 없었고, 사람을 보러 나가지 않으면 해결이 안 될 것 같았다. 내가 보스턴에서는 당분간 볼 만한 친구가 없어서, 이 연옥을 탈출하기 위해서는 샌프란시스코라도 가야 하나 하는 생각이 들었다. 그렇게 더 생각해 보다 지금 내가 할 수 있는 최선인것 같아 바로 추진했다.오전 11시 반에 친구한테 소파에서 잘 수 있는지를 물어봤고, 와도 된다는 답장을 받았다. 답장을 받은 즉시 오후 2시 비행기를 예약하고, 가방 하나만 들고 샌프란시스코를 향했다.친구 집에 도착해서 굴국밥을..