합니다, 개발공부📝 합니다, 개발공부📝

알고리즘 문제 해결 전략 책의 k번째 최대 증가 부분 수열. (동적계획법_테크닉) 기존에 풀었던 LIS문제와 달리 k번째 최대 길이 수열을 출력하는 문제였다. #include #include #include #include #include #include using namespace std; const int MAX = 2000000000 + 1;//k번째보다 1개 더 큰수 int n; int cacheLen[501], cacheCnt[501], S[500]; int lis(int start) {//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환 int& ret = cacheLen[start + 1];//메모이제이션 if (ret != -1) return ret; ret = 1; //항..

알고리즘 문제 해결 전략 책의 동적계획법_테크닉의 예제문제 동적계획법을 사용하는 방법 중에서도 k-1번째까지의 경우부터 1번째 경우를 구하는 방법을 택하도록 한다. #include #include #include #include #include #include using namespace std; int skip;//얘를 건너띄고 출력한다. const int M = 1000000100;//오버플로우를 막기 위해서 이보다 큰 값은 구하지 않는다(k+100) int bino[201][201];//이항계수(n, m 개의 '-''o'를 뽑을 경우의 수 void calcBino() {//이항계수표를 미리 계산해 놓자 memset(bino, 0, sizeof(bino));//미리 0으로 초기화 해 놓고 for (i..