중점 1. 넓은 범위 내에서 숫자를 찾는다. 이때 시간 제약은 1초이다. 2. 숫자의 존재 여부만을 알아내면 된다. 넓은 범위 내에서 숫자를 찾아야 한다. 이때 1초라는 시간내에 숫자의 존재 유무를 찾아야한다. 따라서 이분 탐색을 이용해서 빠른 시간내에 찾아야 되겠다는 생각을 했다. 따라서 입력받는 숫자를 배열에 저장 후 sort를 진행한 후 이분탐색을 진행한다. #include using namespace std; int a[100005]; int n; int binary_search(int target){ int st = 0; int ed = n - 1; while (st target){ ed = mid - 1; } else { return 1; } } return 0; } int main(void)..
coding-test
중점 1. 시간 제한 1초 라는 점. 2. 연속되는 수를 계속적으로 더해야 한다는 점. 이를 통해서 최종 답을 구한다. 3. 2번을 토대로 작은 부분의 문제의 해결이 전체의 답을 구한다는 것을 발견했다. 시간 제한이 있고 연속적으로 반복되는 작업을 수행한다는 점에서 DP 알고리즘을 사용해야 한다고 생각이 들었다. 따라서 배열을 선언하고 n번에는 n번째 까지의 입력받은 수들 중 연속하며 합이 최대인 경우를 저장한다. 만약 이전에 연속값을 더한것 보다 n번째 입력받은 값이 크다면 입력값을 저장한다. 매 순간 마다 두개를 비교하여 그때의 최종 값이 저장되게 한다. 이때 total_max라는 값을 선언하여 매순간 비교하여 연속되는 최댓값을 저장하게 한다. 정답 코드 #include using namespace ..
중점 1. A의 원소를 B에 존재하는지 찾아야한다. 모든 원소를 찾아야 한다. 2. 1번의 기준을 만족하는 원소의 개수와 그것들이 무엇인지 출력해야한다. 3. 출력할때 오름차순으로 출력한다. 원소의 유무를 찾는다는 것에서 이분 탐색을 생각했다. 따라서 입역받는 A와 B에 대한 정렬이 필요할 것이라고 생각했다. 또한 만약 조건을 만족한다면 해당 원소를 이후에 출력해야한다. 따라서 해당 원소를 push back하여서 저장하기로 했다. 이유는 오름차순 출력이기 때문이다. 원소를 저장할 곳을 queue로 지정한다. binary_search함수를 이용해서 코드 수를 줄인다. 해당 함수는 만약 이분탐색을 통해서 해당 값을 찾으면 ture 값을 아니면 false를 return 한다. 정답 코드 #include usi..
중점 1. 랜선의 길이는 2^31 - 1 이다. 따라서 long long형태 및 unsigned 형태를 사용한다. 2. 주어진 조건을 만족하면서 최대의 값을 찾는 문제이다. 각각의 랜선에 대해서 X값으로 나눈 뒤에 n과의 비교를 통해서 max값 인지 아닌지를 판단한다. 따라서 조건을 만족하면서 최댓값을 구하여야하는 최적화 문제에 해당한다. 따라서 이분 탐색 중 parametric search를 사용해야 함을 알 수 있다. 그렇지 않다면 순차 탐색을 통해서 해야함으로 오랜 시간이 걸린다. 여기서 이분 탐색을 위해서 입력 받은 랜선들의 값 중 제일 긴 값을 end 값으로 설정한다. 또한 min값은 (start 값) 1로 해야한다. 따라서 mid 값을 설정하고 이를 이용해 이분탐색 알고리즘을 사용하면 된다. ..
중점 1. 시간 제한이 0.15초이다. 2. 큰 문제가 작은 문제의 합으로 해결되며 그 과정이 동일하다. 풀이: n에 대한 답을 구하기 위해서 재귀등을 이용한 방법을 이용해서도 해결 가능하겠지만 시간 제한이 있기에 문제자가 요구하는 방안은 아닐 것이다. 따라서 점화식이 미리 주어져 있으며 시간 제한이 적기 때문에 DP를 이용하여 문제를 풀어야 한다고 생각한다. 먼저 전역변수로 하위 단계의 답을 저장할 변수를 선언한다. 이후 반복문을 통해서 각 배열의 값에 알맞은 답을 저장한다. 이때 이미 배열에 저장된 값을 활용하는 알고리즘을 사용한다. 또한 위 알고리즘을 사용하기 위해서 초기값을 미리 설정해 놓는다. 이후 n에 대한 값을 출력한다. #include using namespace std; int d[100..
중점: 1. 시간 제한 0.5초 2. 총 합의 최솟값을 구하는 문제 풀이: 시간 제한이 0.5초 이며 큰 문제를 작은 부분의 문제로 분할 할 수 있다는 부분에서 DP 알고리즘을 사용해야 겠다고 생각하였다. 여기서 그리디 알고리즘의 사용도 생각해 보았지만 순서의 중복이 안된다는 문제 때문에 최솟값 만을 고르는 것은 전체 정답의 최솟값이 되지 않을 수 있다는 생각을 하게 되었고 DP를 사용하기로 했다. 따라서 R, G, B의 값을 행렬을 통해서 입력받은 후에 각각의 위치에서 최소의 값을 더해가는 반복문을 생각하였다. 위치의 중복이 없고 최솟값을 찾아서 더한 합계의 행렬의 마지막 행에서의 최솟값이 문제가 원하는 정답이다. 정답 코드: #include using namespace std; int color[10..
