늘 겸손하게

가장 긴 증가하는 부분 수열 2 가장 긴 증가하는 부분 수열을 구하는 문제이다. 문제 풀이 가장 긴 증가하는 부분 수열을 직접 만든 뒤, 길이를 출력하면 된다. 그러면 가장 긴 증가하는 부분 수열은 어떻게 만들까? 수열 A의 첫 번째 원소부터 마지막 원소까지 참조해가면서 참조한 원소가 만들고 있던 부분 수열의 마지막 원소보다 크다면 부분 수열의 꼬리에 추가, 작거나 같다면 부분 수열에서 알맞은 위치에 덮어쓰면 된다. 여기서 알맞은 위치를 찾는데 이분 탐색 알고리즘을 적용한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 imp..

나무 자르기 매개 변수 탐색 기법을 적용하는 문제. 푸는 방법만 알면 간단하게 해결 가능합니다. 문제 풀이 1. 매개 변수 탐색을 위한 변수 설정 찾아야하는 값은 자를 나무 길이의 최대값입니다. 이 최대값을 찾는데 매개 변수 탐색 기법을 적용해야하므로 left 변수 값에는 나무를 자를 수 있는 최소 길이, right 변수에는 나무를 자를 수 있는 최대 길이를 저장합니다. 나무의 높이는 0이상 1,000,000,000 이므로 left 에는 0을 저장하고 , right 변수에는 N개 나무들의 높이 중 가장 높은 키를 저장합니다. 2. 매개 변수 탐색 이분 탐색 기법과 매우 비슷합니다. mid 값을 계산하고 mid 값이 조건에 참인지 거짓인지 판단한 후 left 값 혹은 right 값을 업데이트합니다. 값을 ..

이분 탐색이 binary search인것은 이미 알 수 있다. 그렇다면 매개 변수 탐색은 무엇일까? 매개 변수 탐색(Parametric Search )이란? 이분 탐색과 매우 유사하지만 매개 변수 탐색은 결정 문제라는 것. 결정문제라는 뜻은 구한 임의의 값이 정답인지 아닌지 판별해가며 정답을 찾아가는 문제라는 뜻입니다. 이 "임의의 값"을 매개 변수 탐색 방법에선 이분 탐색에서 해를 찾는것과 유사하게 찾아냅니다. 예시 문제 - 백준 2110 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의..

랜선 자르기 이분 탐색의 응용 버전 문제 풀이 직관적으로 떠오르는 풀이는 가지고 있는 랜선들을 나눈 몫들의 합이 K가 되는 길이를 찾기 위해 길이 1부터 가장 길이가 짧은 랜선 길이까지 반복적으로 랜선들을 나누는 풀이법이다. 정답인 길이가 M 이라면 이 풀이법의 예상 복잡도는 O(NM)이다. 문제에서 N은 1이상 1,000,000 이하의 정수라고 명시했으므로 위 풀이는 시간초과가 발생한다. 그러므로 이분 탐색으로 검색 시간을 N 에서 logN으로 줄여야한다. 이분 탐색을 어떻게 적용할까? 1. left , right 설정 이분 탐색을 위해선 인덱스값을 저장할 변수 2개가 필요하다( left, right 혹은 low, high ). 위 문제에서 요구하는 답은 길이이므로 랜선의 최소 길이인 1을 left에,..