기록방

👉 문제링크 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 🔸 문제 분석 🔸 두 배열 A와 B의 부배열의 합으로 T를 만드는 경우의 수를 출력한다. 🔸 문제 풀이 🔸 부배열을 구하는 방법으로 누적합을 이용한다. 입력 배열의 원소는 최대 1,000이므로, int형으로 2개의 배열을 선언해서 2,000 x 4Byte = 8KB가 쓰인다. 배열 A와 B의 누적합을 만든 뒤, 모든 부배열의 합을 구한다. A의 부배열의 수는 A의 원소 ..

👉 문제링크 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 🔸 문제 분석 🔸 주어진 수열 A의 가장 긴 증가하는 부분 수열 (LIS)의 길이를 출력한다. 🔸 문제 풀이 🔸 n이 100만이므로 LIS의 간단한 풀이 법인 DP를 사용하면, O(n^2)으로 1조로 시간을 초과한다. LIS의 두 번째 풀이법인 이분 탐색을 이용해 O(nlogn)으로 풀이한다. (600만) LIS 배열을 입력 배열 원소를 하나씩 골라 채워간다. 입력 배열의 원소를 채울 자리는 이분 탐색으로 구한다. 🔸 코드 🔸 import java.i..

최장 증가 부분 수열(LIS: Longest Increasing Subsequence)은 원소 n개의 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열을 말한다. ex) 수열 A = {10, 20, 10, 30, 20, 50} 의 경우 LIS = {10, 20, 30, 50} 이고, 길이는 4이다. LIS의 풀이 알고리즘은 대표적으로 DP와 이분 탐색이 있다. DP를 활용한 LIS 구현dp[ i ] = max( dp[ i ] , dp[ i - 1] + 1 )dp 배열에 각 인덱스의 원소를 포함 한 LIS의 최대 길이를 저장한다.(현재 인덱스의 앞쪽 dp 배열을 확인해 최대값 + 1. 혹은 현재 dp 배열 값 중 큰 것을 저장한다.)..

👉 문제링크 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🔸 문제 분석 🔸 N x N 인 배열 A가 있고, A[i][j] = ixj 이다. 일차원 배열 B에 A를 넣고 오름차순 정렬했을 때, B[k]를 구한다. 배열 인덱스는 1부터 시작한다. 🔸 문제 풀이 🔸 배열 A의 원소들 중 중앙값 보다 작은 수들의 개수를 세며 이진 탐색을 통해 풀이한다. 중앙값 보다 작은 수들이 K보다 작다면, 시작 인덱스를 중앙값 +1 로 변경한다. 중앙값보다 작은 수들이 K이상이라면, 마지막 인덱..

👉 문제링크 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 🔸 문제 분석 🔸 N개의 영상을 M개의 블루레이에 나눠 저장하려고 한다. 하나의 블루레이 크기의 최소값을 구한다. 🔸 문제 풀이 🔸 블루레이 크기를 이진 탐색으로 찾는다. 최소 크기는 N개의 영상 중 최대값 최대 크기는 N개의 영상의 총합 중앙값을 시작으로 M개의 블루레이에 모두 저장할 수 있으면 크기를 줄여보고, 모두 저장할 수 없으면 저장 크기를 늘려보는 식으로 탐색한다. 🔸 코드 🔸 import java.io.*; import java.util.Str..