고양이 두 잔

목차 이진 탐색 [Java+Python]1920번, 수 찾기 [Java+Python]1654번, 랜선 자르기 [Java+Python]2805번, 나무 자르기 [Java+Python]2110번, 공유기 설치 [Java+Python]2805번, K번째 수 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. ($1 ≤ A_i ≤ 1,000,000$) ..

목차 이진 탐색 [Java+Python]1920번, 수 찾기 [Java+Python]1654번, 랜선 자르기 [Java+Python]2805번, 나무 자르기 [Java+Python]2110번, 공유기 설치 [Java+Python]12015번, 가장 긴 증가하는 부분 수열 2 문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 $10^5$보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min($10^9, N^2$) 보다 작거나 같은 자연수..

이분 탐색, 이진 검색, 혹은 이진 탐색 알고리즘은 정렬이 끝난 배열(리스트)에서 특정 값을 찾는 알고리즘이다. 정렬이 끝난 배열을 계속해서 반으로 나누어 탐색 범위를 좁히기 때문에 시간 복잡도는 $O(\log{N})$으로 빠르다. 말로만 설명하면 잘 와닿지 않을 수도 있으니 가장 간단한 상황 중 하나를 그림으로 그려보도록 하겠다. 위와 같이 정렬이 끝난 배열에서 7의 위치를 찾는 과정을 이분탐색으로 따라가 보자. 먼저 중간값(5)을 기준으로 7이 작은지 큰지 확인한 후 반쪽을 버린다. 이어서 다음 중간값인 8과 비교해 역시 나머지 절반을 버린다. 마지막 중간값이 7과 같으므로 탐색을 종료한다. 이처럼 매우 단순한 알고리즘이기 때문에 전공생들은 보통 1학년 초반에 배운다고 한다. 추가로 구현은 일반적으로..