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 소스에 내 이름이 떡 하니 들어가게 된 히스토리 되겠다.

Susan Cain, Quiet

살다보면 외향성이 필요할 때가 있고, 그것을 가지고 있는 척 해야 할때가 있다. 내향적인 사람이 외향성인척 하면서 살 필요가 있는가? 외향적인것이 더 좋은것인가? 아니면 그 반대인가?
기질이란 있는것인가? 기질은 바뀌지 않는가 아니면 바꿀 수 있는것인가?

이런 물음들에 대한 새로운 각도의 답을 주는 책이다.

난 쭉 우리 아들이 좀 더 외향적이었으면 하고 바라고 있었는데(내가 그렇지 않아서 인가?)  이 책을 읽고는 그런 걱정을 하지 않기로 했다. 기질을 존중하고 기질에 반하는 행동을 해야 할때 그것을 소화할 만큼의 멘탈만 있으면 되는 것이다.

별 다섯.

38.
이 책에서 가져갈 수 있는 오직 한가지 통찰이 있다면, '자기 자신을 그대로 받아들여도 된다' 라는 느낌이라면 좋겠다.

58
외향성 선호는 사실이다. 이 특성은 아시아와 아프리카에는 덜 나타나고 유럽과 아메리카에는  더 나타나는데, 이들 대륙의 후손들은 상당부분 이주민이었다. 심리학자들은 여행하던 사람들이 집에 머무르던 사람들보다 외향적이라는 점, 그리고 그러한 특성을 후손에게 물려주었다는 점이 이치에 맞는다.

98
사람들의 인식은 문화적인 편견이 반영된 것에 불과할 때가 많다.

99
외향적인 지도자들은 직원들이 수동적일때 집단의 성과를 향상시키는 반면, 내향적인 지도자들은 직원들이 능동적일때 더 효과적이다.

146
과학적 근거를 보면 기업 사람들이 집단으로 브레인 스토밍을 하는것은 정신 나간 짓이다.
단, 온라인 브레인스토밍은 효과가 있다.

162
고반응과 저반응은 각각 내향성과 외향성에 연결된다.
164
고반응 아이들은 외향적이기 때문이 아니라 그 작은 몸이 새로운 물체와 소리와 냄새에 강하게 반응했기 때문에 그렇게 한것이다. 저반응 아이들은 조용했던 이유도 내향적으로 될 아이들이었기 때문이 아니라 실제는 정반대로 신경계가 새로운 것에 별 감흥이 없기 때문이었다.

175
케이건에 따르면 천성 탓이냐 양육 탓이냐는 질문은 눈보라가 기온때문인지 아니면 습도 때문인지 묻는것과 마찬가지다. 둘의 복잡 미묘한 결합이 지금의 우리가 있게 된 원인이다.

178
난초가설
반응성이 높은 아이가 좋은 교육과 보살핌을 받고 안정된 가정환경에서 자라면, 반응성이 낮은 아이에 비해 정서문제가 적고 사교 기술도 뛰어나다는 연구결과가 나왔다. 이들은 공감을 잘하고, 다정하고, 협조적이고 타인과 잘 협동한다. 친절하고 양심적이며, 잔혹함이나 부당함이나 무책임함에 쉽게 흥분한다. 또 자신에게 중요한 일에 성공적이다.

186
우리는 성격을 개조할 수는 있지만, 그것도 어느 정도까지다. 타고난 기질은 우리가 어떻게 살았든 간에 우리에게 영향을 미친다. 우리라는 존재의 상당한 부분은 유전자, 두뇌, 신경계에 따라 정해진다.

196
일단 내향성과 외향성을 자극 수준에 대한 선호도 정도로 이해하고 나면, 자신의 성격에 잘 맞는 환경을 의식적으로 만들어 낼 수 있다. 자극이 과하지 않고 부족하지도 않게, 지루하지도 않고 불안하지도 않게 말이다. sweet spot!

203
신념에서 나오는 용기를 담아 말하는 사람보다 더 용감한 사람은 없다

221
고 반응성인 내향적인 사람은 땀을 더 흘리고, 외향적인 사람은 땀을 적게 흘린다. 이들의 피부는 말그대로 두껍고, 자극에 영향을 덜 받고, 만져보면 시원하다. 바로 여기에서 사회적으로 '쿨하다'는 개념이 생겨났다고 한다

319
Free Traits Theory: 우리는 특정한 성격 특성을 타고나거나 문화적으로 함양되지만,  "개인에게 핵심이 되는 프로젝트"를 위해 거기에서 벗어난 행동을 할 수 있다.

333
자신에게 핵심이 되는 프로젝트를 알아내려면
- 어렸을때 무엇을 좋아했는지 회상해보라. 그때의 구체적인 답변은 표적에서 빗나갔을 수도 있지만, 그 아래 깔려있던 충동은 그렇지 않을 것이다.
- 자신이 끌리는 일에 주의를 기울이자
- 자신이 부러워 하는 일에 주의를 기울이자. 질투는 추한 감정이지만 진실을 알게 해준다.

337
자유특성계약; 일정시간은 자신의 성격에 맞지 않는 행동을 하기로 하되, 나머지 시간에는 자신의 모습 그대로 지낼 수 있게 하는 것이다.

354
내향적인 사람들은 우호적인 상황에서 만난 사람들을 좋아하지만, 외향적인 사람들은 자기와 경쟁하는 사람들을 더 좋아한다
내향적인 환자들은 부드럽고 편안하게 말하는 로봇과 훈련할때 더 나은 반응을 보이고(잘하셨네요. 계속 그렇게 하세요.)
반면 외향적인 환자들은 자극적이고 공격적으로 말하는 로봇과 훈련할때 더 열심히 했다. (고작 그것밖에 못하세요! 더 잘하실 수 있잖아요!)

381
"한번도 만난 적 없는 애랑 노는게 좀 이상 할 수도 있다는 건 아빠도 알지만, 네가 먼저 놀자고 하면 저 애는 좋아서 트럭 놀이를 같이 할걸"
"어제 모르는 아이들한테 말 걸었지? 힘들 수도 있었을텐데, 잘 했네"

382
아이에게 수줍음이 많다는 말을 해서는 안된다. 아이는 부모의 말을 믿을 테고, 그러면 자신의 감정이 통제할 수 있는 것이라기보다는 이미 고정된 특성이라고 믿어버리고 만다.아이는 수줍음이 부정적 의미로 쓰인다는 점도 아주 잘 알고 있다. 무엇보다 수줍음을 탄다는 이유로 아이를 부끄럽게 만드어선 안된다.

388
사실 수많은 학교가 외향적인 아이들에게 맞게 구성되어 있다.
학교의 목적은 아이가 평생을 살아가도록 준비시키는 것이어야 하지만, 실제로 아이들이 준비해야 할것은 학교에서 하루하루 살아남는 방법일 때가 많다