foon's 작업실

Generic Graph Search 알고리즘은 크게 두 가지로 나눌 수 있습니다.

하나는 LIFO Manner를 이용하는 Depth First Search(DFS), 다음은 FIFO Manner를 이용하는 Best First Search 입니다.

BFS(Best First Search)는 Greedy Algorithm과 연관이 되어 있습니다. 해당 상황에서 가장 그럴싸한 경로를 선택한다는 것이 BFS의 핵심이죠. 이 BFS에 속하는 방법중에 하나가 바로 A* Search입니다. root로부터 현재 노드까지의 거리에, 목표 노드까지 남은 거리를 예측하여 그 값을 더하고 OPEN queue에 삽입합니다. 보통 OPEN queue는 MIN HEAP으로 작성된 Priority queue이기 때문에, 최소 예측 비용을 가진 다음 노드까지의 경로가 queue의 선두에 위치해 있게 됩니다. A* Search는 목적지 노드까지 거리를 예측하는데 어떤 특정한 정보를 사용하기 때문에 Heuristic Search로 분류됩니다.

이 A* search에서 heuristic 값이 항상 0으로 고정된다면 무슨일이 일어날까요? 이를 Uniform Cost Search라고 하는데 보통 queue에 들어간 다음 노드까지의 거리만 가지고 다음 노드를 결정하게 됩니다.

 위의 그림에서 알고리즘은 어떤 경로를 선택하게 될까요? 먼저 루트 노드인 A가 CLOSE list에 삽입되고, 알고리즘은 A의 자식 노드들을 경로 값과 함께 OPEN list에 집어넣게 됩니다. 그 중 최소값을 가진 D가 다음 노드로 선택되고, D의 자식 노드들이 경로값과 합께 OPEN list에 집어 넣어집니다. 그렇게 되면 queue에는 [B:3, C:2, F:4, E:2]의 노드들이 들어있게 됩니다.  이와 같이 동일한 값이 두 개이상 존재할 경우, 알고리즘은 구현자의 구현에 따라 다음 노드를 고르게 됩니다. 가령 C가 먼저 삽입되었기 때문에 C를 선택한다면 queue에는 [B:3, F:5, F:4, E:2]이 들어있게 됩니다. 다음 노드로는 E가 선택되겠죠.
 서로 다른 비용을 가진 노드에 대해서 알고리즘은 최소값을 가진 노드를 선택하게 된다는 것이 이 Uniform Cost Search를 위시한 A* search의 기본 개념입니다. 때문에 Greedy Algorithm과 연관이 되어 있다고 하는 것이기도 합니다.
 A* search에서는 그림에 표기된 경로값 외에도 목표까지의 경로 추정치를 휴리스틱으로 사용하게 됩니다. 경로 추정치가 실제의 거리 값보다 작을 경우 이 A* search는 Admissible하다고 표현합니다.


 만약 Uniform Cost Search에서 다음 노드까지의 경로값까지도 사용하지 않는다면 과연 어떻게 될까요? 이를 Breadth First Search라고 합니다. 많이들 아시는 넓이 우선 탐색이 바로 그것입니다.

킹스 스피치 감독 톰 후퍼 (2010 / 오스트레일리아,영국,미국) 출연 콜린 퍼스,제프리 러시,헬레나 본햄 카터 상세보기

간만에 본 영화. 킹스 스피치.

서프라이즈에서 영국왕 조지 6세에 대한 일화를 보여주는 와중에 간간히 끼워져 있던 영화 내용을 보고 흥미를 느껴 기다리게 되었다.

일단 감상 소감을 말하자면 멋진 드라마라는 것.

때로는 실화가 드라마보다 더 드라마틱할 수 있다는 것을 보여주는 것 같기도 하고.

대략적인 줄거리는 다음과 같다.

버티(콜린 퍼스분)는 영국 왕실의 둘째 왕자로써, 말을 더듬는 버릇을 가지고 있다.

콜린 퍼스(Colin Andrew Firth) 직업 영화배우

상세보기

이러한 버릇때문에 어려서부터 형에게 놀림받으며 모든 면에서 잘난 형에게 묘한 컴플렉스를 가지게 된다. 더욱이 백성들 앞에 나서야 하는 '왕'이 되는 것은 그에게는 꿈도 못꿀일이다. 하지만 그럼에도 불구하고 왕자로서의 위엄을 갖추고 책임을 다하려하는 면모도 가지고 있다.

그런 버티를 내조하는 부인(헬레나 본햄 카터)은 그를 위해 언어치료사를 섭외한다.

헬레나 본햄 카터(Helena Bonham Carter) 직업 영화배우

상세보기

그녀가 그를 위해 고용한 언어치료사는 호주 출신의 라이오넬 로그(제프리 러시분). 매번 연극 오디션에 도전하지만 식민지 출신이라는 탓에 번번히 떨어지는 사람이기도 하다.

제프리 러시(Geoffrey Roy Rush) 직업 영화배우

상세보기

로그는 학위는 없지만, 고향에서 귀환병들을 돌보며 알아낸 그만의 노하우로 버티의 말더듬증을 치료하고, 그의 마음을 서서히 열어간다. 처음에는 참을성 없이 포기하던 버티도 로그에게 마음을 열어가며, 웅변 기술을 익혀나간다.

그러던 중 영국 국왕이 노환으로 죽게되고, 버티의 형이 왕위를 물려받게 된다. 하지만 버티의 형은 그가 사랑하는 심슨 부인과 결혼하기 위해 왕위를 포기하게 되고, 버티는 졸지에 그토록 싫어하던 왕위를 물려받게된다. 왕위를 물려받은 후, 세계 2차대전이 터지게 되고 버티는 전쟁에 맞서 국민들에게 용기와 희망을 줄 연설을 준비하게 된다.

현재 영국여왕 엘리자베스2세의 아버지인 조지 6세, 에드워드 8세와 심슨부인의 세기의 스캔들, 그리고 세계 2차대전이라는 실화를 바탕으로 한 이 영화는, 주인공 버티와 언어치료사 로그간의 이야기로 내용을 이끌어가게 된다. 중간중간 나오는 개그코드는 문화가 다른 우리나라에서도 먹힐만큼 재치가 있으며, 영화의 전반에 깔려있는 신뢰와 우정이라는 클리셰는 분명 진부하긴 하지만 변함없이 잔잔한 감동을 준다.

훌륭한 배우들, 특히 내가 가장 좋아하는 여배우인 헬레나 본햄 카터의 숙녀로써의 연기(참 오랜만이다.)를 비롯하여 콜린 퍼스, 제프리 러시라는 명배우들의 연기는 이 영화를 부담없이 보게 만들고 등장인물의 이야기를 옆에서 듣고 공감하는 것처럼 만들어준다.

보고 후회하지는 않을 영화라고 생각하며, 사람간의 관계에 대해 생각해보고 싶은 사람에게 추천하고 싶은 영화이다.

라이오넬 로그의 실제모습, 상당히 잘생긴 듯 하다. 후에 왕의 친구로써, 영국 기사단의 칭호도 받았다고 한다.

실제 조지 6세의 모습. 상당히 미남이다.

별점 : ★★★☆
한줄평 : 실화를 바탕으로 한 신뢰와 우정에 관한 감동적인 이야기

제대로 해봅시다