Study hard

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 [풀이] 이분탐색을 사용하여 풀었다. ※이분탐색을 하려면 배열 A를 정렬시켜야 하므로 vector자료구조를 사용하였다. #include #include #include //sort using namespace std; int N, M; vectorA; void Search(int n) { int front = 0, rear = N - 1; while..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [풀이] 10815번 숫자 카드와는 다르게 상근이가 해당 숫자 카드를 몇 개 가지고 있는지 확인하는 문제였다. 기본 이분탐색으로는 카드의 유무만 판단할 수 있기 때문에 upperbound와 lowerbound를 구하는 방식을 사용했다. upperbound는 찾으려는 값보다 큰 값이 처음 나오는 위치이고, lowerbound는 찾으려는 값 이상인 값이 처음 나오는 ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [풀이] 상근이가 가진 숫자카드를 배열에 저장하고 정렬해 놓고, 확인할 카드가 입력될 때마다 이분 탐색으로 해당 수가 있는지 확인하였다. 입출력 때문에 시간 초과가 나서 cin.tie(0)과 ios_base::sync_with_stdio(false)를 추가해줬다. #include #include //sort using namespace std; #define Max ..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net [풀이] 이분탐색으로 풀 수 있었다. 먼저 입력으로 받은 집의 좌표들을 정렬하고, low는 1, high는 가장 처음 집과 가장 마지막 집의 거리로 설정하였다. #include #include using namespace std; #define Max 200001 int N, C; int Home[Max]; bool Share(int dist..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, www.acmicpc.net [풀이] 이분 탐색으로 해결하였다. 모든 변수를 long long으로 선언해야 범위에 벗어나지 않았다. #include #include //max using namespace std; #define Max 1000001 long long N, M; long long Tree[Max]; bool cutTree(int height) { long long trees = 0; for (int i = 0; ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [풀이] 이분탐색으로 푸는 문제였다. 처음에 재귀로 풀려고 했지만 시간초과에 계속 틀렸다고 떠서 반복문으로 바꿨다. 초기 low는 어찌 됐든 1이상의 길이로 자를 수 있으니까 1, high는 입력되는 전선들 중 가장 긴 전선의 길이로 설정했다. 그리고 이분탐색으로 low부터 high까지 길이중 K개 전선들을 N개 이상으로 나눌 수 있는 가장 긴 길이를 구했다. #inc..