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

탐색가능한 모든 조합의 수를 계산 하는 문제로 완전탐색 을 이용해서 문제를 해결할 수 있었다. 여기서 중요한 것은 중복으로 계산되는 것을 제외하여야 한다는 것이다. 즉 (1,0)과 (0, 1)은 서로 같은 사람끼리 짝을 이루었으므로 같은 경우라고 인지하여야 한다. 이 부분을 해결하기 위해서 숫자 순서대로 먼저 오는 답 하나만 계산할 도록 first 인자를 이용해서 선택되지 않은 학생중에서 가장 번호가 빠른 학생의 짝을 찾도록 하였다. c = int(input()) def countPair(): cnt = 0 first = -1 for i in range(n): if not visited[i]: first = i break if first == -1 : return 1 for i in range(first..

알고리즘 문제 해결 전략 책의 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..