어흥

문제 링크: www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용하는 LIS 알고리즘에 대해 알고 있어야 한다 - DP[] 배열을 TC마다 초기화한다 2. 구현 - 입력 받는 수들을 Arr[] 배열에 저장하면서 DP[] 배열을 전부 0으로 초기화한다 - DP[0] = Arr[0]과 idx=0을 초기화한다 - i: 1~Num-1까지 Arr[]에 있는 모든 수들에 대해 Arr[i]의 값이 DP[idx]보다 크다면 DP[++idx]..

문제 링크: www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 1. 주의할 점 - 일반적으로 알고 있는 LIS의 공식은 길이를 구하는 것으로, 실제 LIS를 구하는 것은 추가 작업이 필요하다 2. 구현 - 모든 수를 Info 구조체 형태의 Vector로 입력 받고, 첫 번째 인자를 기준으로 오름차순 정렬한다 - DP[] 배열을 통해 LIS의 간략한 형태를 구하고, Pos[] 배열을 통해 추가 또는 수정된 원소가 몇 번째 DP 원소와 바뀌었는지 저장한다 - ..

문제 링크: www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 1. 주의할 점 - LIS(가장 증가하는 부분수열)에 대해 알고 있어야 한다 2. 구현 - 모든 수에 대한 입력을 Arr[] 배열에 받는다 - DP[idx] 배열 통해 가장 긴 증가하는 부분 수열을 나타낼 때, idx번째로 작은 수를 DP[idx]에 저장한다 - 만약 새로 비교하는 값(Arr[i])가 DP[] 배열의 가장 마지막 원소(DP[idx])보다 크면, DP배열에 새로 추가한다..

문제 링크: www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 1. 주의할 점 - LIS 알고리즘에 대해 알고 있어야 한다 - 이분탐색을 통한 LIS를 수행한다 2. 구현 - 모든 수를 Arr[] 배열에 담는다 - DP[idx] 배열에 가장 긴 증가하는 부분수열 중에서 idx번째에 위치한 수를 저장한다 - DP[0] = Arr[0]을 담은 후, 1번째 index부터 탐색을 시작한다 - 만약 DP[Idx]보다 Arr[i]가 크다면, 가장 긴 ..

문제 링크: https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 주의할 점 - Arr[] 배열을 Long Long 타입으로 받는다 - DP[] 배열에 가장 긴 증가하는 부분 수열이 저장되어 있는 것이 아니다 2. 구현 - 모든 수를 Arr[]배열에 입력받고, Dp[0]=Arr[0], Idx=0, Ans[0].idx=0, Ans[0].val=Arr[0]으로 초기화 하고 시작한다 - For문을 1~Num-1까지 돌리..

문제 링크: https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용하는 LIS에 대해 알고 있어야 한다. - 가장 긴 증가하는 부분 수열 2와 풀이 방법은 같다. 다른점은 모든 변수를 Int가 아닌 Long Long으로 받아들인다. 풀이 방법: https://imnotabear.tistory.com/183 [백준 12015] 가장 긴 증가하는 부분 수열 2 (C++) 문제 링크: htt..

문제 링크: 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 1. 주의할 점 - 직전의 게시물과 같이 N^2의 시간복잡도를 지니는 방법으로는 TLE가 난다 - 이분탐색을 사용하여 NlgN의 시간복잡도를 지니게 한다 2. 구현 - 모든 배열에 대한 정보를 Arr[] 배열에 저장하고 Dp[0]= Arr[0], idx=0으로 초기화한다 - i: 1~Num-1까지 For문을 수행하며, Dp[idx]< Arr[i]인 경우, 무조건 추가한다 - 이외의 경..