1. 균형잡힌 이진 검색트리를 이용한 풀이 트립 을 구현하여 수열이 추가될때마다 이진 검색트리를 유지 시키고, k번째 수열을 찾는 kth함수를 구현하여 중간값을 찾는다. 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..

1. 완전 탐색 이 문제는 주어진 문자열 입력에 대해 중복된 부분 문자열의 개수를 센다음 k개 이상의 중복 문자열 중에서 가장 긴 부분 문자열을 찾는 문제이다. 하지만 부분 문자열을 전부 만들어서 카운트하면 시간안에 수행이 불가능하다. 2. 공통 접두사의 최대 길이 사용 접미사 배열을 만들고 공통 접두사의 최대 길이를 계산하면 시간안에 해결할 수 있다. 이 때 중요한 것은 k개를 더한것과 비교하는 것이다. 이는 k번째 접미사와 접두사가 일치하지않으면 0이되기 때문에 이는 완활히 작동된다. 다음은 책에있는 코드이다. 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..

1. 비트 마스크 문제 부울 배열들을 비트 마스크 로 풀어내는 문제이다. 과목 => 선수과목 학기 => 과목 학기마다 선수과목이 포함되어 있는지 확인하고. 강의를 들을 수 있는 과목을 선택하여 조합 탐색하면 쉽게 답을 구할 수 있다. tmpSelect = semester[j] & (~select); => 이번 학기에 들을 수 있는 수업중 이미 수강한것은 제외시킨다. => 최상위 비트또한 반전되어 없어진다. => 모든학생이 이번 학기에 들을 수 있는 강의들 if((tmpSelect&(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 65 66 67 68 69 70 #include #include #include #include #include using namespace std; int T, n; int r[200]; int p[200]; vector ratio; int add[200]; void potion() { if(ratio.back()

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