KPU CE

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 풀이 M개를 N번을 탐색하게 된다면 시간복잡도가 N^2이므로 시간초과가 난다. 그래서 이분탐색을 사용하여 NlogN으로 풀었다. 이분탐색만 사용하면 풀 수 있는 간단한 문제였다. 입력을 받을때 원래 cin 받았는데 시간초과가 나서 scanf으로 입력받고 출력도 printf로 하니까 시간초과 문제도 해결하였다. 소스코드 1 2 3 4 5 6..

문제 https://www.acmicpc.net/problem/17124 17124번: 두 개의 배열 정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있 www.acmicpc.net 문제 해결 A[i]를 하나 택하고 A[i]보다 작은 것들 중에 가장 큰 B[j], A[i]보다 큰 것들 중에 가장 작은 B[j]가 답이다. 이것을 구하는데 큰것 작은것 두개의 이분탐색을 만들어서 두개의 절대값을 비교하였다. 만약 작은것 중에 A[i]보다 작은 것이 없으면 B 배열에서 가장 작은 값인 B[1] 만약 가장 큰 값이 없을 경우 문제에서의 최대값인 10..