본문 바로가기
반응형

이분탐색6

[백준] 2343번 - 기타 레슨 (Java) https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 강의 순서가 바뀌면 안된다는 것은 입력 받은 순서대로 디스크에 배치되어야 한다는 것이다. 2. 최소 디스크의 갯수는 M개로 정해져있다. 한 디스크의 최소 용량을 구해야 한다. 1) 완전탐색(DFS) 완전탐색으로 각 디스크에 곡들을 저장해서 그 중 최소값을 구하자. 각 디스크에 저장하는 곡의 수는 for문으로 정해야 하나? DFS로 구현을 하면 어떻게 할 수 있을까? 각 디스크에 저장하는 곡의 수가 .. 2022. 11. 7.
[백준] 17179번 - 케이크 자르기 (Java) https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net N : 자르는 횟수 ( 2022. 10. 7.
[백준] 1654번 - 랜선 자르기 (Java)(○) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net K개의 길이가 다른 랜선을 가지고 있다. 이를 잘라서 같은 길이의 N개의 랜선을 만들어야 한다. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. ( 2022. 10. 6.
[백준] 2805번 - 나무 자르기 (Java) https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 나무를 자르는데 총 N개의 나무를 높이 H로 잘라서 남은 길이의 합이 M이상이 되는 H의 최대값을 구하라. - N : 나무의 수 ( 1 2022. 10. 5.
이분탐색 알고리즘(Upper Bound, Lower Bound) 오름차순으로 정렬된 배열에서 찾고자 하는 값 key가 있을 때, Upper Bound는 key보다 큰 첫번째 위치(초과)를 반환한다. Lower Bound는 key보다 크거나 같은 첫번째 위치(이상)블 반환한다. 예) 배열 {1, 3, 3, 5, 7}이 있을 때, key = 3이면 Upper Bound = 3(인덱스), Lower Bound = 1(인덱스)가 된다. key = 2이면 Upper Bound = 1(인덱스), Lower Bound = 1(인덱스)가 된다. lower bound, 하한은 찾고자 하는 값 '이상'의 값이 처음으로 나타나는 위치를 의미한다. 즉, 왼쪽부터 볼 때 찾고자 하는 값이 같거나 큰 경우를 처음 만나는 위치를 의미한다. key 값이 4일 때 처음 마주하는 키 값 이상을 갖고.. 2022. 9. 22.
[백준] 1920번 - 수 찾기 (Java)(○) 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 선형탐색으로 풀면 시간초과가 발생한다. 이분탐색으로 풀어보자. 1. N개의 수를 입력받아서 오름차순으로 정렬을 해야 한다. 2. M의 수를 하나씩 이분탐색으로 찾아보자. import java.util.*; import java.io.*; /* [백준] 1920번 - 수 찾기 (Java) */ public class Main { static int N.. 2022. 9. 22.
반응형