Algorithm/[Binary Search] (11) 썸네일형 리스트형 BOJ1654 BOJ2805 BOJ1920 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 [Binary Search] 백준 - 10816 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 숫자 카드에 대한 풀이 이다. 이 문제는 기존의 이분탐색 문제와 조금 다른 부분이 있다. 기존에는 값의 범위나, 배열의 범위를 통해서 단일의 값이나 정답을 구하는 문제였지만, 이 문제의 경우에는 한 배열에서 해당과 같은 값의 수를 구하는 것이다. 배열의 탐색, 정렬에 대한 특성 중 하나를 기억 해두자 그것은 바로, 정렬된 배열에서는 자신의 값과 유사하거나 같은 값.. [Binary Search] 백준 1764번 풀이 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 단순히, 두개의 배열에 모두 속하는 교집합 원소들을 뽑는 과정이다. hashset을 사용하여, 중복처리에 대한 이슈를 회피해주고 최종 적으로 contains으로 값을 잡아가 주면된다. [Binary Search] 백준 1920 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 이건 단순한 이분탐색이다. [Binary Search] 백준 2110 풀이 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 공유기 설치 문제이다. 이전에 풀었던 레슨 문제와 유사하다. 범위를 구하고 이분탐색을 하면 끝이다. 말하면, 각각의 리스트들을 합하듯이, 앞에서 뒤의 집을 빼주면서 체크를 하고, 이분탐색의 mid 값보다 크다면, cnt를 증가, 반복문이 다돌면, answer보다 큰지 작은지 체크해서, 답에 update해주면 된다. [Binary Search]백준-2343 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 쉽게 생각할수 있는 이분탐색 풀이이다. 이분탐색의 유형은 크게 두가지 풀이이다. 특정 배열이 있고, 해당 배열 내에서, 이분탐색으로 중간값을 구해서 값을 탐색하는 방법이 있고 특정 조건에 대한 리스트들을 생각해서, 만든뒤에 해당 조건들의 범위에서 이분탐색을 하는 경우가 있다. 해당 문제는 두번째 케이스이다. 각 레슨의 길이를 생각해서 최대의 길이를 계산, 그리고 cnt 를 증가 시키면서 세는 방법이다. .. 이전 1 2 다음 목록 더보기
