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 다음에 하기로..

Dynamic Programming - Knapsack

문제:

S 사이즈 만큼 담을 수 있는 가방이 있고, N개의 물건이 있다. 각 물건은 사이즈 s[i]와 가치 v[i]를 가진다. 가방안에 물건을 담을때 담을 수 있는 최대 가치는 얼마인가?

recurrence 식 추리:
일단 N개의 아이템이 있으니 prefix or suffix기반의 변수가 하나 필요하고(i), v의 최대값을 구하는 것이니 recurrence식의 인자로 v는 제외. 그럼 나머지는 S 밖에 없으니 그것을 두번째 인자로 하면 된다.

K(i, S ) = max{ K(i+1,S) , K(i+1, S-s[i]) + v[i]}

base cases:
K(i, 0) =0 , 0<=i<=N-1
K(N, i) = 0,  0<=i<=S

topological order:
i : N->0 로
S : 0->S or S->0 ; 즉 어느 순서로 해도 상관이 없다.

이 것을 2D 그림으로 표현해 보면 이렇게 된다.

역시 github에 코드를 반영해 놨으니 참고.

Dynamic Programming - Edit Distance

문제는
given two string x y, what's the cheapest possible sequence of char edits to turn x -> y
insert, delete, replace가 가능하고 각 edit의 cost는 정해져 있다.

예를 들어,
HIEROGLYPHOLOGY,  MICHAELANGELO 이 두 단어의 edit distance는 얼마일까?

우선 subproblem을 define해야 한다.
일단 스트링이 나오니까 prefix, suffix, substring중의 하나라고 볼 수 있다.
두개의 스트링이 나오니까 이들 2개의 조합일것이라 추측이 가능하다.

prefix 혹은 suffix기반의 recurrence식을 만들 수 있다.
prefix기반은 이렇게 된다.

유사하게 suffix 기반의 recurrence 식도 만들 수 있다. 이것은 여기서 설명하진 않고 github 소스에 구현되 있으므로 이를 참고하면 되겠다.


reference :
http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/

Dynamic Programming - Parenthesization

A[0] ... A[n-1] 의 N개의 matrix가 있고 A[0]*A[1]* ...A[n-1] 의 값을 구하는 효율적인 순서를 구하는 것이 문제.

Optimal evaluation of associative expression A[0]*A[n-1] e.g. multiplying rectangular matrices

A*B*C = (A*B)*C or A*(B*C)

인데
( m x l )* (l x n ) = (m x n matrix) 가 되고  첫 행렬의 렬(column) 과 두번째 행렬의 행(row)은 같아야 한다.
위의 경우 필요한 #multiplication = m*n*l 이 된다.

즉, (4 x 1)*(1 x 4)*(4 x 1) 을 생각해보면
 {(4 x 1)*(1 x 4)} * {(4 x 1)} = (4 x 4)*(4 x 1) 이지만
 (4 x 1)* {(1 x 4)*(4 x 1)} = (4 x 1)* 상수 가 된다.

이렇듯 순서에 따라서 더 작은 곱셈으로 답을 구할 수 있다.
이 문제는 어떤 순서로 계산을 하면 최대한 빨리 계산을 할 수 있는지를 물어보는 문제다.

앞서 썼던 Dynamic Programming - intro 에서 봤듯이 DP에서 제일 처음 풀어야 것은  subproblem을 정의 하는 것이다.

앞서 얘기한 부분을 잘 생각해보면 결국엔 outermost multiplication이 무엇이냐로 볼 수 있고
P(i,j)를 min cost from i to j
라고 define하면
recurrence는 이렇게 되고,
P(i,j) =  min { P(i,k) + P(k, j) + costOfMultiplication(A[i]~A[k]) by (A[k]~A[j]) } for k in range(i+1, j)

costOfMultiplication = A[i].row * A[j].col * A[k].col
( row 는 앞에 위치하는 행렬에서 결저이 되고 col은 뒤의 행렬에서 결정이 되므로 결국은 시작점의 row와 마지막 행혈의 col이 된다. )

P(i, i) = 0
이고

우리가 원하는 답은 P(0, n)이 된다.
여기서 좀 특이한 것은 topological order를 구하기가 좀 애매하다.

Dynamic Programming - intro

dynamic programming은
- careful brute force
- recursion + re-use
- shortest path in DAG
라고 볼 수 있다.


5 easy steeps to DP :

1. define subproblems
2. guess
1. guessing which subproblem to use to solve bigger problem
2. add more problems to guess/remember more
3. recurrence
4. recurse + memorize (acyclic인지 확인 필요)
   or bottom-up table (topological order를보고 bottom-up일지 top-down일지를 결정)
5. original problem

subproblem for strings/sequences 는 셋중 하나, 요 세개는 많이 쓰는 애들이니까 DP를 풀때 제일 먼저 생각해봐야 할 것들.

- suffix[i:]
- prefix[:i]
- substring[i:j]

이 교수님 강의 넘 맘에 든다. 귀에 쏙쏙. 4편까지 있음. 

씨리즈로 몇가지 문제를 풀어볼 생각이다.
DP 문제는 table 혹은 recursive 방식으로 모두 풀수 있다. recursive방식은 간단한 반면 탐색범위가 커지면 stack overflow로 한계가 있으므로 문제를 보고 탐색 범위를 보고 더 효율적인 방법으로 풀면 된다.

• Parenthesization
• Edit distance
• Knapsack
• Travelling Salesman problem