LIS
최장 증가 수열(LIS) 정리
최장 증가 수열 (LIS) Longest Increasing Subsequence, 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다. {6, 2, 5, 1, 7, 4, 8, 3}이라는 배열이 있을 경우, LIS는 {2, 5, 7, 8}이 됩니다. {2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 {2, 5, 7, 8} 입니다. 1. 가장 긴 증가하는 부분 수열 (1 ≤ N ≤ 1,000) 가장 긴 증가하는 부분수열 길이 구하기, 2중 for 문 DP [11053] 가장 긴 증가하는 부분수열 (LIS) 11053번: 가장 긴 증가하는 부분 수열..
[2631] 줄 세우기 (최장증가수열, LIS, 2중 for문)
2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 분석 정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌 풀이 import sys input=sys.stdin.readline n = int(input()) arr=[] for _ in range(n): arr.append(int(input())) dp = [0 for _ in range(n)] for i in range(n): dp[i] = 1 for j in range(i): if arr[j] < arr[i]: dp[i] = max(d..
[11053] 가장 긴 증가하는 부분수열 (LIS)
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 분석 1 ≤ N ≤ 1,000 1 ≤ Ai ≤ 1,000 풀이 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dp = [1]*n for i in range(1,n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i],..
최대 선 연결하기
분석 최대 부분 증가수열 분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 karla.tistory.com 풀이 """ 왼쪽의 번호와 오른쪽의 번호, 같은 번호끼리 선으로 연결 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열 오른쪽의 번호 정보가 위부터 아래 순서 서로 선이 겹치지 않고 최대 몇 개의 선 연결? 자연수 N(1
가장 높은 탑 쌓기
분석 최대 부분 증가수열 분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 karla.tistory.com 풀이 """ 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 ..
[14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색)
14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 분석 D[i] : 0~i까지 i를 포함하는 가장 길게 가하는 수열의 길이 A[i]를 i번째 수열의 값이라고 정의하면 D[k]는 A[i]>A[K]를 만족하는 최대 수열의 길이 즉, A[i]보다 작은 값을 지니고 있는 수열의 최장 증가 수열의 길이들 중 최댓값을 찾아 해당 값에 +1 한 값을 D[i]에 저장 D[i] = max({D[k]}) +1 (k=1~i-1) D 리스트를 맨 뒤에서부터 탐색해 최댓값과 동일 값을 가지는 최초 inde..