1. 완전 탐색(시간초과, 잘못된 구현) 이 문제는 각 친구들이 먹을 수 있는 음식이 하나라도 먹을 수 있게 하는 최소한의 메뉴를 선정하는 문제이다. 이 문제는 다음과 같이 완전 탐색할 수 있다. - 친구들을 기준으로 탐색 - 음식들을 기준으로 탐색 모든 친구들이 먹을 수 있는게 하나라도 있어야하므로 친구들을 기준으로 탐색하는게 더욱 구현이 직관적일 것이다. 코드는 다음과 같다. 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 6..

1. 항상 최선을 다해 게임을 플레이한다. 이 문제는 자신의 차례일 때 항상 최선을 다한다. 다음 차례인 상대의 선택을 고려하면서 선택해야한다는 것이다. 어떻게 해야 최선일까? 자신의 선택한 점수 - 다음턴에 상대방이 선택한 점수 가 최대일때가 최선의 선택이 된다. 2. 재귀 함수 한번 위에 가정한것을 식으로 표현해보자. i는 0~3까지이며 뭘 선택 할 것인지를 나타낸다 0: 맨 왼쪽 선택 => myTurn = board[lo] dlo => +1, dhi => 0 1: 맨 오른쪽 선택 => myTurn = board[hi] dlo => +0, dhi => -1 3: 맨 왼쪽 두개 삭제 => myTurn = 0 dlo => +2, dhi => 0 4. 맨 오른족 두개 삭제 => myTurn = 0 dlo ..

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 118 119 120 121 122 123 124 125 126 12..

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 #include #include #include #include #include #include std::vector cache; int elements[500]; double skip; 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 #include #include #include #include #include #include #include using namespace std; st..

1. 문제의 변형 n개의 정사각형으로 모든 경우의 도형을 만들 수 있는 수는 구하기가 까다롭다. 하지만 문제는 세로로 단조인 폴리오미노를 구하라는 것이므로 쉽게 문제를 변형하여 풀 수 있게된다. 세로로 단조인 폴리오미노는 가로의 직사각형으로만으로 모든 경우의 수를 구할 수 있음을 나타낸다. 즉, 이문제 는 탑쌓기로 변형할 수 있는데 1층에 몇개의 정사각형을 쓰는지 2층에 나머지 정사각형에서 몇개를 쓰는지 . . . n층에 몇개를 쓰는지 결국 이문제는 재귀 호출로 문제를 풀 수 있게 된다. 2. 점화식 이 문제를 풀 점화식은 poly(remain, before) = remain만큼 정사각형이 남아있는 단계에서 before의 개수가 이전에 쓰인 경우의 세로 단조인 폴리오미노의 개수 move = 1 (befo..