무한도전?

요즘 인터넷에 무한도전 출연 연예인들이 뉴욕가서 바보 짓 하고 왔다고 타블로 형이라는 사람이 비난 글을 올려서 떠들석하다. 나라가 작다보니 누가 글 하나 올리면 난리도 아니다..ㅎㅎㅎ

연예인 형도 공인 취급 받는 한국을 보면 대단해 보이기도 하고 좀 우습기도 하고 그렇다.

노이즈 마케팅이라면 성공적인게 도대체 무슨 짓을 하고 왔나고 다시보기로 봤더니 별 내용도 없더라니..

젤 말이 많았던게 박명수가 피자집가서 미국 사람들이 잘 먹는 피자가 머냐고 물어보고 싶었는데 영어가 잘 안되어서 점원이 주는대로 먹으라고 했다나...하는 부분인데 사실은 꼭 그렇지도 않은 것 같았다.

설령 주는대로 먹으라고 손 치더라도 어쩌겠냐...거기서 자존심 세우면서 손짓 발짓하면서 다른거 먹으면 자존심이 또 사나? 어찌 되었던 누구나 집에서 큰소리치지 밖에서는 찍소리도 못한다. 굳이 외국을 말하는게 아니라...

집에서야 가장이라고 와이프나 애들한테 할말 하고 살지..물론 능력 없는 가장은 그것도 못하지만...ㅡㅡ;;

여하튼 회사가면 상사한테 찍 소리 못하지...돈없이 어디 좀 돌아다니려면 여기저기서 개무시하지..

설령 대통령인들 아프리카 한복판에 떨어져서 말 안통하는데 자존심 챙기고 있으면 우스운 꼴 당하는 거다..

결국 미국에서 영원한 이방인으로 개무시 당해 생긴 피해의식에 쩔은 타블로 형의 설익은 비난은 땅으로나 여론으로나 좁은 한국에서나 생길 헤프닝으로 밖에 볼수 없다..

비타민

스웨덴 오고 나서 해가 장 시간 떠 있는 날이 처음인 것 같다.

하늘이 유난히 푸르고 구름 한점 없는 화창한 날씨다. 며칠 전에도 아침 나절에 잠시 해가 떴다가

교수가 와서 해떴다고 좋아라 자랑하듯이 나한테 얘기하고는 한두시간 있다가 다시 비가 내리더니..ㅡㅡ;;

오늘은 이상하게 오후가 넘도록 해가 떠 있다.

아마도 겨우내 해 떠 있는 일주일 중에 하루가 아닌가 싶다.

어제 저녁에 파스타 통조림을 먹겠노라 들고 왔다가 뚜껑을 열었더니 어이 없게도 소스만 있는것이다..ㅡㅡ;

이런 된장...

결국은 일찍 집에 들어가서 면 삶아서 먹었다..ㅡㅡ;;

집에 사다 놓은 파스타 캔이 대체 머가 안에 들어 있는지 몰라서 아침에 마트가서 냉동 식품을 사들고 왔다.

계산하면서 계산대 옆에 비타민이 보이길래...종합비타민제는 밥값이 현재 없어서리...리임버스 받아야 ㅠㅠ

비타민 c도 부족할 듯하여...과자 같이 생긴 비타민을 하나 샀다. 안에 20정 들어있는 오렌지 맛으로..

주말이라 버스가 자주 없는 탓에 기다리기 적적해서 비타민이나 먹을까 해서는 하나를 입에다 넣었다.

아무 생각없이 한국 약국에서 파는 씹어 먹는 비타민 정이려니...슈퍼서 파는데 오죽..

이거 웬걸...입안에서 느낌이 이상하다 싶었다. 첨에는 알싸한게 음..특이하군...이라 생각했는데

점점 입안에서 먼가 나오는 것이다. '젠장...이거 발포성 비타민제인가 본데...ㅡㅡ;;' 라는 생각과 더불어

거품이 생기기 시작했다. 순간 이걸 뱉어야 하나? 라고 고민이 생기면서도 한 알에 얼마지? 하는 생각까지 났다.

에고...그냥 조금씩 넘겨야 겠다...라고 생각하고 조금씩 넘기는데 맛또한 좋지 못했다. 탄산 거품만 계속 먹으니 약간 구역질 같은 것도 낫다...ㅠㅠ

반쯤 먹고는 안되겠다 싶어서...씹어서 삼키면 되겠지 하고는 씹었다..

하지만 그건 완전 잘 못된 생각이었다. 씹는 순간 마치 원자 폭탄이 입안에서 터지듯 개거품이 순식간에 발생했다. 입안에 거품이 가득 차기 시작했지만 도저히 삼킬 수가 없었다...ㅡㅡ;;

주변을 둘러 보다 물건이 쌓여 있는 뒷 쪽으로 가서 뱉어 냈다. 거품이 한가득 바닥에 나오면서 웩 거리는데

지나가던 할머니가 나를 이상하게 쳐다 보면서 갔다. ㅡㅡ;;. 어글리 아시안이 침뱉나? 하고는..

젠장...학교와서 구글에 해석해보니 하루에 한정씩 물타서 먹으라고 나와있다.

앞으로는 좀 읽어 보고 먹던지 해야겠다...

Cut vertices

Problem statement, introduction to algorithm

A cut vertex (in a connected, undirected graph) is a vertex whose removal disconnects the graph.

A simple algorithm for identifyiing cut vertices:

  1. For each vertex w, remove w from the graph and see if the graph becomes disconnected, using DFS or BFS.

Time for this one is O(n(n+m)), where n=#vertices, m=#edges.

To get a faster algorithm, consider the DFS tree of the graph. In particular, consider the back edges:

The graph is on the left, the cut vertices are in green.

The DFS tree is on the right, the back edges are the dotted edges.

Claim: A non-root vertex U is a cut vertex if and only if one of its children W in the DFS tree has the following property:

• there is no descendant of W with a back edge reaching above U.

To determine whether this property holds for a vertex, define:

• The dfs-number of each vertex by labelling the vertices 1,2,...,n in the order in which DFS first encounters them. Above, the dfs-number of each vertex is shown in green next to the vertex.
• For each vertex v, define low[v] = min { dfs-number[v] , min { dfs-number[w] : (u,w) is a back edge for some descendant u of v }}. That is, low[v] is the smallest dfs-number reachable by taking tree edges down from v and then at most one back edge up.

Claim: A non-root vertex U in the DFS tree is a cut vertex if and only if one of its children W in the DFS tree has:

• low[W] >= dfs-number[U].

(Prove this later.)

Claim: A root vertex is a cut vertex if and only if it has two or more children in the DFS tree (using just tree edges).

(Prove this later.)

Claim: the low[] numbers satisfy the following recurrence relation:

• low[v] = min { dfs-number[v], min {dfs-number[w] : (v,w) is a back edge}, min {low[w] : w is a child of v in the dfs-tree } }

(Prove this later.)

To finish, the low[] numbers can be computed bottom-up using the DFS tree using the recurrence. This computation takes O(n+m) time.

To summarize, here is the outline of an O(n+m)-time algorithm for identifying cut vertices:

1. Do a DFS on the graph.
2. Compute the dfs number for each vertex.
3. Compute the low number for each vertex.
4. The cut vertices are the non-root vertices U having a child V such that low[V] >= dfs-number[U], plus the root vertex, if the root vertex has degree two or more in the dfs tree.

Proving the claims

The argument for correctness of the algorithm rested on the following three claims:

1. A non-root vertex U is a cut vertex if and only if one of its children W in the DFS tree has the following property:

there is no descendant of W with a back edge reaching above U.

2. The root vertex of the dfs tree is a cut vertex if and only if it has two or more children in the DFS tree (using just tree edges).

3. The low numbers satisfy the following recurrence relation:

low[v] = min { dfs-number[v], min {dfs-number[w] : (v,w) is a back edge}, min {low[w] : w is a child of v in the dfs-tree } }

---

To verify the algorithm, we need to consider carefully whether the claims are true. In particular, are we convinced the claims will hold when the algorithms are run on any input.

Next we will do this, partly, to give an idea of what's involved.

For the first claim to be true, it must be that, for any input,

1A. If a non-root vertex U is a cut vertex, then it will have a child W in the DFS tree such that no descendant of W has a back edge above U.

and

1B. If a non-root vertex U has such a child, then it is a cut vertex.

The second part (1B) is easy to argue for. If U has a child W, with no descendant of W having a back edge going to a vertex above U, then removing W disconnects the child from the parent of W.

The first part (1A) is a little less obvious. We tried to come up with a line-by-line justification:

1. Suppose U is a cut vertex.
2. Removing U from the graph separates the graph into at least two components.
3. The root R of the DFS tree is in one of these components, say, C.
4. There is at least one other component, say, C'.
5. Let W be the first vertex in C' encountered by the DFS.
6. Then consider where W has to be in the DFS tree...

• Since all paths from R to W go through U, W has to be a descendant of U in the DFS tree.
• Since W is the first vertex in C' encountered by the DFS, W has to be the immediate child of U in the DFS tree.
• Since all paths from R to W go through U, there cannot be a descendant of W that has a back edge going above U.

This seems to be a convincing and general argument that (1A) is true. If we accept this argument, then we believe (1A) is true. If we accept that (1B) is also true, then we believe claim (1).

Note that to really convince ourselves that the algorithm is correct, we need to verify also that claims (2) and (3) are correct. We leave these as exercises (for claim (3), see DynamicProgramming).

---

References

• CormenEtal? problem 23-2 (Articulation points)

늙는다

사람이 나이가 되면 쉬이 늙는다더니 요즘 그 말을 통감한다.

가끔 화장실 다녀 올때 거울에 비친 내 모습이 낯설을 때가 종종 있다.

어제 다르고 오늘 다르다더니...이제 나도 나이가 들었구나..하는 생각이 든다.

세월엔 장사없다고 하는데 역시 나이는 못 속이나 보다.

그렇고 보면 사람이란 아둔한 동물임에 틀림없다. 영장류라 잘 난척하지만 결국 하는 짓이란

동네 강아지하는 짓이랑 뭐가 다를게 있을까 싶다.

먹고 자고하는게 결국 다인데 거기에 무슨 각가지의 의미를 부여하게 되었는지 모르겠다.

그러고는 거기서 스트레스 받곤 한다.

이래도 한평생 저래도 한평생 너무 짜증내면서 살지 말자..

웃으면서 살자..ㅎㅎㅎ

웃어 생기는 주름은 보기에 나쁘지도 않다더라...ㅎㅎㅎ

디자인 강국

유럽 국가들이 디자인이 강하다는 사실은 누구나 잘 알고 있는 사실이다.

하지만 각 국 마다 차이는 있는 듯하다. 날씨와 민족성이 연관이 크듯이 디자인도 성격을 반영하는게 아닐까?

스웨덴에 와서 디자인에 대한 생각이 많이 바뀌었다.

미대를 나오지는 않았지만 아는 친구들이 하는 디자인이란 무척 화려하기도 하고 멋스럽기도해 보였다.

특히나 산업 쪽은 모던해 보이려고 노력하는 것 같은 느낌을 많이 받았던 것 같다. 그것이 이노베이티드 된 거라고 믿는 것일지도 모른다.

북유럽 디자인 코드는 한 마디로 심플이다. 절제된 선과 불필요한 부분에 대한 과감한 제거?

물건들이나 시설이 다소 딱딱해 보이지만 반면 컬러나 조명을 적절히 사용하여 느낌을 부드럽게 해 놓았다.

결정적으로 이 디자인의 특징은 편의성이다.

실 생활에서 물건들을 사용하다보면 감탄사가 절로 나오게 된다. 왜 우리 나라에는 이렇게 안만들었지?

그것이 첨단 테크를 사용하는 물건이 아니라는 것이 놀라운 점이다. 우리나라도 이제 기술 후진국은 아니다.

그냥 평범한 일상에서 자주 사용하는 것들...욕실 물품, 부엌 용품, 사무 용품 같은 것들이다.

디자인들이 투박하다 싶을 정도로 직선적이고 처음 보는 사람도 직관적으로 사용할 수 있다.

하지만 전체적인 조화는 디자인의 묘미를 극대화 시켜 준다.

난 디자인에 대해 우매하다. 전무후무한 자의적 지식 밖에 갖추지 않은 나조차도

생활에서 느끼는 디자인에 대한 우수성을 쉽게 접할 수 있다.

역시 선진국은 다르다..ㅡㅡ;;

적응 기간...

나이가 들어서 인지 요즘 느끼는 건 시차 적응이 빨리 안된다는 거다.

예전에 한창 나이때는 하루 안자고 버티면 담날 부터는 금방 적응이 되더니 여름에 한국 들어가면서 느낀거지만

거의 일주일 이상이 걸리는 듯 하다. 혹자는 하루에 한시간 정도 극복한다고 한다. 그럼 9일?? ㅡㅡ;;

여하튼 초저녁에 졸려 죽고 새벽에 말똥 말똥 해져서는 어제도 3시에 일어나서 6시까지 문서 작성하고 잤다. 덕분에 아침에 늦게 출근하긴 했지만 서도...ㅡㅡ;;

학교 일은 거의 셋업이 다 되었다. 방 키랑 출입 카드도 수령했고 내 방이 생겼다..ㅡㅡ;;

사실 예전 광고에 내 방이 생겼다. 그런 카피가 있었는데...그 당시 나도 언제 내 방이 생기겠나...

회사 같으면 임원이 되어야 겠고 학교 같으면 교수가 되지 않고서야 방이 있는 걸 못 봤으니..

근데 뜻하지 않게 엉뚱한 시점에 내 방이 생겼다. 이 동네는 워낙 선진국이라서 인지 교육적 혜택이 너무나 훌륭하다. 시설도 엄청나게 좋다는 말 밖에는 표현 할 수 없다.

여하튼 난 내 방이 생겼다. 창에 커텐도 달려 있고 문을 열고 들어서면 자동으로 불도 켜진다..ㅡㅡ;;

제법 큰 엘시디 화면도 벽에 있고, 버튼을 누르면 아래위로 자동으로 움직이는 책상도 있다. 이건 정말 첨에 봤을때 감탄사가 나왔다. 책상이 움직이다니...ㅡㅡ;; 이런 미개한...

다만 창밖으로 보이는 날씨가 우울할 따름이다. 며칠째 계속 비가 내린다. 날이 갈 수록 날이 저무는 시간이 빨라진다. 3시정도만 되도 벌써 어둡다...어두워~~

스웨덴 도착

무사히 랜딩했다. 친절한 택시 기사와 집주인 아줌마 덕분에 첫날에 길을 헤매지 않고 잘 도착했다.

공항에서 시내까지는 꽤나 거리가 되어서 택시비가 많이 나올까 염려 했는데...

다행히 마일리지로 과금하는 것은 아니었지만 여하튼 비싸긴 했다.

사실 택시비 비싸다는 느낌은 여전하긴 하지만 시장 물가를 보면 약간은 퇴색 되는 느낌이다.

와서 처음 안 사실이지만 여긴 겨울에 해가 안뜬다는 거다. ㅡㅡ;;

간혹 창으로 햇빛이 잠시 비치기는 하지만 정말 잠시 동안이라...함작가 말로는 겨울동안 일주일 정도 해가 뜬다는데... 여하튼 온지 며칠 되었지만 해는 구경해 보지 못했다.

엄청 춥다는 느낌은 아직 아니지만 샤워 후에 느끼는 욕실에서의 추위는 기분이 좋진 않다...ㅡㅡ;;

한 겨울이 오면 라디에이터 성능을 믿고 살수 있을까? 하는 의구심이 들기도 하고...음..

문제는 추위가 아니다. 추우면 옷 껴 입고 담요라도 둘둘 감고 있으면 되는데...먹는게 문제다.

사실 먹는게 문제라기 보다는 돈이 문제일지도 모르겠다.

생활비는 거기서 거기다...라는 나의 고정 관념을 무참히 짓밟은 물가에서 좌절했다.

뉴욕, 동경 물가...이건 그냥 장난 정도이다. 역시 세계 최고 물가를 자랑하는 국가의 자부심을 내세울 만 하다는 생각이다.

며칠 동안 빵이랑 크림 치즈로 연명하다 오늘은 하루종일 병든 닭마냥 침대에서 누워 있길래,

오후에 일어나서 슈퍼에서 훈제 닭 한마리를 사들고 와서 뜯었더니 저녁에 약간 다시 살아난 느낌이랄까?

역시 고기를 먹어야해...ㅡㅡ;; 문제는 마트 한번 가면 몇개 집어 들어도 3~4만원은 기본으로 나오니..

이틀 꼴로 그렇게 쓴다해도 대충 한달에 60만원은 나오니 좀 제대로 먹는다 치면 백만원...ㅡㅡ;;

엘에이서 그 정도 쓰면 정말 배터지게 먹을 텐데...강력한 물가가 생각을 일차원적으로 몰고가고 있다..ㅡㅡ;;

올 유캔 잇

어디 오래 있는 것도 아닌데 쑥스럽게 사람들이 저녁 먹자고 해서 동네 한식당에 갔다.

원래는 가격대가 좀 있어서 손님이 없는 편이라 예약도 안하고 갔는데...ㅎㄱㄷ

왠걸 외국 애들이 장사진을 치고 있는게 아닌가..ㅡㅡ;;

아마도 가게가 손님이 없어 올유캔잇을 싸게 내 놓고선 밀려든 손님 들인것 같았다..

얘네들도 싼거 엄청 좋아하나보다...라는 생각이 들면서도 요즘 미국 경기가 옛날같지 않다는 사실을 다시 느껴 본다.

예약 안한 덕택에 한시간을 넘게 기다렸다가 자리에 앉을수 있었다.

중간에 한인타운으로 가자는 둥..때마침 트래픽이 있는 시간대라...여러 의견에 분분했지만

왔다갔다 시간 따지만 그냥 기다린게 아까워서 오기를 부린 것이다.

사장님이 좀 미안했던지 서비스 고기 좀 내어 오시고...뭐 무한대라 그다지 감흥은 없지만,

그리고 굳이 거기서 먹겠다는 건 가지고 있던 주류 쿠폰 때문이기도 했다. 흠...반값이니 어딘가

간만에 잘 먹었다는 표현이 어울리게 배불리 먹긴했다. 담날 하루종일 화장실 들락 거린거 빼고는..ㅡㅡ;;;

불법 카피본

논문 보다 유난히 책이 레퍼런스 많이 되어 있는 탓에 내용도 어렵고 해서 텍스트를 찾았다.

간혹 수업 할때 교수들이 이제 막 출간한 책들을 웹에다 올려 놓는 경우도 많기에..

하지만 이들 텍스트는 역사도 오래되고 꽤나 바이블이라 인터넷에 pdf로 돌아다니는 것을 구하기가

쉽지 않았다. 구글 북에 잠시 들러서 몇 페이지 읽다가 짜증이 지대로 나서 한번 찾아 보리라 맘 먹고는 뒤지다.

역시나 중국애들은 아직 지적 재산권 개념이 전무 후무한지 얘네들 사이트에는 없는게 없다..ㅡㅡ;;

http://www.ebookee.com.cn/

한군데 듕귁 사이트를 알아내서 링크를 걸어 놓고는 3권중 2권을 찾았다..오호라~~ 부끄럽군..

만약 중국애들이 이짓을 언젠가 그만 둔다면 아마도 나같이 불쌍한 학생들은 더욱 힘들어지리라...ㅡㅡ;;

오늘 전자신문 기사에 듕국 애들이 짝퉁 휴대폰 만들어 신흥 시장에다 엄청 뿌려댄다고 나오던데...

남의 일이니 덜 새삼스럽다 그 덕을 보니 뭐라 할말이 없네...이런..