1. 문제 코딩테스트 연습 - 징검다리 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 2. 결정 문제 이진 탐색을 사용하는 문제 보통 dp로 풀 수 있지만 n이 클 때 보통 사용한다. 이 문제도 dp로 풀 수 있지만 입력이 엄청 커 이진 탐색을 사용하여 최소의 거리의 최대값을 구하였다. 여기서 이진 탐색은 lo 값을 리턴하는데 참인 조건일때 lo를 mid로 설정하기 때문에 lo를 리턴해야한다. (참인 조건일때 hi를 mid로 설정하면 hi값 리..

1. 문제 심사하는 직원들은 각각 심사하는데 시간이 전부 다르다 이 시간들의 배열이 주어지고 입국 심사해야하는 사람의 수 n이 주어진다. 이때 모든 사람을 심사했을때 걸리는 최소의 시간을 구하여라. 2. 큐를 활용한 풀이 => 시간 초과 이는 그리디 적으로 풀 수 있다. 모든 사람이 가장 빨리 끝나는 심사 위원을 선택만 하기만하면된다. 따라서 모든 시간을 우선순위 큐에 넣어놓고 n번을 그리디적으로 선택 하는 것이다. 그 후 가장 긴 시간을 찾으면 된다. 이는 nlogn 으로 입력이 아주 큰 문제이므로 시간초과가 나오게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #include #include us..

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