돌이 코딩하는 방

사실 Technique라고 하기도 뭐하지만... 최근에 여러문제들을 풀면서 느낀 점이 있어서 간단하게 적어 놓으려고 한다. Prefix Sum 이란? Prefix = 접미사 sum = 합. 그니까 앞에서 부터의 합을 의미한다. 어떠한 값이 들어있는 기존의 배열 arr이 존재한다고 하면 $pre[x]=\sum_{i=1}^{x} arr[i]$ 로 표현되는 값들이 prefix sum들이라는 것이다. How? prefix sum 배열을 채우는 것은 $O(N)$만에 정말 간단하게 할 수 있다. $pre[i]=pre[i-1]+arr[i]$ 로 할 수 있다. 어떤 식으로 활용해야 할지에 대해서 고민을 해봐야 한다. prefix sum은 구간 합을 구할 때 주로 사용되어진다. i부터 j까지의 구간합은 $pre[j]-p..

DP에서 쓰이는 테크닉들 중 처음으로 비트마스크(Bitmask)에 대해서 설명하려고 한다. 보통 DP 말고 다양한 곳에서 쓰이기도 하지만 이글에서는 DP에 쓰이는 방향으로 초점을 두고 진행할 예정이다. Bitmask란? Bitmasking 기법이라고도 불리며, Bit에다가 masking을 하는 것이다. 다시 말해 DP값의 중요한 요소중 한가지인 '상태'를 배열등이 아닌 한 개의 숫자로 표현하겠다는 것이다. 예를 들어 bool arr[4] 배열이 채워질 수 있는 모든 경우의 수를 0~15의 수에 대응을 시켜 표현 하겠다는 것이다. 언제 & 왜? Bit masking은 보통 제한이 굉장히 작으면서, 모든 경우를 다 표현하고 싶을 때 사용한다. 이때 비트를 사용하기 때문에 스케일은 당연히 지수 스케일이며, 어..