Program Programming Programmer

이항 계수(Binomial coefficient)는 n 개 에서 k 개를 고르는 (순서 없는)조합의 가짓수입니다. 이는 nCk 로 보통 표현하며 이항 다항식 {\displaystyle x+y} 의 거듭제곱 {\displaystyle (x+y)^{n}}에 대해서, 전개한 각 항 {\displaystyle x^{k}y^{n-k}}의 계수이기도 합니다. 그리고 위와 같이 점화식으로 표현할 수 있습니다. 따라서 이항 계수는 아래와 같은 방법으로 구할 수 있습니다. 12345678910111213141516const int MAX = 1000; //memset(cache, -1, sizeof(cache))int cache[MAX][MAX]; int getBinomialCoefficient(int n, int k)..

선형적인 배열에서 특정 값을 찾는 방법으로 Sequential search 와 Binary search 방법이 있습니다.Sequential search 은 말 그대로 배열의 앞에서부터 끝까지 차례대로 찾아가는 방법이고Binary search 는 오름차순으로 정렬된 배열에서 divide and conquer algorithm 을 사용하여 찾을 대상을 절반씩 줄여가는 방법으로 시간 복잡도를 줄이는 방법입니다.Binary search 는 최악의 경우에서도 을 보장하기 때문에 크기가 큰 배열에서는 일반적으로 Sequential search 보다 빠르게 값을 찾을 수 있습니다. https://en.wikipedia.org/wiki/Linear_searchhttps://en.wikipedia.org/wiki/Bin..