본문 바로가기

이진 탐색(이분 탐색)7

[Baekjoon] 17179번: 케이크 자르기 https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 문제 해결 과정 착안 자르고자 하는 케이크 조각 수를 만족하기 위해 자연수 1부터 $L$까지의 길이 중 가능한 길이의 최댓값을 이진 탐색(binary search, 이분 탐색)을 응용하여 구한다. 구현 편의상 시작 탐색 구간의 우측 끝값을 불가능한 길이인 $L+1$로 설정하여 탐색을 시작하고 아래 코드와 같이 탐색 알고리즘을 구현하였다. [스포 주의].. 2023. 8. 14.
[Baekjoon] 11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 과정 착안 이번 포스트에서 다루는 문제는 최장증가부분수열(longest incresing subsequence, LIS)을 구하는 문제인데, 이 문제는 다음과 같은 점들을 고려하여 효율적으로 해결할 수 있다. $n$ 개의 항으로 이루어진 수열 $\{a_i\} \space (1 \leq i \leq n)$에 대.. 2023. 7. 15.
[Baekjoon] 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 문제 해결 과정 착안 공유기를 설치했을 때 가장 인접한 두 공유기 사이의 거리의 최댓값을 찾기 위해, 이진 탐색(binary search, 이분 탐색)을 응용하여 문제를 해결하고자 하였다. 구현 입력받은 $N$ 개의 집 좌표를 배열 Houses[]에 저장하여 오름차순으로 정렬하면, 가장 인접한 두 공유기 사이의 거리를 $c$ 라고 했을 때 설치하.. 2023. 7. 12.
[Baekjoon] 2805번: 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 해결 과정 착안 이전 포스트에서의 방법과 동일하게, 이진 탐색(binary search, 이분 탐색) 알고리즘을 응용하여 해결하고자 했다. 구현 직전의 포스트에서와 거의 유사한 문제이므로 구체적인 구현 내용은 생략하였다. 문제에서 주의할 점은 역시 정수 오버플로(integer overflow)를 염두에 두어 변수의 자료형을 사용해야 한다는 점과, 이진 .. 2023. 6. 27.
[Baekjoon] 1654번: 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 해결 과정 착안 캠프에서 사용할 랜선을 만들기 위해 목표로 하는 $N$ 개 이상의 랜선을 얻으면서, 가능한 최대의 랜선 길이를 구해야하므로 주어진 랜선 길이를 여러 번 잘라보며 최대 길이를 구해야 한다. 이때, 목표로 하는 $N$ 개 이상의 랜선을 만들기 위해 가장 작은 길이인 1부터 시작하여 랜선을 잘라 계산을 하다보면 주어지는 입력 값이 어떤지에 따라 랜선 길.. 2023. 6. 27.
[Baekjoon] 10816번: 숫자 카드 2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 문제 해결 과정 착안 (최초 접근 방법) STL의 헤더에 포함된 std::unordered_map 클래스를 활용하여 입력되는 숫자를 키, 반복되는 개수를 값으로 가지도록 구현하고자 하였다(기본 오버로딩 되어있는 [] 연산자 활용). (다른 접근 방법) 이전에 다른 문제들을 풀어보는 동안 숫자형 키 값을 사용할 때 std::unordered_map 클래스를 사용하.. 2023. 6. 25.

티스토리툴바