알고리즘/이분 탐색(4)
-
[백준/C++] 1764번 듣보잡
문제: www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제풀이 이분 탐색 문제이다. 벡터 3개를 선언하여 하나는 듣도 못한 사람, 하나는 보도 못한 사람, 하나는 둘의 중복되는 문자열인 듣도보도 못한 사람을 넣는다. 코드 #include #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin>>N>>M; vect..
2021.02.09 -
[백준/C++] 1620번 나는야 포켓몬 마스터 이다솜
문제: www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제풀이 이분 탐색 문제이다. 포켓몬 이름이 입력으로 들어오면 포켓몬의 번호를, 포켓몬의 번호가 입력으로 들어오면 포켓몬의 이름을 출력해야 한다. 벡터를 두 개 선언해서 하나는 포켓몬 이름을 저장하고 다른 하나는 번호와 이름을 같이 저장한다. 번호와 이름을 같이 저장한 벡터는 sort() 함수를 이용해 사전 순으로 정렬해준다. 문제에 대한 입력을 받을 때 string 형으로 ..
2021.02.06 -
[백준/C++] 1920번 수 찾기
문제: 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 문제풀이 이진 탐색 문제이다. 배열을 정렬한 후 이진 탐색을 진행하면 된다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int N; cin>>N; int A[N]; for(int i=0; i>A[i]; sort(A, A+N);..
2021.02.01 -
[백준/C++] 2805번 나무 자르기
문제: www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제풀이 이분 탐색 문제 중에서도 조건을 만족하는 값들 중 최댓값을 구하는 문제이다. (나무길이) - (벌목기 높이)의 총합 >= M 을 만족하는 벌목기 높이의 최댓값을 구해야 한다. 최댓값을 구하기 위해서 위의 조건을 만족하더라도 루프를 멈추지 않고 계속 탐색한다. 코드 #include using namespace std; int main(){ ios::sync_..
2021.01.29