Baekjoon Online Judge6 피보나치 수열 정리 (백준 2749 피보나치 수 3, 11444 피보나치 수 6) 1. 피보나치 수열이란? 피보나치 수열은 0번째, 1번째 항이 0, 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 피보나치 수열의 점화식을 세워 보자면 $ F_{n} = F_{n-1} + F_{n-2} (n>=2) $ 이다. 위의 식처럼 점화식이 무척 간단하기 때문에 N의 수가 작을 경우에는 동적 계획법을 통해 피보나치 수를 구할 수 있다. 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8,.. 2020. 4. 28. 동적 계획법(DP) 1 (11053 가장 긴 증가하는 부분 수열 LIS) DP란 다이나믹 프로그래밍의 약어이다. 한국어로 동적 계획법이라고 말한다. 동적 계획법은 어떠한 복잡하거나 큰 문제를 간단하고 작은 문제로 나누어서 푸는 알고리즘 설계 기법이다. 복잡한 문제가 같은 부분이 반복되는 부분 구조와 최적의 부분 구조를 가지고 있을 때 여러 개의 부분 문제로 나누어 설계하여 풀 수 있다. 그래서 일반적으로 부분 구조를 통해 점화식을 만들고 Bottom-Up 방식과 Top-Down(재귀) 방식을 통하여 전체 문제를 해결한다. 이 동적 계획법의 핵심 기법은 메모리제이션이다. 메모리제이션은 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 그래서 DP 배열을 만들어서 그.. 2020. 4. 28. 1395 스위치 with Lazy Propagation Lazy Propagation으로 구간 합 구하기 2를 풀고 바로 다음 문제로 넘어갔다. 처음에는 모두 꺼져있고 구간이 주어질 때 키고 끄고를 반복하여 구간 내 켜져있는 스위치의 개수를 출력하는 문제이다. 스위치를 두 번 키면 결국 같은 상태가 된다. 따라서 홀수일때만 노드의 값을 변경해주면 된다. 처음 그냥 구간내 개수로 변경하면 되겠지 했다가 다른 구간에서 변경이 되는 경우도 있으므로 구간 개수에서 현재 노드의 값을 빼줘야하는 것을 뒤늦게 알게 되었다. void update_lazy(int idx, int l, int r) { if (lazy[idx] != 0) { if (lazy[idx] % 2) seg[idx] = (r * 1LL - l + 1) - seg[idx]; if (l != r) { la.. 2020. 4. 2. 10999 구간 합 구하기 2 with Lazy Propagation 2차원 세그먼트 트리까지 공부를 하고 Lazy Propagation을 배우게 되었다. 직역하면 게으른 전파라는 소리이다. 이것을 쓰는 이유는 구간 전체를 변경할 때 빠르게 구하기 위해서이다. 기존 세그먼트 트리에서 Update를 할 때 한 점을 갱신한다. 왼쪽 오른쪽 구간을 나누고 구간 안에 속해있으면 탐색을 안 하기 위해서 세그먼트 트리를 쓰는 것인데 구간 전체를 변경하게 된다면 결국 각각의 점을 들어가서 변경을 해야 한다. 이러한 비효율적인 일을 막기 위해서 변경은 나중에 방문을 할 경우 한 번에 하고 변경되는 값을 따른 배열에 모아놓는 것이다. 자세한 구현법은 코드와 함께 정리하겠다. 1. 먼저 세그먼트 트리와 똑같은 크기의 Lazy 배열을 만든다. 2. 그리고 기본적인 세그먼트 트리와 똑같이 구현.. 2020. 4. 2. 이전 1 2 다음