https://www.acmicpc.net/problem/2143 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net - 누적 합(Cumulative Sum) - 이분 탐색(Binary Search) 우선 두 배열의 크기가 모두 1000이기 때문에, O(N^2)의 이중for문을 통해 가능한 모든 부분배열의 합의 경우의 수를 Asumcase, Bsumcase에 저장하였다. 그 이후, O(logN)의 lower_bound, upper_bou..

https://www.acmicpc.net/problem/2467 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net - 투 포인터(Two Pointer) - 이분 탐색(Binary Search) 간단한 투 포인터 문제로 보인다. 과정은 이러하다. (1) 용액 배열의 양 끝을 초깃값으로 잡은 뒤, 서로 다가오면서(투포인터) 두 개의 합이 0에 가장 가까울 경우 저장해준다. (2) 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net - 이분 탐색(Binary Search) - 다이나믹 프로그래밍(Dynamic Programming) - 너무나도 중요한 문제이다. 가장 긴 증가하는 부분수열을 구하는 풀이법은 크게 두 가지가 있다. 첫 번째는 길이가 N인 수열을 돌면서, "현재의 숫자 앞에서 자신보다 작은 수이면서 가장 큰 부분수열을 가진 값 + 1" 을 구하는 시간복잡도 O(N^2)인 풀이법이 있다. 두 번째는 "현재의 숫자 ..

https://www.acmicpc.net/problem/1253 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net - 이분 탐색 (Binary Search) - 투 포인터 (Two Pointer) 투 포인터를 이용하여, 서로 다른 두 수를 지목했고, 이들의 합을 구했다. 시간복잡도의 경우, - N개의 숫자를 모두 순회해야 하므로 O(N) - 각각의 숫자들이 서로 다른 두 수의 합으로 구할 수 있는지를 구하는 것은 투 포인터로 구현했으므로 O(N) 따라서 O(..

https://www.acmicpc.net/problem/2110 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net - 이분 탐색(Binary Search) 이 문제를 풀기 전에 파악해야 하는 점은, 문제의 조건(가장 인접한 두 공유기 사이의 최대 거리)을 구하는 데에 있어서, "첫 번째 공유기"는 무조건 포함한다는 것이다. 또한, 우리가 Focus해야 하는 부분은 "간격"이다. (공유기의 위치가 아니다.) 예제를 예로 들어 보자. [1, 2, 4, 8, 9] 에서, 공유기 2개만 사용한다고 가정했을 때, 공유..

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net - 이분 탐색(Binary Search) - 깊이 우선 탐색(Depth First Search) 1. 30개의 물건이 있고, 이를 선택하는 경우의 수를 모두 더하는 최대 경우의 수는 이다. 따라서 O(2^N)의 시간복잡도를 가지므로 제한시간 1초인 문제에서 시간초과가 발생한다! 결국 이것을 줄일 수 있는 방법은 1. 물건들을 절반으로 분리한다.(part1 집합과 part2 집합으로 분리) 2. 각..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net - 이분 탐색 (Binary Search) 1. 국가예산의 총액은 한정되어 있고, 여러 지방의 예산 요청액은 국가 예산 총액을 넘어설 수도 있다. 그렇기에 여러 지방의 예산 요청액을 최대한 충족하는 선에서, 국가예산 총액을 최대한 써야 한다(상한가 지정). 2. 상한가 지정은 Binary Search 로 진행을 한다. 1. Binary Search 진행 시에 low, mid, high 관계를..