Day 2 Western Montana - Near Glacier National Park 6시 반 좀 넘어서 일어났다. 잠은 그런대로 잤지만, 썩 개운치는 못하게 일어났다. 창문을 열어보니.. 어제 오후와는 완전히 다른, 그림같은 설원 속에 있었다. (사진은 그림같이 않음에 양해를 부탁한다. 동영상으로 찍은 경우가 많아 그렇다) 아직 진짜는 시작도 안 했으니, 바로 아침을 먹으러 간다. 아침도 몇 가지 옵션을 선택할 수 있다. 나는 스크램블 에그로 골랐다. 아침을 같이 먹었던 대학생은 캐나다에 있는 집으로 가기 위해 기차를 탔다고 했다. 보통은 집에 갈때 6~7시간 정도 운전해서 가는데, 지금은 고속도로가 빙판이 되어 있을 것 같아서 기차로 간 후 역에서 부모님이 픽업해주시기로 했다고. 기차가 미국의 ..
정말 갑작스럽지만, 저번 주 3주 전 6주 전 (...) 암트랙의 Empire Builder를 타본 후기를 써 보려고 한다. 3월 6일 ~ 3월 8일은 공휴일이 끼어 있는 주도 아니고 아무 일도 없는 시기지만, 과제가 없길래 2주 전쯤에 충동적으로 티켓을 구매했다. 보스턴 → 시애틀 비행기, Empire Builder, 시카고 호텔 1박, 시카고 → 보스턴 비행기 표를 끊고, 평소처럼 살다가 전날 최소한의 준비물만 챙겨 출발했다. Day 1 Seattle 4시 반 기상 후 Boston Logan에서 6시 50분 비행기를 타고 시애틀로 갔다. 비행 시간은 약 6시간 정도로, 시차 때문에 3시간이 당겨져서 도착 시간은 10시였다. 몇천 km를 넘어서 Pacific에 왔다는 실감은 그다지 들지 않았다. 날씨가..
Undirected graph $G = (V, E)$ 에 대해, $G$의 $t$-spanner $H = Spanner(G,t) = (V, E^\prime)$ 는 다음 성질을 만족한다: $E^\prime \subseteq E$ 모든 $u, v \in V$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작음 즉, 최단 경로를 Approximate하게 보존하는 Sparsification이다. Equivalent하게, 다음과 같이 표현할 수도 있다. $E^\prime \subseteq E$ 모든 $(u, v) \in E$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작..
- Total
- Today
- Yesterday