기록기록 우는 갈매기

미래의 결과를 예측할 수 없는 상황에서 지금 내가 할 수 있는 최선의 결정은 무엇일까? 매 선택마다 그 순간에 가장 좋다고 생각되는 것을 선택하는 것이다. 즉, 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달한다. 매 순간 가장 좋다고 생각되는 것을 선택하면 그것이 궁극적으로도 최적이 될 수도 있기 때문이다. 이러한 원리의 접근방식이 바로 Greedy Approach이다. 하지만 이는 미래를 고려하지 않고 단지 그 순간에서의 optimal한 것을 선택한 것이므로, 그 해답이 궁극적으로 optimal라는 보장이 없다. 따라서 최적의 해답을 주는 알고리즘인지 검증하는 과정이 반드시 필요하다. 따라서 Greedy Approach 알고리즘의 구성은 다음과 같다. ① 선택 절차, selec..

이항계수라하면 고등학교 때 잠깐 나타나고 말 것인줄 알았거늘..... 여기서 또 마주치다니 우리에게 너무나도 익숙한 이 이항계수 nCk 어쩌구 저쩌구가 동적 계획법과 어떤 관련이 있다는건지 알아보자..^^ 이항계수란? 이항계수는 n개의 원소중에서 k개를 순서에 상관없이 뽑았을 때 조합의 가짓수이다. 파스칼의 삼각형을 이용한 이항계수의 성질은 다음과 같다. nCk = n-1Ck-1 + n-1Ck 위 식과 그림을 보면 알 수 있듯, 파스칼 삼각형에서 n-1번째 줄 k-1번째 수와 n-1번째 줄 k번째 수를 합한 값이 n번째 줄 k번째 수의 값이 된다. 즉, 이전 항들의 수의 합이 다음 항의 수가 된다. 이는 전체 문제의 부분들이 서로 상관관계가 있다는 것이고, 따라서 이항계수는 dynamic programm..