알고리즘 (6) 썸네일형 리스트형 [JS 알고리즘] 특정 범위에 해당하는 원소 개수 구하기(lowerBound,upperBound) lowerBound(arr,x) 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 왼쪽 인덱스를 반환 upperBound(arr,x) 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 오른쪽 인덱스를 반환 const lowerBound = (arr, target, start, end) => { while (start = target) end = mid; else start = mid + 1; } return end; }; const upperBound = (arr, target, start, end) => { while (start < end) { let mid = parseInt((.. [JS 알고리즘] 순차 탐색과 이진 탐색 순차 탐색이란? 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 탐색법이다. 시간복잡도는 O(N)이다. 이진탐색이란? 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 시간 복잡도는 O(log N)이다. 각 단계마다 탐색 범위를 2로 나누며, 범위가 반으로 감소하므로 로그 복잡도를 가진다. 이진 탐색을 사용할 때 좋은 점 넓은(억 단위 이상)탐색 범위에서 최적의 해를 찾아야 하는 경우 데이터를 정렬한 뒤에 다수의 쿼리를 날려야하는 경우 const binarySearch = (arr, target, start, end) => { if (start > end) return -1; let mid = parseInt(start + end / 2); if (.. [JS 알고리즘] 백준 17609 문제 회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다. 여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로.. [js 알고리즘] 백준 9009: 피보나치 문제 피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다. 하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다. 예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 .. [JS 알고리즘] 병합 정렬이란? 병합 정렬이란? - 병합 정렬의 경우에는 분할 정복 알고리즘을 사용하고 있다. - 분할 정복은 더 이상 쪼갤 수없는 크기가 될 때까지 분할해야하기 때문에 재귀함수로 구현해야한다. - 단점: 재귀함수를 사용하게 되면 함수 호출이 많이 발생되며, 오버헤드가 발생한다. 즉, 메모리를 많이 사용하게 된다. - 장점: 시간 복잡도 O(NlogN)을 보장하는 빠른 정렬 알고리즘이다. 분할 정복이란? 1. 분할(divide): 큰 문제를 작은 부분 문제(쉬운 문제)로 분할한다. 2. 정복(conquer): 작은 부분 문제를 각각 해결한다. 3. 조합(combine): 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결한다. 병합 정렬 동작 방식 => 각 부분 배열은 이미 정렬된 상태로 보며, 각 부분 배열의 첫번.. [JS알고리즘] 선택 정렬, 버블 정렬, 삽입 정렬 선택 정렬, 버블 정렬, 삽입 정렬은 시간 복잡도 O(n^2)로 비효율적인 정렬 알고리즘입니다. 선택 정렬 - 선택 정렬은 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법입니다. - 각 단계에서 가장 작은 원소를 선택하고 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체합니다. - 매 단계에서 가장 작은 것을 선택하는 데에 약 N번의 연산이 필요하다. 5 4 3 2 1 1단계: 첫 단계에서 제일 작은 수는 1입니다. 1 5 4 3 2 2단계: 그 다음 제일 작은 수는 2입니다. 1 2 5 4 3 3단계: 그 다음 제일 작은 수는 3입니다. 1 2 3 5 4 4단계: 마지막으로 제일 작은 수는 4입니다. 1 2 3 4 5 const selectSolution = (arr) =.. 이전 1 다음
