본문 바로가기

JavaScript/Algorithm

 (13)
[leetcode] 35. Search Insert Position - array https://leetcode.com/problems/search-insert-position/description/ 고유 정수의 정렬된 배열과 목표값이 주어졌을 때, 목표값이 발견되면 인덱스를 반환합니다. 그렇지 않은 경우 순서대로 삽입했을 때 인덱스가 있을 위치를 반환합니다. 런타임 복잡도가 O(log n)인 알고리즘을 작성해야 합니다. Example 1:Input: nums = [1,3,5,6], target = 5Output: 2  Example 2:Input: nums = [1,3,5,6], target = 2Output: 1  Example 3:Input: nums = [1,3,5,6], target = 7Output: 4  일단 돌아가게 만들었지만... 시간 복잡도 때문에 리팩토링 해야한다...
[Algorithm] 완전 탐색(Exhaustive search)과 브루트 포스(Brute Force) 완전탐색(Exhaustive search)과 브루트포스(Brute Force) 알고리즘은 모든 가능한 경우의 수를 탐색하여 문제를 해결하는 방법입니다1. 완전탐색 (Exhaustive search)완전탐색은 모든 경우의 수를 다 만들어 보는 방법입니다.이 방법은 컴퓨터의 빠른 계산 능력을 이용하여 가능한 모든 경우를 일일이 나열하면서 답을 찾습니다 2. 완전 탐색의 종류완전 탐색은 문제의 구조에 따라 다양한 방법으로 구현될 수 있습니다.브루트 포스 (Brute Force): 반복문과 조건문을 사용하여 가능한 모든 경우를 단순하게 탐색합니다.비트 마스크 (Bit Mask): 이진수를 사용하여 문제에서 나올 수 있는 모든 경우의 수를 표현하고 탐색합니다.백트래킹 (Backtracking): 답을 찾는 과정에..
[Algorithm] 5. 이진 탐색(Binary Search) 알고리즘 흔히 for 문을 이용해 배열의 처음부터 끝까지 탐색하는 선형탐색은 O(n) 이라는 시간복잡도로 효율성이 떨어집니다.이를 보완하는 탐색 알고리즘으로 대체되는 이분탐색 (Binary Search, 이진 탐색이라고도 합니다 )은 O(log N) 의시간 복잡도를 가지고 있습니다.   주어진 범위의 절반씩 삭제하며 윈도우를 조절하며 찾아가는 기법으로주어진 배열은 순서대로 정렬이 되있어야 사용할 수 있는 알고리즘입니다. 32를 찾는 순서는 아래와 같이 절반의 범위를 줄여가며 진행됩니다   /** * 정렬된 배열에서 특정 요소의 인덱스를 찾는 이진 탐색 함수 * @param {Array} arr - 검색할 정렬된 배열 * @param {*} elem - 찾고자 하는 요소 * @returns {number} - 요소..
[Algorithm] 알고리즘 기본 패턴 4 - Devide & Conquer 4. Devide & Conquer 여기서는 간략하게 개념만 설명하고 넘어가겠습니다.분할 정복 알고리즘의 예시로는 이진 탐색 트리 그리고 정렬 알고리즘으로 넘어가면 퀵 정렬과 병합 정렬이 대표적인 예가 될 수 있습니다.이 알고리즘은 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리하며,링크드 리스트나 트리가 대상이 될 수도 있습니다.  이진 탐색 트리 를 보면 선형탐색으로 O(n) 의 시간을 들여 찾는 것 보다절반으로 나누어 찾아가면 O(log n) 로 훨씬 더 효율적으로 찾는 것을 알 수 있습니다. 이렇게 몇몇 케이스에서 분할 정복  패턴을 사용하면 더 효율적인 결과를 얻을 수 있습니다. function search(array, val) { let min = 0; let max = ar..
[Algorithm] 알고리즘 기본 패턴 3 - Sliding Window 3. Sliding Window 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용합니다. 창문을 하나 만들어야 합니다. 여기서 말하는 창문이란 개념은 주어진 데이터의 범위를 나타냅니다.그 창문을 만들고 데이터 안에서 창문을 여는 것처럼 이동을 시키며주어진 조건을 클리어하는 알고리즘 패턴입니다. 이 기법은 윈도우의 크기를 나타내는 변수와 하위 배열, 또는 다른 문자열이 주어지며,윈도우의 크기는 고정되거나 가변적인 크기가 될 수 있습니다. 조건에 따라 창문을 이동시키며, 시작 위치에서 시작하면 보통 왼쪽에서 오른쪽으로 이동합니다. 오른쪽에서 왼쪽으로 이동도 가능하고 가운데 위치에서 시작할 수도 있습니다. 그러나 보통 창문을 왼쪽, 즉, 요소..
[프로그래머스] Lv1) 숫자 짝꿍 처음에는 시간 복잡도를 생각하지 않고 무지성으로 해를 구했지만.. 시간초과ㅠ 처음 코드는function solution(X, Y) { let result = [] const num1 = Array.from(X).sort((a,b) => b-a) const num2 = Array.from(Y).sort((a,b) => b-a) num1.forEach((value, i)=> { if(num2.indexOf(value) !== -1) { let commonIdx = num2.indexOf(value) result.push(num2[commonIdx]) num2.splice(commonIdx,1) ..
[Algorithm] 알고리즘 기본 패턴 2 - Multiple Pointers (다중 포인터) 1. 개념 배열이나 문자열에서 한 쌍의 값이나 조건을 찾을 때 사용인덱스 또는 위치에 해당하는 포인터 또는 값을 생성하고 특정 조건에 따라 시작, 끝 또는 중간으로 이동합니다.공간의 복잡성을 최소화하면서 문제를 해결하는 데 매우 효율적입니다.정렬된 배열에서 사용합니다 2. 특징시간 복잡도: 대부분 O(n) 공간 복잡도: O(1) (추가 공간이 거의 필요 없음) 주로 정렬된 배열에서 사용됨 두 개의 값을 비교하거나 특정 조건을 찾을 때 효과적3. 사용하는 경우중복 값 찾기 특정 합을 가진 쌍 찾기 팰린드롬 확인 배열에서 고유한 값 개수 세기  4. 예제 1) 정렬된 배열에서 합이 0인 쌍 찾기/** * 배열에서 합이 0이 되는 두 숫자를 찾는 함수 * @param {number[]} arr - 정렬된 숫자..
[Algorithm] 알고리즘 기본 패턴 1 - Frequency Counter (빈도수 세기) 1. Frequency Counter (빈도수 세기) 배열/ 문자열의 요소들의 빈도수를 비교할 때 사용하며이 패턴은 Object 또는 Set을 사용하여 값의 값/빈도를 수집합니다중첩 루프 또는 O(N^2) 중첩 루프를 O(n)으로 최적화 해야 합니다  예 1)두 개의 배열을 인수로 받는 same이라는 함수가 있습니다. 이 함수는 배열의 모든 값이 두 번째 인수 배열에 해당하는 값의 제곱을 갖는 경우 참을 반환해야 합니다. 값의 빈도는 동일해야 합니다. same([1,2,3], [4,1,9]) // true same([1,2,3], [1,9]) // false same([1,2,1], [4,4,1]) // false  이전 사용했던 풀이법은 아래와 같습니다.const same = (arr1, arr2) =..

티스토리툴바