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) 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분..

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 #include #include #include int clocks[4][4] = {0,}; int switchPushNum[10] = {0,}; std::vector switchToClock = { {0, 1, 2}, {3, 7..

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 #include bool gameboard[20][20] = {false, }; // y1, x1, y2, x2 int block[4][4] = { {1,-1, 1, 0}, {1, 0, 1, 1}, {1, 0, 0, 1}, {0, 1, 1, 1} }; bool isOkay(int h, int w, int y, int x) { re..

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 #include #include #include int picnic(std::vector& friendPairList, bool* isInclude, int studentNum, int index, int includeCount) { int ret = 0, first = 0, second = 0; if(includeCount == studentNum) return 1; if(index == friendPairList.size()) return 0; first =..