LIS

[백준] 18353번 - 병사 배치하기 (python)

문제 병사의 전투력이 내림차순이 되도록 하는 가장 긴 수열을 구한다. 문제 바로가기 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 LIS 알고리즘을 활용하면 쉽게 풀 수 있다. "증가하는" 부분 수열이 아닌, "감소하는" 부분 수열을 만들어야 하기 때문에 reverse()를 사용해 초기 전투력을 뒤집은 후에 계산했다. 이전 LIS 포스팅 [백준] 가장 긴 증가하는 부분 수열 (LIS) 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subse..

[DP] 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)은 대표적인 다이나믹 프로그래밍 문제이다. {10, 20, 10, 30, 20, 50} 과 같은 수열이 주어졌을 때, 수가 점점 증가하는 수열의 가장 긴 길이를 구한다. 1) Dynamic Programming 풀이법 - O(N^2) 파라미터 설명: n = 수열의 길이 arr = 수열을 이루는 숫자가 담긴 배열 d = arr[i]를 마지막 원소로 가질 때 LIS의 길이 d[i] 값을 1로 초기화한다. 현재 위치(i)보다 이전에 위치한 원소(j)가 작은지 확인한다. (i는 기준이 되는 인덱스, j는 i보다 작은 인덱스) arr[i] > arr[j] 이면, 현재 위치 숫자 중 d의 최댓값..