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

change is inevitable

이제 막 eclipse contributor 가 되기도 했고, 이제 막 재미가 붙고, 더 큰 건으로 contribution할 수 있는 건 수를 찾던 중 이기도 했는데 아쉽게도 회사에서의 직무에 변경이 생겼다. 자세한 스펙은 아직 미지수 이지만 context, server , analysis, big data 의 키워드가 주 일것으로 생각된다.

그래서 그동안 1년여동안의 eclipse생활을 뒤돌아 봤는데, 기간에 비해 이룬것이 적다는 생각이 들었다. 그래서 아쉽지만 그래도 이 기간동안에 의식적으로 노력한 것에 대한 결과는 얻은것 같아 안도감이 든다.

그 노력이란...

내가 하고싶어하는 일을 나의 할일로 만들지 않으면 누군가가 내가 하기 싫은 일을 나의 일로 만들어 버린다는 것.

이 고리를 잘 엮으면 난 나의 커리어와 재미를 동시에 만족시킬 수 있게 된다. 전략적으로 접근해야 해서 쉽지는 않지만 또 잘 연결을 시키다 보면 불가능한 것도 아니더라.

나의 삶을 내가 컨트롤 할 수 있는 영역을 넓혀 간다는 것. 멋진 일이다.

아듀 이클립스.

그리고 난 다시 새로운 분야로 뛰어든다.

Eclispe platform contributor 되다.

Eclipse에 처음으로 내 소스를 반영하여 contributor가 되었다.

내가 반영한 것은 emacs key scheme에 있는 recenter command를 enhancement한 것인데.
기존에는 cursor line이 center 로만 옯겨졌는데 이것을 오리지널 이맥스처럼 center top bottom 으로 스크롤링되게 만드는 패치를 만들어서 반영하였다.

패치를 보면 알겠지만 매우 간단한 작업이었고, 더 어려운것은 그 프로세스 적인 부분이었다.
사실 어떻게 어떻게 해서 contributor 가 될 수 있다는 정보가 별로 없고 막막한 부분이 있었는데 이번에 그런 부분을 공유해보면 혹시나 비슷한 고민을 하고 있는 분들께 도움이 되지 않을까 하여 공유해보고자 한다.

1. 우선 내가 해결하고자 하는 이슈가 이미 진행중인지 버그질라를 통해서 검색
2. 해당하는 이슈가 있다면 그 이슈를 이용하면 되고, 없다면 새 이슈를 등록한다. 나의 경우 이슈는 https://bugs.eclipse.org/bugs/show_bug.cgi?id=412267 이었다.
3. 이슈 등록후, 패치를 attach함.
4. 이렇게 패치를 등록하면 각 모듈의 maintainer가 이슈를 재할당하고 첨부된 패치에 대한 feedback을 해준다. 나의 경우는 아래 사항들을 얘기했었다
1.  command의 설명을 업데이트 하고, 소스의 copyright, credential 업데이트
2. CLA(Contributor license agreement) 서명
3. coding convention, compact assignment, operator 사이는 공백 하나씩 주기
4. 버그 리포팅 및 재현할 수 있는 테스트 케이스 기술
5. 이렇게 몇번의 피드백이 오고간 후 최종 패치를 올렸더니
   한 달여만에 master git 에 반영이 되었다.
   http://git.eclipse.org/c/platform/eclipse.platform.text.git/commit/?id=1726a32434ee8a113d5ab8c3441987c7aa6fdf25

eclipse는 git을 사용하고 있어서 git의 기본적인 사용법을 알아야 더 편할것 같고, 이 외에 정보들은 eclipse wiki등을 찾아 보면 되겠다.

이렇게 eclipse platform 소스에 내 이름이 떡 하니 들어가게 된 히스토리 되겠다.