본문 바로가기

백준4

피보나치 수열 정리 (백준 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.
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.
12899번 데이터 구조 세그먼트 트리를 응용한 문제이다. 이제 막 세그먼트 트리를 공부해서 처음엔 추가하는 것도 어려웠다. 추가하는 것은 set을 써도 가능하지만 세그먼트 트리를 공부하기 위한 것이니까 안 하고 고민을 해봤다. 그냥 세그먼트 트리에서 미리 다 만들어져 있다고 가정하고 일반적으로 Update 하듯이 값을 수정해주면 되었다. 그리고 값을 수정한 뒤 X번째로 작은 수를 찾아야 하는데 이 방법을 몰라서 세그먼트 트리를 다시 공부하였다. 결국 방법은 트리 구조에서 마지막번째 레벨의 노드가 1~2000000까지 있게 만들었으므로 K번째 노드가 수 K를 나타내는 것으로 나타낼 수 있다. 그래서 각 노드의 값을 그 수의 개수로 입력하고 세그먼트 트리로 개수들의 합을 저장한다. K 번째 수는 결국 왼쪽에 K개가 있으면 그 노드.. 2020. 4. 2.

티스토리툴바