htmlcleaner contribution

htmlcleaner 사용하다가 버그? 가 발견되어 현상과 패치 포인트를 적어주니 패치를 해주었다.

한 일주일정도 걸린것 같다.

오픈 소스 컨트리뷰션 어렵지 않아요.

http://sourceforge.net/p/htmlcleaner/bugs/116/

공식적으로 두번째 컨트리뷰션.

Travelling salesman problem - TSP

TSP :
N개 도시가 있고, 세일즈맨은 1번 도시에서 부터 시작해서 모든 도시를 한번씩만 거쳐서 다시 1번 도시로 돌아와야 한다. 각 도시를 이동할때의 비용이 있고-d(i,j)- 이때 최소 비용을 구하는 문제다.

naive :
기본적으로 N개의 도시를 차례대로 나열하는 Permutation 문제라고 볼 수 있다. 따라서 이때의 time complexity는 O(n!) 가 된다. N이 10정도만 되어도 문제 풀기 쉽지 않은 수준이다. (10! = 3628800)

DP :
C(i, S) : 1에서 시작해서 집합S에 있는 모든 도시를 한번씩만 거치고 i 도시로 들어오는 최소 비용
이라고 정의하면,
그러면 우리가 구하고자 하는 값은
C(1, S-{1}) 이 된다.

그 다음은 이렇게 된다.

C(i, {2..N}) =  min << C( j, {2..N} - {j}) + d(j, i) >> where 2<=j<=N, i!=j,  

C(1, {2..N})  이 우리가 원하는 최종답이 된다.

C(i, {}) = d(1,i) 단, i!=1
C(i, {2}) = C(2, {}) + d(2,i)
C(i, {3}) = C(3, {}) + d(3,i)
...
C(i, {2,3}) = min << C(2, {3}) + d(2,i)  or C(3, {2}) + d(3,i) >>
...
이런식으로 C(1, {2..N}) 을 구하게 된다.

그림으로..

집합S를 캐쉬로 표현할때는 bit 로 포함되고 안되고를 표현하면 되는데,
예를 들면, N=4 일때 {2,3,4} 를 표현하면 2^4-2 가 된다. 즉. 1110 (0은 1이 포함되지 않았다는 의미이다)

나중에 어떤 순서로 도시를 방문하는지 알고 싶으면 parent[S] 를 저장하고 있으면 된다.

나의 구현은 여기에

reference ::
https://github.com/evandrix/SPOJ/blob/master/DP_Main112/Solving-Traveling-Salesman-Problem-by-Dynamic-Programming-Approach-in-Java.pdf
https://www.youtube.com/watch?v=aQB_Y9D5pdw

Closest pair of points

Closest pair of points :
2차원에 N개의 점이 있다고 있고, 이때 가장 가까운 거리의 두 점을 찾는 문제다.


먼저 가장 쉬운 방법은 모든 경우의 수에 대해서 계산을 해보는 것. 아래 처럼 되겠지.

findMinBruteforce(i, j):
min=MAX_FLOAT
for a in range(i,j):
  for b in range(i+1, j):
    cur_dist = dist(N(a), N(b))
    if (cur < min): min=cur 

이것을 더 효율적으로 할 방법은 없을까?
우선 N개의 점을 x 좌표를 기준으로 sort를 한다. 그리고 그 중간으로(N/2) 으로 왼쪽 영역과 오른쪽 영역으로 나눈다.

 왼쪽 영역의 최소거리를 dl , 오른쪽의 그것을 dr 이라고 하면 d = min(dl, dr) 이 된다. 그러면 각 영역안에서의 점들끼리는 계산이 되었지만 각 영역을 넘나드는(cross)하는 점들은 계산이 되지 않았다. 그런데 d보다 큰 것은 최소가 될 수 없으니 중간에서 d 만큼 왼쪽에 있는 영역 부터 d만큼 오른쪽에있는 영역 까지의 점들이 고려가 되어야 한다. 이 점들을 따로 뽑아서 y 좌표를 기준으로 sort해서 최소 거리를 구하면 전체 영역의 최소거리 d를 구할 수 있다.

여기서 insight는 bruteforce의 경우 모든 점들에 대해서 계산했지만, divide후에는 left/right/cross 되는 점들만 따로 생각하면 되니까그 계산횟수가 많이 줄어든다. 이것을 recursive하게 한 영역에 2~3개의 점이 있을때까지 반복하면 된다. 물론 2-3개 있을때는 bruteforce로 구현하면 되는 것이고.

나의 구현은 여기에 있다.


References:
http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
http://www.geeksforgeeks.org/closest-pair-of-points/

간단 하게드는 것

제품이나 서비스에 있어서(뭐 안그런것이 있겠냐마는) 사용자를 위해 무언가를 간단하게 만들려고 하면 뒤에서 해야할 일이 많다. 이런것을 보통 usability 라고 부른다. 이것을 측정하지 않고 중요하지 않게 생각하는 회사에서는 흔히나타날 수 있는 부작용은 UX등을 아주 복잡?하게 만드는 것이다. 이런 일은 예상외로 자주 일어 나는데 그 안의 사연들을 보면 지극히 상식적일 수 밖에 없다.

예를 들어 보자. H사는 핸드폰 제조 업체. 이번달 말에 새 모델 출시를 준비하고 있다. 자체 앱스토어인 H App Store도 만들고 H Music도 만들어서 번들링을 한다. 나는 H App Store의 개발자라고 하자. 일정은 이미 빠듯한 상황이고 여유는 별로 없고 윗 사람들은 일정만 강조한다.  H App Store 의 경우는 서버에 사용자 기록을 남겨야 하니까 약관 동의를 받고 device id 를 key로 서버에 저장하게 된다. 이렇게 App Store는 개발을 끝냈다. H Music쪽에서도 보니까 App Store와 비슷하게

 서버에 사용자 기록을 남기고 약관동의도 받아야 하고 device id도 받아서 key를 사용하게 했다. 이렇게 제품을 출시.

고객의 피드백 중에그러고 보니 모두 H사의 서비스를 사용하는데 약관동의를 두번이나 받아야 하며, 내가 단말을 바꾸게 되면(device id가 바뀐다)  이전 기록들이 다 지워져서 다시 입력을 해야 하는가란 voc 가 많이 들어와서 다음 버전에 이것을 간단히 할 수 있는 기능을 넣기로 한다.

이름하여 H Account!

 H Account를 H App store에서 한번 만들어서 로그인을 해두면 그것을 H Music 도 H Books도 재사용할 수 있어서 사용자는 처음 한번만 로그인을 하면 되는 것이다.

 이렇듯 사용자의 클릭 몇번을 save하는 데에는 H Account라는 개발조직을 필요로 한다. H 사가 어느 정도 규모가 있는 회사라면 적어도 몇십명의 개발자가 필요한 것이고 회사로서는 몇십억의 투자가 필요한 것이다.

 어떻게 보면 복잡하게 만드는 것이 가장 쉬운 것이다. 어떻게 해서 사용자에게 더 간단하게 이 서비스를 제공할 수 있을가 라는 고민은 돈과 시간이 많이 드는 일이다.
이 방면의 선수는 애플!

MST - Prim Algorithm

minimum spanning tree(MST)는 undirected graph - G(V, E) - 에서 모든  점을 연결하는 그래프 중에서 weight의 합이 최소인 서브 그래프를 말한다.

MST를 구하는 대표적 알고리즘은 Kruskal 과 Prim 알고리즘이 있다.

먼저 Prim algorithm은 graph를 2개의 set 으로 나누고 두 셋을 연결하는 에지는 최소여야 MST를 만들 수 있다는 아이디어로 부터 만들어진 것이다.

설명은 여기가 너무나 잘 되어 있고..
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

나의 구현은 여기
https://github.com/nberserk/codejam/blob/master/java/src/codejam/lib/PrimMST.java


Kruskal 다음에 하기로..