LIS와 유사한 문제, 다양한 방법으로 해결할 수 있다. #include #include #include using namespace std; int a[100001], exist[1000001], N; int binary_search(int start, int end, int element) { while (start a[mid]) start = mid + 1; else end = mid; } if(a[end]==element) return end; else return -1; } int main(void) { cin >> N; for(int i=0; i> a[i]; sort(a, a+N); for(int i=..
zeros배열과 ones 배열을 활용하여 각 숫자에서 0과 1이 나온 횟수를 메모이제이션으로 저장한다. #include #include using namespace std; int zeros[41], ones[41]; int z(int n) { if(zeros[n]) return zeros[n]; else if(n==0) return zeros[n]=1; else if(n==1) return zeros[n]=0; else return zeros[n]=z(n-1)+z(n-2); } int o(int n) { if(ones[n]) return ones[n]; else if(n==0) return ones[n]=0; else if(n==1) return ones[n]=1; else return ones[n]=..
LIS 알고리즘을 사용하면 간단하게 해결할 수 있다. #include using namespace std; int a[1000], length[1000], n; void dpFunc() { int res=0; for(int i=0; ires) res=length[i]; } cout > n; for(int i=0; i> a[i]; dpFunc(); return 0; }
전형적인 DP 문제로, 점화식만 이끌어 낸다면 쉽게 풀 수 있다.n번째에서의 경우의 수를 계산한다 하자n-1에서 n으로 가는 경우의 수는 한가지다.n-2에서 n으로 가는 경우는 n-2+1+1, n-2+2로 2가지다. 이때 n-2+1+1은 n-1에서 n으로 갈 떄 세준 케이스 이므로 n-2+2 의 한가지 경우만 센다.마찬가지로 n-3에서 n으로 가는 경우의 수도 한가지이다.즉, 다음과 같이 식을 세울 수 있다. DP[n]=func(n-1)+func(n-2)+func(n-3) 스스로 코드를 짠 후 아래를 눌러 읽어보자.더보기#include using namespace std;int DP[11];int func(int n) { if(DP[n]) return DP[n]; if(n==1) return ..
DP를 사용하여 가능한 최수 경우의 수를 Bottom-Up 방식으로 구해준다.#include using namespace std;int main() { int N, DP[1000001]; cin >> N; DP[1]=0; for(int i=2; i
동적 계획법(Dynamic Programming, DP)은 알고리즘이라기 보다는 하나의 기술이다. 분할 정복에서 사용하는 기법으로, 큰 문제들을 작은 문제들로 쪼개서 그 답을 저장하고 재활용한다. 쉽게 말하자면 '기억하며 풀기' 라고 할 수 있다. 왜 DP를 사용하는가? 다음과 같은 함수를 계산한다고 해보자. $f(a, b) = f(a-1, b)+f(a, b-1)\space(a, b\ge 1)$ $f(0, n)=f(n, 0)=1$ 이떄 f(2, 2)를 계산한다고 하면 다음과 같은 계산 과정를 거치게 된다. 위 에서는 총 5번의 연산을 수행하는데, 이때 f(1, 1)에 대한 연산을 2번 수행하고 있으므로 이를 미리 연산한다고 가정하면 f(2, 2)를 구하기 위해 4번의 연산만 수행하면 된다. 만약 a, b..
