# LIS
총 112개의 포스트
Leetcode - 673. Number of Longest Increasing Subsequence
주어진 배열에서 가장 긴 subsequence 즉 LIS의 갯수를 구하라.우선 LIS 길이를 구한 뒤, 배열을 backtracking을 통해 순회하면서 LIS길이를 만나면 총 갯수를 카운트 한다. 답은 맞지만 TLE가 발생한다. DP로 풀이하는 방법: memoizati
2023년 2월 27일
·
0개의 댓글·
0Leetcode - 334. Increasing Triplet Subsequence
주어진 배열에서 아래 조건을 만족하는 세개의 값이 존재하면 true리턴i < j < k and nums\[i] < nums\[j] < nums\[k]LIS 문제의 풀이방법으로 해결 (https://velog.io/@soopsaram/Lee
2023년 2월 21일
·
0개의 댓글·
0백준 14003 가장 긴 증가하는 부분 수열 5
백준 14003 <-클릭LIS알고리즘을 사용하여 최장 증가 수열을 구하는 문제이다. 1부터 5까지 있는데 5부터 풀어봤다. 1~4를 모두 확인한 것은 아니지만 기본적으로 같은 문제이고, 대신 테스트케이스의 조건이 달랐다. 해당 문제를 dp로 풀게되면 $$O$$($
2023년 2월 19일
·
0개의 댓글·
0[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 4
dp - 최대 부분 증가수열(LIS)
2023년 2월 13일
·
0개의 댓글·
0LIS Algorithm
알고리즘 문제를 풀다가 개념이 명확히 정립되어 있지 않아 공부를 했다. Longest Increasing Subsequence, 말 그대로 수열 중에서 증가하는 부분이 얼마나 긴지를 구하는데 사용하는 알고리즘이다. 주의할 점은 연속적이지 않아도 된다는 점이다. [10,20,10,30,20,50] 에서 LIS는 [10,20,30,50]이다. 공통 변...
2023년 2월 10일
·
1개의 댓글·
1