1. 완전 탐색 이 문제는 packing 문제에서 중복가능한점을 제외하고 전부 같다 따라서 이문제는 다음과 같이 쓸수있다. menu(price) = price로 시킬 수 있는 메뉴의 최대 선호도 이에 모든 메뉴를 for문으로 탐색하면서 price를 넘어가지 않도록 선택하는 재귀함수를 구현하면 답을 구할 수 있다. 2. 반복적 동적 계획법 하지만 이 문제의 price의 최대 값은 10억이다. 총 n메뉴가 있을때 값이 2만을 넘지 않으므로 n^50000시간 이상 걸릴 수 있을 것이다. 이렇게 큰 수를 메모이제이션 하려면, 슬라이딩 윈도 기법을 사용해야한다. 이 기법은 반복적 동적 계획법을 이용해야만 쓸 수 있다. menu(price) = price로 시킬 수 있는 메뉴들의 최대 선호도 합 이 식이 의미하는 ..

1. 완전 탐색 이 문제는 BOARDCOVER에서 문제를 풀었듯이 완전 탐색으로 해결 할 수 있다. 각 차례마다 사용 가능한 모든 블록들을 모든 위치에 넣어보면서 한번이라도 짝수 차례일때 블록을 못넣으면 함수를 종료시키면 된다. 2. 비트 마스크를 사용한 동적 계획법 이 문제는 주어진 게임판의 상태에 따라 승패가 좌우된다. 이전 까지의 블록의 배치와 지금이 누구 차례인지 알 필요 없다는 것이다. 게임판은 5*5배열로 '#' 과 '.' 두 상태가 있으므로 비트마스크로 배열을 하나의 정수로 표현할 수 있다. 이 정수 하나로 메모이제이션이 가능해지고 완전 탐색에서 더욱 수행시간을 최적화 시킬 수 있다. 3. 비트마스크를 사용한 블록 배치 가능 유무성 판단 이 문제에서 블록의 형태는 L자 형과 | 형 ㅡ 형 이..

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연산..