기록보관소

피보나치 수 2는 다이나믹 프로그래밍으로 해결할 수 있는 문제입니다. 피보나치 수를 구하기 위해 피보나치 수를 보관할 배열을 선언한 후 반복적인 연산을 통해 피보나치 배열을 업데이트시켜 최종적으로 원하는 피보나치 수를 구하도록 하여야 합니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) long long int fibo[120]; int N; int main(void) { fibo[0] = 0; fibo[1] = 1; scanf("%d", &N); if (N == 0) printf("%d\n", fibo[0]); else if (N == 1)printf("%d\n", fibo[1]); else { for (int i = 0; i < N-1; i..

가장 긴 증가하는 부분 수열 2는 이분법을 사용하여(솔직히 이 문제의 핵심은 이분법이 아닌 것 같습니다. 이분법만 아는 것으로는 조금 부족할 수도 있을 것 같습니다.;) 풀 수 있는 문제입니다. 원래 문제인 가장 긴 증가하는 부분 수열(LIS)문제는 동적계획법(완전탐색 + 메모이제이션)으로 해결할 수 있으나 N의 개수가 100만이 되어서 더 빠른 방식의 알고리즘을 고안해야 합니다. 문제를 곰곰히 생각해보면 다음과 같은 통찰을 얻을 수 있습니다. 수열의 어떠한 위치를 탐색하고 있다고 가정하면 우리는 그 이전의 수들로만 구성된 수열들을 상상할 수 있습니다. 어떤 수열은 1개의 숫자로만 이루어질 수도 있고, 어떤 수열을 2개, 3개 혹은 그 이상의 숫자로 만들어질 수 있을 것입니다. 우리가 구하고자 하는 것은..