Greedy Algorithm by object

요즘에도 면접에서 이런 질문을 하는지 모르겠지만, 나는 "10년 뒤의 당신의 모습을 상상해보시오" 와 같은 질문을 굉장히 싫어한다. 왜냐면 지금까지 살면서 그런 생각을 한 적이 없기 때문이다. 난 살면서 계획을 세운 적이 거의 없다. 그래서 연말이 되더라도 별 다르게 정리할 것도, 새해가 밝아도 세울 계획이 없다. 그건 우리 인생을 전혀 예측할 수 없기 때문에 그런 계획이 무의미하다고 믿기 때문이다.

그럼에도 불구하고 어떻게 해야 우리는 최적의 삶을 추구할 수 있을까?

바로 그 해답은 Greedy Algorithm, 욕심쟁이 알고리즘에서 찾을 수 있다.

예를 들어 낙성대역에서 의정부역까지 가장 짧은 지하철 코스를 찾는 문제를 생각해보자. 이 문제는 다익스트라 교수님이 제안하신 방법으로 매우 훌륭하게 풀 수 있다. 문제 해법의 핵심은 지금 이 순간 최고로 보이는 길을 찾는 것이다. 그리고 그 과정을 반복한다. 그러면 이것은 전체적으로도 최적의 길을 구해준다.

낙성대역에서 거리가 가장 짧은 다음 역을 고른다. 그리고 다음 역으로 가서 다시 가장 짧은 거리의 역을 찾는다. 이 과정을 반복하면 의정부역까지 가는 최단 거리를 찾을 수 있다.

즉, locally optimum을 고르다보면 결국엔 global optimum을 이끌어내는 것이다 (CLRS).

A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.

욕심쟁이 알고리즘은 언제나 그 순간 최고로 보이는 것을 고른다. 즉, 전체적으로 최적의 해를 기대하면서 가까이 있는 최적의 선택을 하는 것이다.

그렇다. 우리 인생도 5년, 10년, 20년 생각할 필요없이 지금 이 순간의 locally optimum 을 찾으면 그 길은 결국 global optimum 으로 갈 것이다. 고로 헛된 꿈 꾸지말고 당장 닥친 일이나 열심히 하자. 그래서 난 미래 계획 같은 것 안 세운다. 세우는 것은 무의미.

 IMGP0245(3993)

@@ 종종 유학을 무슨 목적으로 나왔냐는 질문을 받게 된다. 솔직히 말해 난 아무 생각 없이 그냥 공부 잘 하는 친구들이 유학가니 따라나왔다. 진짜다. 갔다와서 교수가 되겠다와 같은 생각을 한 적이 없다. 그런 계획을 세워봤자 내 경험상 무의미하다는 것을 깨달았기 때문이다. 나는 그저 지금 이 순간 주어진 과제를 열심히 하면 된다. 그러면 그 만큼 미래에 나갈 수 있는 가능성이 하나 더 열리게 된다.

일러두기: Greedy Algorithm으로 못 푸는 문제도 많다는 것.


핑백

  • 미친병아리가 삐약삐약 : 2007년 12월 31일.. 2007-12-31 00:06:10 #

    ... . 합리적이며, 이성적으로 본다면 해결 안되는게 현실인데, 이런게 부조리 현실과 타협하는 것일까? 난 아니라고 생각한다.. 현실을 극복하는 길이라 생각한다.. Greedy Algorithm 읽고보니, 이것도 괜찮은 방법인 것 같다.. 하루 하루 오늘에 최선을.. 대한민국 IT프로젝트 교훈 보고서 맞다.. 환경이 좋게, 급히 개선되지는 않을 것 ... more

  • 시내편: 시간을 내 편으로 만들기 | 4four.us 2009-11-09 22:59:19 #

    ... 늘리자는 겁니다. 스티븐 코비의 소중한 것을 먼저 하라 (First Things First) 책의 주제와도 비슷한 얘기 같고, 또 검색해보니 이미 greedy algorithm을 이런 식으로 설명하신 분이 있네요. 그냥 재미로 읽으주시면 감사하겠습니다 :) This entry was posted on Monday, November 9 ... more

  • 시간을 내 편으로 만들기 | 4four.us 2009-11-10 01:42:22 #

    ... 늘리자는 겁니다. 스티븐 코비의 소중한 것을 먼저 하라 (First Things First) 책의 주제와도 비슷한 얘기 같고, 또 검색해보니 이미 greedy algorithm을 이런 식으로 설명하신 분이 있네요. 그냥 재미로 읽으주시면 감사하겠습니다 :) This entry was posted on Tuesday, November ... more

덧글

  • 코카스 2007/12/27 17:36 # 삭제 답글

    아.. 이거 설마 미괄식 구성인가요? :)
  • 빛의탑 2007/12/27 17:42 # 답글

    하지만 greedy method는 optimal solution을 보장하지 못하는 단점이 있죠..
  • object 2007/12/27 17:43 # 답글

    그렇죠... 보장하지 않습니다. 그냥 그런 '희망'을 가질 뿐이죠 ㅎㅎ
  • tan 2007/12/27 17:58 # 삭제 답글

    지금 주어진 과제를 열심히 해야하는건 불변의 진리인데, 5년후 10년후도 어느정도 어떻게 될지는 내다보고 어떤 일을 벌일지 결정해야하며, 최대한 미래에 많은 길을 낼 수 있는 방향을 선택해야 한다.
  • louis 2007/12/27 19:37 # 답글

    브라보! ㅋ
  • object 2007/12/27 19:38 # 답글

    그래서 제가 '일러두기'를 둔 것이죠. 언제나 예외는 있는 법. 그냥 이건 내 스타일. 10년 뒤, 뭐가 어떻게 될지 아무도 모름. 그걸 내다보고 일을 벌리나 내다보지 않고 벌리나... 별 차이 없다고 봄.
  • hwkim 2007/12/27 20:05 # 답글

    ㅎㅎㅎ 공감 200% 입니다. 특별한 계획 없는 삶에 무료해질 듯 싶으면 이따금씩 simulated annealing 같은 것을 해서 어디론가 튀어주는 것도 optimal solution에 근접하는데 도움이 되죠. 그런 의미에서 저는 유학을 결심하게 되었네요 ^^;;
  • 하냐앙 2007/12/27 21:37 # 답글

    저랑 비슷한 걸지도 모르겠네요.
    저도 순간에 충실하면 영원이 답을 준다라는 자세로 살아요 -0-
  • NoSyu 2007/12/27 21:51 # 답글

    Greedy Algorithm은 잘 모르지만,
    예를 보니 출발역과 최종역이 있기에 Greedy Algorithm을 쓸 수 있는 것이 아닌가 하는 생각이....
    만약 최종역이 없다면
    서울 2호선 역 하나마나 내려서 다시 타는 것과 같은 일도 발생하지 않을까 하는 생각도 들었습니다.^^;;;
  • eslife 2007/12/28 07:52 # 삭제 답글

    저도,, 단기적인 목표조차 잘 세우지 못하는 편이라..
    인생에 장기적인 목표를 가지고 행동하는 사람이 나중에 결과도 좋다고 하더군요.
    분명한 목표를 세워서 상상해 보는것도.. 그리고 그걸 이뤄 보는것도 나름 다른 인생을 살 게 할지도 모르니 다른 알고리듬에도 약간의 관심을 주세요 ^^;;
  • object 2007/12/28 08:55 # 답글

    저에게 장기목표가 있다면 잘먹고 잘살기 정도 밖에는 없군요 ㅎㅎ 장기목표가 그다지 불필요하다고 생각되는 것은 전혀 생뚱맞은 목표가 아닌 이상 결국 그 장기목표를 실현하기 위해 해야할 일은 당장 주어진 과제를 열심히 하는 것말고는 딱히 없기 때문입니다. 제가 지금 우주비행사가 되겠다! 라는 꿈을 키우면 지금부터 전혀 다르게 움직여야겠지만, 좋은 회사에 들어가서 높은 자리까지 올라가겠다(?) 또는 훌륭한 교수가 되겠다(!)와 같은 꿈을 이루려면 결국 지금 제가 해야하는 일을 열심히 해야할 수 밖에 없죠. 물론 그런 먼 미래의 꿈을 가지면 그것이 하나의 동인이 될 수 있지만.. 저는 언제나 헛된 꿈은 꾸지 않는 것이 훨씬 낫다라는 생각을 가지고 있어서 장기 계획을 세운 적이 없네요. 10년 뒤에 회사를 차려 유능한 CEO가 되겠다.. 이런 꿈이 과연 얼마나 효과적인지 저는 상당히 회의적입니다. 전혀 먼 미래를 생각하지 않는다는 것은 약간 과장 섞인 말이고 헛된꿈보다 현실적인 꿈을 갖고 지금 주어진 일이나 열심히 하자는 것이 제 생각입니다.
  • 오스카 2007/12/28 10:08 # 답글

    31% 인간형(책 제목)이시군요. ^^
  • 수아기 2007/12/28 10:48 # 삭제 답글

    최적인생경로 알고리즘이라.. 누구나 그걸 풀 수 없겠지만 어쩌면 object님이 말한대로 Greedy가 근접해일지도 모르겠습니다. 현재에 충실하자. 그리고 최선을 다하자. 저의 인생관이기도 합니다만 가끔 최적을 찾지 못할때도 많은것 같아요. 저 책은 개인적으로 좋아하는 책인데 옆에있는 커피와 잘 어울리는걸요.^^
  • object 2007/12/28 11:24 # 답글

    헉.. 그런 책이 있었네요.

    창의력 계발 전문가이자 기업 컨설턴트인 스티븐 샤피로는 ‘31% 인간형’에서 목표에 얽매이지 않고도 성공적으로 살고 있는 사람들의 이야기를 공개한다. 미국인 1,012명을 대상으로 한 설문조사 결과에 따르면 새해 다짐을 지키는 사람은 8%에 불과하고 나머지 92%의 사람들은 실패해서 스트레스를 받고 있다고 한다. 또 33%의 사람들은 목표 때문에 애를 태우고 있으면 13%는 목표를 달성해야 한다는 강박관념 때문에 한 번쯤은 법을 어기거나 비윤리적인 행위를 한 적이 있다고 밝혔다. 그러면서도 41%는 목표를 달성하고 나서도 환멸감만 남았다고 한다.
  • window31 2007/12/28 17:07 # 삭제 답글

    추억의 최단거리 알고리즘으로 좋은 내용을 써주셨네요 ^^
    저도 10년뒤의 계획을 세운다는 거창한 생각이 전혀 없기 때문에 상당부분 공감하고 갑니다.
    1년앞 혹은 한달앞 계획부터가 먼저죠 ^^;;
  • guest 2008/01/05 01:43 # 삭제 답글

    dijkstra의 최단거리 알고리즘은 그리디 알고리즘이 아닙니다.
    그리디 알고리즘과 인생을 비유한 것은 동의할 수 있습니다만...
  • object 2008/01/05 03:22 # 답글

    Dijkstra 최단거리 알고리즘 중 핵심 부분이 Prim's 알고리즘과 똑같죠. 그래서 그리디로 비유한 것입니다. 제가 위에 설명한 다음 역 찾는 것은 그리디와 동일합니다만.. 그리디 알고리즘이라고 할 수는 없지만 또 아니다라고 할 수도 없습니다.
댓글 입력 영역