1. 최적 문제 n개의 강의 중에서 k개이상의 강의만 남겨놓고 철회할 때 최소 누적 등수를 구하는 문제이다. 이것은 k개 까지 하나 하나 철회해보면서 누적등수를 계산하고 그 중에서 최소값을 구하는 최적화 문제이다. 이 문제를 결정문제로 변형해보자 2. 결정 문제 isOkay(r) = r의 누적등수가 주어졌을 때 이것보다 작은값이 있는가? 위와 같은 식을 토대로 함수를 작성해 보았다. isOkay는 k개 까지 모든 경우를 세서 주어진 누적등수보다 작은 값이 나오면 true 작은 값이 나오지 않을 경우 false를 반환한다. 하지만 이 함수는 최악의 경우 2^1000 개를 카운트하므로 당연히 제출한 코드는 시간 초과를 내뿜었다. 이전 꺼랑 비교해서 더 큰값이 나올 경우 가지치기하려는 생각도 해봤지만 답을 구..

1. 결정 문제 이 문제를 결정문제로 해석한뒤 이진법으로 풀어보자 D에 k번째 표지판이 있는지? 이것을 이진법으로 0 , 8030,000 까지 탐색하면 답이 나올 것이다. 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 #include #include #include #include int T, N, K; int L[5000], M[5000], G[5000]; bool search(int D) { int sign = 0; for(int i = 0; i = L[i] - M[i]) sign += 1 + (std::min(D,L[i]) - L[i] + M[..

1. 최적화 문제 이 문제는 각 기지를 모두 연결할 수 있는 거리 중에서 최대 거리를 최소화 하는 문제로 모든 경우의 수를 만들어서 최대거리가 최소인 경우를 찾으면 된다. 하지만 이 최적화 문제는 경우의 수가 너무 많다. 2. 결정 문제 결정 문제로 문제를 변형해보자 모든 기지를 통신반경 D인 무전기로 연결할 수 있는지? 이 문제를 이진탐색으로 여러번 수행하면 최적해에 아주 가까운 근사값을 얻을 수 있을 것이다. 3. 코드 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 ..

1. 결정 문제(decision problem) 결정 문제란 예 아니오 현태의 답만이 나오는 문제들을 가리킴. 최적화 문제의 반환 값은 답의 경우의 수가 무한한 데 반해, 결정 문제는 두가지 답만 있음. 그러므로 결정 문제가 최적화 문제보다 더 어렵거나 시간 복잡도가 더 클 일도 없다. 2. 결정 문제로 바꾸기 어떤 문제에서 최대가 되는 x를 구하자고 하자 이를 결정 문제로 바꾸는 것은 다음과 같다. y이상일때 문제가 해결되는지? 이 결정 문제를 이분법을 사용하여 10번 100번 반복하면 결국 원래 문제인 x를 구할 수 있다. 3. 이분법의 함정 답이 가질 수 있는 가지수가 유한일 때 이분법은 수치적 안정성을 잃어버리게 된다. 최적화 문제는 아주 미세한 차이가 나더라도 답과 가까운 값을 반환하지만 결정 ..

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. 완전 탐색 주어진 블록으로 빈 공간에 넣을 수 있는 최대 개수를 구하는 문제이다. 이 문제를 풀기 위해서는 일단 다음과 같은 함수가 필요할 것 같다. - 블록들을 회전 시키는 함수. - 왼쪽위에서부터 오른쪽아래까지 블록을 넣는지 않넣는지 , 블록을 넣을때 회전하는 케이스 까지 모든 경우를 세는 함수. 이 완전 탐색으로는 시간안에 못풀것 같다. 10*10 의 빈 공간이 있으면 최대 5^100번 함수가 실행 될것 같기 때문이다. (5가지 경우 수 선택 x 0 90 180 270에 100개의 칸) 물론 이것이 실제 돌아가면 훨씬 더 빨리 수행될것이다. 하지만 그래도 엄청나게 큰 수행시간 일 것이다. 2. 조합탐색 - 가지치기 단순 휴리스틱 함수를 구현하면 더욱 빨리 수행될 것 같다. 이 함수는 남은 칸의..