Jacob's Coding Playground

앞서 BFS(Breadth First Search)에 대해서 알아봤었는데요, BFS의 알고리즘상 가까운 노드부터 검색을 하기 때문에 이론적으로 unweighted(edge들이 모두 동일한 weight를 가지고 있을 경우) graph에서는 BFS를 이용하면 Shortest Path를 찾을 수 있습니다.

그럼 앞서 우리가 예제로 사용했던 간단한 네트워크를 가지고 다뤄보겠습니다.

아마 네트워크 분석을 하면서 가장 많이 등장하는 스킬(?)이 바로 Depth First Search(DFS)와 Breadth First Search(BFS)일 것입니다. 이들이 가장 기본적으로 graph를 traversing하는 두 가지 방법이기 때문입니다. 가장 자주 등장하면서도 제일 헷갈리고 어려운 개념이기 때문에 잘 습득해 놓아 사용하도록 합시다 :)

Python에서 network analysis를 하기 위해서는 graph를 정의해야 하는데요, 우리가 직접 구현해서 쓸 수도 있겠지만, 아주 powerful하고 편리한 기능을 가진 라이브러리가 있기 때문에 그것을 기반으로 사용하고자 합니다. 바로 networkx라는 라이브러리인데요, numpy, scipy, pandas와 동일하게 아주 요긴하게 사용되는 라이브러리입니다. 그래도 핵심적인 알고리즘이나 컨셉은 가져갈 수 있으니 잘 사용해 봅시다 :)

일단 예제로 사용할 graph로써 networkx에서 제공하는 작은 그래프 하나를 사용하겠습니다.

만약 우리가 가진 데이터가 너무 많은 predictor들을 가지고 있으면 어떻게 할까요? 이런 경우 overfitting에 시달릴 가능성도 커지고, 분석 또한 어려워지겠죠. 그렇기 때문에 다양한 selection method가 등장하게 되었습니다. 그 중 오늘은 가장 직관적인 Best Subset Selection방법에 대해 알아보겠습니다.

[문제출처 : Codechef] 한 초콜릿 가게에 방문하는 손님들은 특이한 특징이 있습니다. 바로 초콜릿을 사면서 필요없는 화폐를 내지 않는다는 점입니다. 즉, 바꿔말해, n개의 초콜릿을 산다고 했을 때, 손님이 낸 화폐들 중 어느 하나라도 제거했을 때 n개의 초콜릿을 살 수 없다는 이야기입니다.

점원은 손님들이 x원짜리 초콜릿을 몇개 사고싶어하는지 결정해야합니다. 만약 손님이 불가능한 조합으로 화폐를 줬다면 -1을, 가능한 조합이면 몇 개의 초콜릿을 원하는지 구하세요.

이번에는 제 포스팅 처음으로 코딩이 없는 포스트를 올리려고 합니다. 그만큼 제게는 충격이었고, 수학자들의 위대함을 새삼 느끼게 되네요! 하버드와 MIT를 방문하니 마구 학구열이 불타네요 :) 어찌됐건 한 예화를 들려드리겠습니다. (참고 : Math Is Fun)

옛날에 Königsberg라는 도시에 Immanuel Kant라는 사람이 살고 있었습니다. 그는 정말 시계처럼 정해진 규칙대로 살아가는 규칙남이었죠. 그러던 어느날 그는 하나의 사실에 충격을 받습니다. "어떻게 내가 집에서 출발해서 각 동네를 찍는데 중복되게 건너지 않은 다리가 없지!?" 결국 그는 이 문제를 그의 친구였던 Leonhard Euler(오일러)에게 부탁하게 됩니다. 오일러는 결코 불가능하다는 것을 증명했고, 수학의 또 하나의 새로운 지평을 여는 역사적인 순간이었죠.

결국 문제는 이것입니다. 도시의 각 부분을 모두 찍으려고 할 때, 다리를 한번씩만 거쳐서 할 수 있을까요?