[Algorithm] 최장 증가 수열 (LIS. Longest Increasing Sequence)
LIS (Longest Increasing Sebsequence) 최장 증가수열 문제는 어떤 배열에서 특정 부분을 지워 만들 수 있는 증가 부분수열 중 가장 긴 수열을 구하는 문제다. 배열이 [1, 4, 4, 6, 8, 3]이면 증가부분수열은 [1, 4, 6, 8], [4, 6, 8], [4, 8], [6, 8]이다. 여기서 가장 긴 증가 부분수열은 [1, 4, 6, 8]이다.가장 쉬운 방법은 모든 증가부분수열을 구해 가장 긴 것을 찾는 것이지만, 같은 연산을 반복하기 때문에 O(2^n)의 시간복잡도를 가진다. 이 문제를 효율적으로 해결하는 두 가지 방법이 있다. Ex) 배열 (1, 5, 4, 2, 3, 8, 6, 7, 9, 3, 4, 5) 에서 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열..
2023. 3. 13.
[Algorithm] 선형 탐색, 분할 정복, 이진 탐색(Binary Search)
선형 탐색, 순차 탐색 (Linear Search, Sequential Search) 정렬된 배열 안에서 특정 원소를 찾기 위해 인덱스 0부터 차례로 탐색 원소를 건너뛰는 일 없이 순차적으로 탐색 선형 탐색을 이용해 O(n)의 시간복잡도로 구현할 수 있다. const arr = [1, 2, 3, 4, 5, 6]; const linearSearch = (sortedIntArray, value) => { for (let i = 0; i < arr.length; i++){ if (arr[i] === value) return i; } return -1; } console.log(linearSearch(arr, 3)); // 2 console.log(linearSearch(arr, 5)); // 4 console..
2023. 3. 9.
