https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net • 접근 보통 피보나치 문제를 접근할 때에는 divide and conquer 또는 DP로 접근한다. n이 매우 작은 경우(BOJ 2747 참조)에는 재귀로 풀어도 풀 수 있다. 시간복잡도가 O(2^N)이기 때문이다. 그보다 n이 조금 더 커진다면 DP로 풀 수 있다. 이 경우 time complexity가 O(N)이므로 N이 대략 2억 언저리인 경우까지도 해결이 가능하다. 이 문제는 다르다. n의 upper bound가 1e18이다. 이런 경우에는 O(N)으로 풀 수 없다. ..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net divide and conquer 문제인데, 다소 까다로운 부분이 있다. 직접 2차원 배열을 돌면서 수를 일일이 입력하고 다니면 N>=15라는 조건 때문에 시간 초과가 발생한다. 따라서 4개의 사분면으로 분할하여 계산을 생략해주는 과정이 반드시 필요하다. 나는 sizeRec에 미리 작은 사분면의 넓이를 저장한 후에 어느쪽 사분면이냐에 따라서 0, 1, 2, 3을 곱해 주어 직접 계산하는 과..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net divide and conquer로 해결할 수 있는 문제이다. start에서 end까지의 부분 히스토그램을 보았을 때, 그 안에서 만들 수 있는 직사각형의 최대 넓이는 세 경우 중 하나에서 구할 수 있다. 편의상 mid = (start+end)/2 로 정의한다. 1. start ~ mid까지의 부분 히스토그램 중 최대 넓이 2. mid+1 ~ end까지의 부분 히스토그..