# LIS

75개의 포스트

boj 23035

https://www.acmicpc.net/problem/23035문제를 읽어보면 가장 짧은 경로만 갈 수 있다니까 움직일 수 있는거리는 N+M이며 이는 문제에서 주어진 그림에서 상, 우 방향으로는 갈 수 없다는 소리다.이를 유의해서 관점을 살짝 바꾸면 LIS

2022년 6월 28일
·
0개의 댓글
post-thumbnail

[백준 14003] 가장 긴 증가하는 부분 수열 5

2021.07.15에 작성했던 백준 14003 문제 풀이입니다.

2022년 6월 27일
·
0개의 댓글
post-thumbnail

[PS] 백준 14003 - 가장 긴 증가하는 부분 수열 5

[PS] 백준 14003 - 가장 긴 증가하는 부분수열 5

2022년 5월 18일
·
0개의 댓글

[Algorithm] LIS (최장 증가 부분 수열)

[Algorithm] LIS (최장 증가 부분 수열)

2022년 5월 16일
·
0개의 댓글
post-thumbnail

[JavaScript] 300. Longest Increasing Subsequence

숫자들을 순회하면서, 해당값까지 가능한 LIS길이를 dp어레이에 저장한다.해당 인덱스 이전값을 순회하면서 가장 긴 값을 찾아 1 증가시켜준다. 나보다 작은값이 없어서 LIS갱신이 불가능한 경우에도 "나 자신"으로 이루어진 길이1짜리 LIS가 존재하므로 max초기값 0에

2022년 5월 7일
·
0개의 댓글
post-thumbnail

[JavaScript] 673. Number of Longest Increasing Subsequence

DP에는 해당인덱스를 포함한 LIS 길이를 저장하고,count에는 그 LIS와 같은 길이의 LIS가 몇개가 있는지 저장한다.max에는 가장 긴 LIS 길이를 저장하고, 이 LIS길이를 가지고 있는 인덱스의 count의 총합이 정답이 된다.count의 총 합을 정답으로

2022년 5월 7일
·
0개의 댓글
post-thumbnail

[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 5 / 14003

문제문제 링크접근 방식이분 탐색을 이용하여 LIS 문제를 푸는 과정에서 숫자 배열(arr)의 수가 LIS 배열에 들어가는 인덱스를 rec 배열에 저장한다.그 후 rec 배열의 뒤에서 부터 시작하여 3, 2, 1, 0을 선택하면 가장 긴 증가하는 부분수열의 원소를 구할

2022년 4월 11일
·
0개의 댓글
post-thumbnail

[알고리즘] Java / 백준 / 가장 긴 증가하는 부분 수열 3 / 12738

문제문제 링크접근 방식수열의 크기가 1,000,000 이므로 dp로 풀면 O(n^2) 이기 때문에 시간 초과가 난다.따라서 이분 탐색으로 풀어야 한다. 코드

2022년 4월 11일
·
0개의 댓글
post-thumbnail

[BOJ]2631(python)

백준 2631(줄세우기) python 풀이입니다

2022년 4월 11일
·
0개의 댓글
post-thumbnail

[알고리즘 개념] 최장 증가 부분 수열 (LIS)

Longest Increasing Subsequence최장 증가 부분 수열→ 어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제Brute-force 접근방법 수열의 모든 부분집합을 구하

2022년 4월 4일
·
0개의 댓글
post-thumbnail

[알고리즘/백준] 11053번 : 가장 긴 증가하는 부분 수열(python)

이건 set형으로 중복 없애고 풀어보기도 하고 다 해봤는데 계속 틀렸다고 나와서 답을 봤다... LIS를 사용해야 한다고 한다. 새로 하나 배웠다.

2022년 3월 22일
·
0개의 댓글

[BOJ] 2565. 전깃줄

백준 2565 전깃줄 풀이

2022년 3월 21일
·
0개의 댓글

Algorithm - LIS 알고리즘

동적 계획법으로 풀 수 있는 유명한 알고리즘 문제 중 하나인 '최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)' 문제와 알고리즘에 관한 소개

2022년 3월 12일
·
0개의 댓글

[BOJ] 11053 - 가장 긴 증가하는 부분 수열

LIS - DP / Binary Search

2022년 3월 11일
·
0개의 댓글
post-thumbnail

[PS] 백준 12015 - 가장 긴 증가하는 부분 수열 2

[PS] 백준 12015 - 가장 긴 증가하는 부분 수열 2

2022년 3월 9일
·
0개의 댓글

백준 12015 가장 긴 증가하는 부분 수열 2

백준 12015최장 증가 부분 수열 (LIS,Longest Increasing Subsequence)의 알고리즘은 두개가 있는데, 하나는 dp를 이용하는 방법이고 하나는 이분탐색을 이용하는 방법이다. n이 매우 클 때, 시간 복잡도를 개선하기 위해 후자의 방법을 사용하

2022년 3월 7일
·
0개의 댓글

[알고스팟] JLIS

JLIS기존 LIS 문제와 같은 방식으로 풀 수 있다.일단 A 수열에서 LIS, B 수열에서 LIS를 뽑으면 안 된다.A에서 적게 뽑고 (LIS가 아닌 증가 부분 수열)B에서 LIS를 뽑아도 그것은 답이 될 수 있다.애초에 LIS의 길이가 몇인지 모르니A에서 몇을, B

2022년 3월 7일
·
0개의 댓글

[알고스팟] Longest Increasing Sequence

Longest Increasing Sequence 다이나믹 프로그래밍 다이나믹 프로그래밍 (= 동적 계획법)은 완전탐색에서 기인한다. 대부분 문제를 보면 '어떤 것들을 선택해야 최적의 경우일까?'로 설명될 수 있다. 동적 계획법은 메모이제이션을 통해 반복적인 연산

2022년 3월 6일
·
0개의 댓글

14002 가장 긴 증가하는 부분 수열 4 (JAVA)

[가장 긴 증가하는 부분 수열 4] 백준, 14002

2022년 3월 5일
·
0개의 댓글