[Algorithm] 동적 프로그래밍 LIS 문제 (Memoization VS Tabulation)
LIS(Longest Increasing Subsequence)는 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열을 반환합니다. 부분 배열(Subsequence)는 데이터의 순서가 유지되는 모든 부분 배열을 의미합니다. 반면 substring 혹은 subarray는 연속된 부분 배열을 의미합니다. 예를 들어 'abc' 문자열이 주어진 경우 substring과 subsequence는 다음과 같습니다. arr='abc'; substring = 'a','b','c','ab','bc', 'abc'; subsquence = 'a','b','c','ab','ac','bc','abc'; 주어진 배열에서 subsequnce를 구하기 위해서 동적 프로그래밍(Dynamic Programming) Memoization과 T..
2022. 7. 13.
[Algorithm] 두 배열에서 k 번째 수 찾기 Javascript(getItemFromTwoSortedArrays 알고리즘)
문제 길이가 m, n이고 오름차순으로 정렬되어 있는 두개의 배열이 주어진다. 각 배열은 자연수로 이루어져 있고, 두 배열을 합친 전체 배열에서 k 번째 요소를 출력한다. 입력 자연수를 요소로 가지는 배열 arr1 arr1.length는 m 자연수를 요소로 가지는 배열 arr2 arr2.length는 n k number 타입의 0 이상 정수 출력 nubmer 타입 주의사항 두 배열의 합은 1,000,000 이하 입출력 예시 let arr1 = [1, 4, 8, 10]; let arr2 = [2, 3, 5, 9]; let result = getItemFromTwoSortedArrays(arr1, arr2, 6); console.log(result); // --> 8 arr1 = [1, 1, 2, 10]; a..
2022. 6. 18.
