알고리즘&코딩테스트/알고리즘

LIS 알고리즘 - DP(동적계획법) LIS 알고리즘 - DP(동적계획법)LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.이 문제는 기본적으로 배열에서 연속적이지 않지만, 각 숫자가yarisong.tistory.com 저번에 이어 LIS알고리즘을 이용하여 가장 갈게 증가하는 부분 수열을 찾는 알고리즘 중 이분 탐색을 이용한 방법을 알아보자 1.LIS 알고리즘-이분탐색 이분탐색의 경우 시간 복잡도는 O(nlog⁡n)을 가진다. 이분탐색을 이용하는 경우에는 실제 LIS가 아닌 LIS의 길이를 구하는데 중점을 두는  알고리즘이다.이분탐색은 배열이 정렬되었다는 특징을 이용하여 탐색 범위를 절반씩 줄..

LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 가장 길게 증가하는 부분 수열을 찾는 알고리즘이다.이 문제는 기본적으로 배열에서 연속적이지 않지만, 각 숫자가 이전의 숫자보다 커지는 수열을 찾는 문제이다.LIS 문제는 여러 방법으로 해결할 수 있지만, 대표적인 두 가지 방법은 동적 계획법(DP) 과 이분 탐색을 이용한 방법이다. 1. LIS 알고리즘 DP(동적계획법) 동적 계획법을 이용한 LIS 문제 해결은 O(n²) 시간 복잡도를 가진다. 다음과 같은 배열이 주어졌을 때 {50, 3, 20, 10, 2, 1} DP를 적용한 계산 과정을 살펴보자. 먼저 간단하게 알고리즘을 살펴보면 다음과 같다.LIS[i]: 인덱스 i까지의 수열에서 끝나는..