myblog

https://en.wikipedia.org/wiki/Trie

1. Allocation 오름차순으로 정렬한 뒤 돈이 부족할때 까지 산다. - 시간 복잡도 sorting part : O(NlogN) => Counting sort로 O(N)으로 단축 시킬 수 있음 processing part: O(N) => 총 O(N) 2. Plates Dynamic programming 이용 첫 N stack에서 P개를 뽑아 만들수 있는 maximum sum을 dp[N][P]라고 하면 dp[i][j] = max(dp[i][j],sum[i][x]+dp[i-1][j-x]) for i [1,N]: for j [0,P]: dp[i][j] =0 for x [0,min(j,K]: dp[i][j] = max (dp[i][j],sum[i][x]+dp[i-1][j-x]) - 시간 복잡도 O(N*P*..

Fixed-length Encoding & Variable-length Encoding 일반적으로 문자(character)는 8bit의 2진수로 저장이 된다. 각 문자가 같은 크기의 저장공간을 차지하기 때문에 이것을 fixed-length encoding이라고 부른다. 따라서 문자열을 압축하기 위해서는 어떤 문자들의 저장공간을 8bit 보다 작게 가져가야 한다. 이때 사용하는 방법이 variable-length encoding이다. 문자열에서 특정 문자들이 다른 문자들에 비해 더 빈번하게 사용되는 경우가 있다. 이러한 경우 자주 사용되는 문자를 짧은 bit, 적게 사용되는 문자를 긴 bit의 2진수로 mapping 하게 된다면 총 문자열의 크기를 줄일 수 있다. 하지만 variable-length enc..