# LIS
[이.취.코.테>DP>기출문제] 병사 배치하기
N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치
[JavaScript] 300. Longest Increasing Subsequence
숫자들을 순회하면서, 해당값까지 가능한 LIS길이를 dp어레이에 저장한다.해당 인덱스 이전값을 순회하면서 가장 긴 값을 찾아 1 증가시켜준다. 나보다 작은값이 없어서 LIS갱신이 불가능한 경우에도 "나 자신"으로 이루어진 길이1짜리 LIS가 존재하므로 max초기값 0에
[JavaScript] 673. Number of Longest Increasing Subsequence
DP에는 해당인덱스를 포함한 LIS 길이를 저장하고,count에는 그 LIS와 같은 길이의 LIS가 몇개가 있는지 저장한다.max에는 가장 긴 LIS 길이를 저장하고, 이 LIS길이를 가지고 있는 인덱스의 count의 총합이 정답이 된다.count의 총 합을 정답으로
[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 5 / 14003
문제문제 링크접근 방식이분 탐색을 이용하여 LIS 문제를 푸는 과정에서 숫자 배열(arr)의 수가 LIS 배열에 들어가는 인덱스를 rec 배열에 저장한다.그 후 rec 배열의 뒤에서 부터 시작하여 3, 2, 1, 0을 선택하면 가장 긴 증가하는 부분수열의 원소를 구할
[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 3 / 12738
문제문제 링크접근 방식수열의 크기가 1,000,000 이므로 dp로 풀면 O(n^2) 이기 때문에 시간 초과가 난다.따라서 이분 탐색으로 풀어야 한다. 코드
[알고리즘 개념] 최장 증가 부분 수열 (LIS)
Longest Increasing Subsequence최장 증가 부분 수열→ 어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제Brute-force 접근방법 수열의 모든 부분집합을 구하
[알고리즘/백준] 11053번 : 가장 긴 증가하는 부분 수열(python)
이건 set형으로 중복 없애고 풀어보기도 하고 다 해봤는데 계속 틀렸다고 나와서 답을 봤다... LIS를 사용해야 한다고 한다. 새로 하나 배웠다.
Algorithm - LIS 알고리즘
동적 계획법으로 풀 수 있는 유명한 알고리즘 문제 중 하나인 '최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)' 문제와 알고리즘에 관한 소개
백준 12015 가장 긴 증가하는 부분 수열 2
백준 12015최장 증가 부분 수열 (LIS,Longest Increasing Subsequence)의 알고리즘은 두개가 있는데, 하나는 dp를 이용하는 방법이고 하나는 이분탐색을 이용하는 방법이다. n이 매우 클 때, 시간 복잡도를 개선하기 위해 후자의 방법을 사용하
[알고스팟] JLIS
JLIS기존 LIS 문제와 같은 방식으로 풀 수 있다.일단 A 수열에서 LIS, B 수열에서 LIS를 뽑으면 안 된다.A에서 적게 뽑고 (LIS가 아닌 증가 부분 수열)B에서 LIS를 뽑아도 그것은 답이 될 수 있다.애초에 LIS의 길이가 몇인지 모르니A에서 몇을, B
[알고스팟] Longest Increasing Sequence
Longest Increasing Sequence 다이나믹 프로그래밍 다이나믹 프로그래밍 (= 동적 계획법)은 완전탐색에서 기인한다. 대부분 문제를 보면 '어떤 것들을 선택해야 최적의 경우일까?'로 설명될 수 있다. 동적 계획법은 메모이제이션을 통해 반복적인 연산
