1. 완전 탐색 알고리즘 이 문제는 주어진 문자열을 3-5글자씩 끊어서 특정 규칙에의해 정해진 난이도를 부여하여 전체 문자열의 최저 난이도를 계산하는 문제이다. 이 문제를 풀 함수는 한번 호출되었을 떄 문자열을 3-5길이의 문자열과 나머지 문자열로 분할한다. 난이도 판별함수를 실행하여 문제를 해결하고 (최대 5번의 for문) 나머지 문자열은 재귀호출하여 다음 부분문제로 넘어간다. 이 함수는 문자열의 길이가 n일 떄 최소 n/3 의 깊이와 최대 n/5 깊이를 가지고 3^n/3 > leaf > 3^n/5 인 잎의 개수를 가진다. 따라서 완전 탐색은 지수적 수행 시간을 가지며 이는 시간초과를 의미한다. 2. 메모이제이션 적용 부분문제는 동일하다 i 이전과 i 이후 i의 이전 문자열은 i 이후 문자열을 해결하는..

동적 계획법을 적용한 문제 풀이 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 117 #include #include #i..

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 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 =..