알고리즘 (JS)

[sort] 배열에서 숫자, 문자열 정렬하기

sort 함수 사용하는 경우 '정렬'과 관련된 문제를 풀 때 1. sort() 함수 사용 금지 2. N의 케이스가 100만 초과 (sort 메서드의 시간 복잡도는 O(NlogN) 이므로) 인 경우를 제외하고는 sort 함수를 사용하여 문제를 해결할 수 있다. 기본 sort 함수는 하나만 기억하면 된다. 어떤 함수를 a, b값을 받아 실행 시켰을 때 값이 음수가 나오면 a가 먼저 b가 나중 값이 양수가 나오면 b가 먼저 a가 나중 값이 0이 나오면 순서를 바꾸지 않음 숫자에 적용 const arr = [1, 5, 3, 2, 7, 10] arr.sort((a, b) => { return a - b }) 만약 첫번째로 1, 5를 매개 변수로 받아서 실행하면 1 - 5 = -4 로 음수가 나온다. 그래서 음수가..

2024. 1. 9. 22:30

알고리즘 (JS)

[데이터구조] Linked List

Linked List (연결 리스트) 개요 일련의 노드가 연결된 데이터 구조로, 각 노드는 데이터 값과 다음 노드를 가르키는 포인터로 구성된다. 그래서 다음 노드라는 것은 메모리 안 구조를 따라 가는 것이 아니라 포인터에 의해서 연결이 된다. 가장 마지막 노드는 다음 노드로 null 을 가르켜서 마지막임을 나타낸다. 장점 전체 데이터 구조를 재할당하거나 재구조화 하는 것 없이 리스트의 요소를 쉽게 삽입 혹은 삭제할 수 있다. 단점 요소에 랜덤하게 접근하는 것이 쉽지 않다. 요소에 접근하려면 O(n)의 시간 복잡도를 갖는다. 동작 - 삽입: 처음, 끝 혹은 주어진 인덱스에 요소를 추가한다. - 삭제: 인덱스 혹은 값을 받아서 해당 요소를 삭제한다. - 검색: 값을 통해서 요소를 찾는다. 사용 스택과 큐는 ..

2023. 12. 11. 22:45

알고리즘 (JS)

[데이터구조] Stack / Queue

Stack 순서가 있는 요소의 모음으로, LIFO(Last In First Out) 의 법칙을 따른다. 가장 나중에 들어온 요소가 끝에 붙고 가장 첫번째로 나가게 (삭제되게) 된다. 접시 쌓기와 같다고 생각하면 된다. 가장 위에 놓여있는 접시를 가장 처음으로 사용하게 된다. 스택은 수학적 모델이 아니라 행동으로 정의되는 추상적인 데이터 타입이다. 두 가지 동작을 하는데 - push : 컬렉션에 요소를 추가한다. - pop : 컬렉션에 가장 마지막으로 추가 된 요소를 삭제한다. 스택을 사용할 수 있는 예시 상황 - 브라우저 히스토리 추적 - 타이핑을 취소할 때 - 자바스크립트 런타임에서의 콜스택 Queue FIFO (First In First Out) 법칙을 따르는 컬렉션이다. 먼저 추가된 요소가 가장 먼..

2023. 12. 1. 18:44

알고리즘 (JS)

[데이터구조] 배열 / 객체 / Set / Map

일반적으로 사용하는 데이터 구조와 그에 대한 메서드의 시간 복잡도를 알아보자 Array (배열) const arr = [1, 2, 3, 'string'] 값들을 저장할 수 있는 데이터 구조로, 같은 하나의 배열 안에 다양한 타입을 포함할 수 있다. 생성하기 전에 크기를 지정할 필요없이 사이즈 변경이 가능하다. 인덱스는 0에서부터 시작하고 삽입한 순서대로 유지된다. 배열은 반복이 가능하기 때문에 for 문 안에서 사용할 수 있다. 배열의 끝에 삽입을 하거나 배열의 끝에서 삭제할 경우: O(1) 배열의 처음에 삽입 혹은 처음에서 삭제할 경우: O(N) 인덱스로 요소에 접근하는 경우: O(1) 검색하는 경우: O(n) 따라서 자주 사용하는 메서드를 분류해 보자면, push, pop: O(1) shift, un..

2023. 12. 1. 17:42

알고리즘 (JS)

The Other Algorithms

Cartesian product 두 개의 set에서 각 요소의 곱을 나타내는 방법이다. 예를 들어, A = [1, 2] / B = [3, 4] 가 있다면 AxB = [[1, 3], [1, 4], [2, 3], [2, 4]] 이런 식으로 나타내게 된다. function cartesian(arr1, arr2) { const result = []; for (let i = 0; i < arr1.length; i++) { for (let j = 0; j < arr2.length; j++) { result.push([arr1[i], arr2[j]]) } } return result } 이렇게 되면 Big O는 O(mn)가 된다. arr1과 arr2의 길이가 다르기 때문에 그걸 곱한 게 새로운 배열의 길이가 되고 O..

2023. 11. 22. 17:31

알고리즘 (JS)

Sorting Algorithms

Bubble Sort 실제로는 많이 쓰이지 않지만 기본적으로 알고 있어야 하는 방법이다. 근접한 요소끼리 비교해서 내가 원하는 순서대로 정렬하는 것을 반복하고 만약 요소들이 순서가 변경되지 않았다면 제대로 정렬이 된거니까 완료한다. function bubbleSort(arr) { let swapped = do { swapped = false for(let i = 0; i arr[i+1]) { let temp = arr[i] arr[i] = arr[i+1] arr[i+1] = temp swapped = true } } } while(swapped) } Big O : O(n^2) Insertion Sort 정렬이 된 배열과 정렬이 되지 않은 배열이..

2023. 11. 22. 16:40