Chadoll

최장 증가 부분 수열(Longest Increasing Subsequence)이란? 원소개 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 간단히 말해, 가장 긴 증가하는 부분 수열이다. 예시 [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열에서 최장 증가 부분 수열(LIS)은 [2, 5, 7, 8]이 된다. [2, 5, 7], [2, 4, 8] 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 [2, 5, 7, 8]이다. 최장 증가 부분 수열 알고리즘 풀이 방법 최장 증가 부분 수열의 길이를 구할 수 있는 풀이 방법은 크게 2가지가 있다. 동적계획법 (DP, Dyna..

이진 탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이며, 이분 탐색이라고도 불린다. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이진 탐색 (이분 탐색) 알고리즘 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 시작점, 끝점, 중간점(start, end, mid) 변수 3개를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데..