[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.
[Programmers] Lv 2. 줄 서는 방법
https://school.programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr function solution(n, k) { const [arr, result, dp] = [ Array.from({ length: n }, (_, i) => i + 1), [], [1, 1, 2], ]; const factorial = (n) => { if (dp[n] !== undefined) return dp[n]; return (dp[n] = n * factorial(n - 1)); };..
2023. 3. 12.
[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.
