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/

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

binary search

binary search
각 배열이 ascending으로 sort되어 있을때, 특정한 값을 찾을때 사용하는 search방법. N까지 loop를 돌면서 모든 방법을 찾는 것O(N)에 비해서 아주 효과적인O(logn) search 알고리즘이다.
이게 얼마나 효과적이냐 하면 백만개중에서 찾아야 한다고 치면 25번 만에 원하는 값을 찾을 수 있다는 얘기다. N이 커지면 커질수록 엄청난 파워를 보여준다.

classic한 binarySearch알고리즘은 아래와 같다.
java에서는 Arrays.binarySearch 로도 제공된다.

 
int binarySearch(int key, int[] a){
 int lo = 0;
 int hi = a.length - 1;
 while (lo<=hi) {
  int mid = lo + (hi-lo)/2;
  if (a[mid] > key ) {
   hi = mid-1;
  }else if (a[mid] < key) {
   lo = mid + 1;
  }else{
   return mid;
  }
 }  
 return -1;
}

binary search에 기반한 몇가지 응용이 있다.

예를 들면,
어떤 조건(100보다 큰)을 만족하는 최소값 - 1번
어떤 조건(100보다 작은) 을 만족하는 최대값 - 2번


1번은 nnnnnnnyyyyyyy중에서 가장 작은 y를 찾는 것
2번은 yyyyyyyynnnnnnn(y는 조건 만족, n는 불만족)중에서 가장큰 y를 찾는 것

1번에서 조심해야 할것은 범위가 ny 로 좁혀졌을 경우, while 루프를 빠져나갈 수 없다는 것. 이유는 mid를 계산할때 소수점은 버리기 때문에 계속 lo(즉, n)에만 머물러 있다는 것. 따라서 이때 반올림을 위해서 +1을 해줘서 workaround 할 수 있다.

public static int binarySearchBiggestSatisfyingCondition(int lo, int hi, IValidator validator){  
 while (lo<hi) {
  // special
  int mid;
  if (hi-lo ==1) {
   mid = lo + (hi-lo+1)/2; // notice +1 added, round up. this is because
  }else{
   mid = lo + (hi-lo)/2; 
  }
   
  if (validator.validate(mid)){
   lo = mid;
  }else {
   hi = mid-1;
  }
 }
  
 if (validator.validate(lo)) {
  return lo ;
 }  
 return -1;  
}

같은 방식으로 2번은 이렇게 하면 된다. 단, 이때 1번처럼 while루프를 바져나오지 못하는 현상은 없다.

public static int binarySearchSmallestSatisfyingCondition(int lo, int hi, IValidator validator){
  while (lo<hi) {
   int mid = lo + (hi-lo)/2; // notice +1 added, round up. this is because 
   if ( validator.validate(mid) ) { // predicate function is true
    hi = mid;
   }else {
    lo = mid+1;
   }
  }
  
  if (validator.validate(lo)) {
   return lo ;
  }  
  return -1; 
  
 }

reference:

• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

kmp algorithm

string match알고리즘 인데 key는 한번 비교한 문자에 대해서 다시 비교하지 않는다이다.


ABCDABD에서  ABD를 검색한다고 하자.

0123456
ABCDABD : S[i]
ABD     : P[j]

- 2에서 처음 mismatch가 발생하는데, 이때 i는 3으로 바로 건너띌 수 있다. 왜냐하면 B로 시작하거나 C로 시작하면서 ABD와 match가 될수는 없기 때문에, 

반대로 
0123456789
ABADABABAC : S[i]
ABABAC     : P[j]
  ABABAC

이 경우는 3에서 mismatch가 발생하면, j를 1로 reset해서 다시 검색한다. ABAB에는 실패했지만 ABXX에서 성공할 수 있으므로.

앞에서 알아본 것을 구현하려면 failiure function을 미리 계산해서 가지고 있으면 된다.
N이 클 수록 시간에서 엄청난 이득을 볼 수 있다.

Reference:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Description_of_and_pseudocode_for_the_search_algorithm
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching

shortest unique pattern( 최소 길이 문자열)

문자열들의 집합이 주어졌을 때, 한 문자열의 핵심 부분 문자열은 이 문자열의 부분 문자열이면서 다른 문자열들에 포함되지 않는 문자열 중 가장 짧은 것을 의미한다.

예를 들어, {zebra, bras, ebbs} 가 주어졌을때 각 명령어의 핵심 부분 문자열은 다음과 같다.
zebra : z
bras : as
ebbs : bs(bb도 가능)

[input]
파일의 첫 줄에는 테스트케이스의 수 C가 주어져 있다. 1<=C<=10
각 테스트 케이스의 첫 줄에 명령의 집합이 포함하고 있는 문자열의 개수 N이 주어진다. 2<=N<=1000
다음 N줄에는 영어 소문자로 된 문자열들이 한 줄에 하나씩 주어지며, 각 문자열의 길이 최대는 100이다. 또한 어떤 명령어도 다른 명령어의 부분 문자열이 아니다.

[output]
각 테스트 케이스 마다 첫 줄에 "Case# X"를 출력한다. X는 케이스의 번호.
각 케이스에 대해서 N줄에 각각 해당하는 명령어의 핵심 부분 문자열의 길이를 출력한다.

[example]
2
3
zebra
bras
ebbs
3
foobar
bard
for

Case# 1
1
2
2
Case# 2
2
1
2

풀이
각 문자열의 substring에 대해서 Tree를 만든다. 각 Node는 char를 가지고 hitCount를 가지게 한다. 그래야 hitCount로 unique한지 판단이 가능하니까

ebbs를 예를 들면
ebbs의 substring은 아래와 같고
ebbs
bbs
bs
s
이를 바탕으로 Tree를 만들면
e
  b
    b
      s
b
  s
  b
    s
s
가 된다.

이렇게 모든 문자열의 substring에 대해서 Tree를 만들고
hitCount가 1인 node를 검색하면 unique한 substring을 검색 할 수 있다.

실제 구현은 여기에서.. (여기에 버그가 있는것 같은데 못찼겠음.--;; )
https://github.com/nberserk/codejam/blob/master/src/stop/july13/ShortestUniquePattern.java