최장 증가 수열 (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번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부
karla.tistory.com
2.가장 긴 증가하는 부분 수열 2 (1 ≤ N ≤ 1,000,000)
가장 긴 증가하는 부분수열 길이 구하기, 이분탐색
[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)
12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS Longest Increasing
karla.tistory.com
3. 가장 긴 증가하는 부분 수열 5 (1 ≤ N ≤ 1,000,000)
가장 긴 증가하는 부분수열과 그 길이 구하기, 이분탐색
[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 분석
karla.tistory.com
4. 줄 세우기 (1 ≤ N ≤ 200)
[2631] 줄 세우기 (2중 for문)
2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과
karla.tistory.com
[2631] 줄 세우기 (최장증가수열, LIS, 이분 탐색)
2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과
karla.tistory.com
5. 줄세우기 (1 ≤ N ≤ 1,000,000)
연속최장증가수열
[7570] 줄세우기 (연속 최장 증가 수열, LIS)
7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사
karla.tistory.com