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. 완전 탐색 이 문제는 먼저 문자열들이 주어졌을 때 모든 문자열이 어떤 문자열에 얼마나 곂칠 수 있는지 계산해야한다. 이 계산은 모든 문자열의 개수 n에 대하여 overap[A][B] = A다음으로 B가 왔을때 중복되는 것을 제외한 최소의 길이 에 저장되어진다. 이 배열의 초기는 A = -1일때 B는 자기 자신의 길이를 나타낸다. 이후 계산할 restore()함수에서 이것을 더하여 최소 값을 나타낸다 next는 모든 문자열을 가리키며, 이미 쓴 문자열일경우 패스한다. restore(last, used) = min( overlap[last][next] + restore(next, used + (1

1. 완전 탐색 원래 가격은 다음에 해당해야한다 1. 바뀐 가격의 숫자들로만 이루어져있다. 2. 바뀐 가격보다 싸야한다 3. m의 배수야 한다. 다음은 이런 정보들을 통하여 완전 탐색하는 코드이다. 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 #include #include #include #include using namespace std; //current p..

1. 비트 마스크 이진법 관련 연산들을 아주 빨리 할 수 있도록 정수의 이진수 표현을 자료 구조로 쓰는 기법 (엄밀하게 자료 구조라고 할 수 없음) 2. 비트 마스크의 장점 - 더 빠른 수행 시간 : 대부분 연산은 O(1)에 구현된다. - 더 간결한 코드: 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문 - 더 작은 메모리 사용량: 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있다. - 연관 배열을 배열로 대체: map같은 연관 배열 객체를 단순 배열을 사용해 같은 정보를 표현 3. 비트 연산자 - AND연산: 두 비트가 모두 1인 경우. 1반환 - OR연산: 두 비트중 하나라도 1인 경우. 1반환 - XOR연산: 두 비트중 하나만 1인 경우 (1의 개수가 홀수). 1반환 - NOT연산..

1. 완전 탐색 이 문제는 다음 과 같은 규칙이 있다 gen 0: gen0 gen 1: gen1 gen 2: gen1 + -gen1 gen 3: gen2 + -gen2 gen 4: gen3 + -gen3 . . . gen n: gen n + -gen n 여기서 -gen1은 gen1의 가운데 부호를 마이너스를 바꾼 것이다. 이를 통해 우리는 완전 탐색 함수를 구현할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 std::string minusDragon(int gen) { if(gen == 1) return "FX-YF"; return dragon(gen-1) + "-" + minusDragon(gen-1); } std::string dragon(int gen) { if(gen == 0) 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 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..