https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 어떻게 풀어야할지 감을 못 잡았는데 알고리즘 분류를 보고서야 이분 탐색임을 알았다. 이분 탐색의 왼쪽 값(l)은 배열의 최댓값, 오른쪽 값(r)은 배열 원소들의 총합을 기준으로 시작한다. 가운데 값(m)은 (l+r)//2로 정한다. 블루레이의 크기에 몇 개의 강의가 들어가는지 세어주는 함수를 만들어서 개수를 반환한다. 이 때 블루레이의 크기는 m을 기준으로 판단..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 2022.07.31 - [Algorithm/BOJ] - [BOJ][python] 2110. 공유기 설치 문제를 풀었던 것이 도움이 되었다. 랜선 길이를 찾기 위해서 왼쪽 값(l)은 1, 오른쪽 값(r)은 랜선 길이의 최댓값으로 초기화해주었다. N개 이상의 랜선을 가져야 하는데, 랜선의 개수는 모든 랜선을 이분탐색하며 중간 값(..
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 💡IDEA 이분 탐색을 사용하는 문제이다. 문제의 분류를 보지 않으면 이분 탐색 문제라는 것을 알기 어려운 것 같다. 그리고 이 문제는 간격의 최대값을 찾는 문제이므로, 왼쪽 값과 오른쪽 값을 초기화 할 때 조심해야 한다. 왼쪽 값(l)은 최소 간격인 1, 오른쪽 값(r)은 최대 간격인 가장 작은 좌표값과 가장 큰 좌표값의 차이이다. 이분 탐색을..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 이분 탐색이란 가장 작은 값과 가장 큰 값을 기준으로 가운데 값을 찾아 타겟값을 비교하여 좌우 변수를 조정하며 탐색하는 방법이다. 이 문제에서는 가운데 값보다 큰 높이의 나무를 잘라낸 합으로 비교하며 좌우 변수를 좁힌다. 절단기에 설정할 수 있는 최대 높이를 구하기 위해 구한 합과 타겟값을 비교하며 가장 큰 높이를 ..
