Graduation 문제 - 과목이 64개 이상이라면 bit memoization은 어떻게.. cutececil 책에 나온 졸업학기 이 문제에서 수강할 과목 n이 최대 100개? 라면 bit로 메모이제이션하는 것은 어떻게 해야할까요? 현재는 n은 12과목이라서 아래처럼 해도되지만, int cache[][] = new int[10][1 << 12]; 기억해야하는 원소가 1000개 이상일때는 비트로 못하는 것인가요? 전 이런거를 생각했으나,,,,,,,, 음... int cache[][] = new int[10][100][1 << 10]; cache[semester][n/1023][n%1023] = func(...) 메모이제이션해야할 n이 30보다 큰 수라면, 비트 메모이제이션 하던 것을 아예 새롭게 다른 알고리즘으로 해야할 지.. 아님 제가 생각한 거 처럼 비트를 쪼개어야 할지? 궁금합니다. 8년 전
2개의 댓글이 있습니다. JongMan 기억해야 하는 원소가 1000개면 상태 공간의 수가 2^{1000} 이란 말씀이신데... 이거는 전 우주의 원자의 수보다 많은데 64비트 정수형 변수에 담을 수 있냐 없냐를 따질 때가 아닌 거 같군요. 이 경우 당연히, 아주 아주 당연히, 2^n 시간 복잡도는 쓸 수 없습니다. 8년 전 link cutececil 빠른 답변 진심으로 고맙습니다. 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
cutececil
책에 나온 졸업학기 이 문제에서 수강할 과목 n이 최대 100개? 라면 bit로 메모이제이션하는 것은 어떻게 해야할까요?
현재는 n은 12과목이라서 아래처럼 해도되지만,
int cache[][] = new int[10][1 << 12];
기억해야하는 원소가 1000개 이상일때는 비트로 못하는 것인가요?
전 이런거를 생각했으나,,,,,,,, 음...
int cache[][] = new int[10][100][1 << 10];
cache[semester][n/1023][n%1023] = func(...)
메모이제이션해야할 n이 30보다 큰 수라면, 비트 메모이제이션 하던 것을 아예 새롭게 다른 알고리즘으로 해야할 지.. 아님 제가 생각한 거 처럼 비트를 쪼개어야 할지? 궁금합니다.
8년 전