1. 문제 11444번: 피보나치 수 6 (acmicpc.net) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 이 문제는 엄청나게 큰 n번째 피보나치 수를 구하는 문제이며 피보나치 수의 성질을 잘 알고 있어야 풀 수 있는 문제이다. 피보나치 수의 점화식은 다음과 같다 f_n = f_n-1 + f_n-2, (f0 = 0, f1 = 1) 이 식을 다음과 같이 열벡터로나타낼 수 있다. C_n은 원소의 합이 f_n이 되는 열벡터이다. C_n = { {f_n-2}, {f_n-1}} 그리고 이 식을 풀어쓰면 다음과 같은 식이 나오게 된다. C_n = { {f_n-2}, {f_n-2 +..

1. 문제 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 2. 분할정복 직사각형이 있는 경우의 수는 한 부분문제에서 총 3가지의 경우 로 나눌 수 있다. 1. 왼쪽~ 중간 쪽에 최대인 직사각형이 있는 경우 2. 중간~오른쪽 쪽에 최대인 직사각형이 있는 경우 3. 중간을 포함하여 위의 두 영역에 걸쳐 있는 경우 직관적으로 한 문제당 왼쪽, 오른쪽 두개의 부분문제로 나뉘어지고, 중간을 ..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 #include #include #include #include #inclu..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #include #define max(a,b) a>b?a:b #define min(a,b) a>b?b:a int fenceHeight[20000] ={0,}; int maxRec(int low ,int high) { int ret = 0, mid = (low + high)/2, left = 0, right = 0, tmpRec = 0, width = 1, height = 0; if(low +1 == high) return f..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include //all black -> b //all white -> w //all different - > quad : x(left up)(right up)(left down)(right down) //Upside down void dividePicture(const std::string& picture, std::string (&pieces)[4], int index, int currentPiece, int count) { if..

주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀 호출을 이용해 계산 각 부분 문제의 답으로부터 전체 문제의 답을 계산 문제를 거의 같은 크기의 부분문제로 나눈다. 세가지 구성요소 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case) 자연스러운 방법으로 나누고 나눈 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 필요 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커짐 (부분 문제가 중복된다 overlapping subproblems) 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분..