Mason

이중 연결 리스트 단일 연결 리스트와 마찬가지로 head와 tail을 가지며 인덱스가 없어 인덱스를 이용한 무작위 접근을 할수 없다. class Node { constructor(val) { this.val = val; this.prev = null; this.next = null; } } class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } } 위의 클래스를 보면 단일 연결 리스트와 비슷하지만 하나 다른점은 각 노드들이 자신의 앞의 노드를 가르키는 포인터를 하나씩 더 갖으며 이로인해서 특정 작업에 관해서는 시간복잡도의 효율이 좋아지지만 공간복잡도의 효율이 나빠진다. 단일 연결 리스트의 ..

단일 연결 리스트 위와 같은 구조이며 문자열, 숫자 등 무엇이던 원하는 데이터를 저장하는 자료구조중 하나이다. 배열처럼 순서에 따라 다수의 데이터를 저장하지만 인덱스없이 객체들이 연속으로 연결되있는 구조이다. 예를 들어 다섯번째 아이템에 접근하다고 가정햇을때 배열의 경우 인덱스를 이용하여 접근 할수 있지만 이경우에는 첫번째, 두번째, 세번째, 네번째 아이템들을 순차대로 거처야 다섯번째 아이템에 접근할수 있다. class Node { constructor(val) { this.val = val; this.next = null; } } class SinglyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } }..

Radix Sort 다른 정렬 알고리즘들과 달리 비교 작업을 수행하지 않는 정렬 알고리즘이며 숫자형 데이터만을 정렬할때 사용한다. 문자열이나 이미지 데이터를 가저와 이진형태로 변환후 정렬이 가능하지만 정렬할때의 실제 데이터는 숫자여야만한다. 정렬하려는 배열을 받은후 10개(10진수)의 버킷을 만든다. 받은 숫자형 데이터들의 첫번째 자릿수를 해당되는 버킷에 배치시킨후 버킷의 순서대로 배열을 재배치 시킨다. 이후 재배치된 데이터들의 두번째 자릿수를 이용하여 동일한 작업을 진행하며 반복적으로 작업을 수행하며 필요에 따라 반복적으로 계속해서 진행된다. 몇개의 보조 함수들이 필요하며 배열의 가장 큰수를 구하고 그수가 가진 자릿수를 구하며 데이터의 특정 자릿수에대한 값을 구하는 함수들이 필요하다. 최대 자릿수 알아..

Quick Sort 재귀를 이용하여 배열이 1개의 아이템이 남을때까지 분할 시키며 Pivot포인트를 지정하여 정렬한다. Pivot 정렬 함수를 만들어 정렬을 실행할 아이템을 Pivot 포인트로 지정한다. 이후 배열의 아이템들을 순차적으로 Pivot과 비교하며 Pivot보다 낮은 아이템들은 배열의 왼편으로 이동시킨다. 배열의 모든 아이템들의 비교가 끝이나면 이동시킨 아이템들중 맨 오른쪽의 아이템과 Pivot의 위치를 교환한다. 이후 Pivot의 위치는 확정이 되며 Pivot을 기준으로 배열의 왼쪽 아이템들과 오른쪽 아이템들을 반복하여 진행한다. Pivot 함수 function pivot(arr, start = 0, end = arr.length - 1) { let pivotIndex = start; let..

Merge Sort 분할, 정렬, 합병 3가지의 단계로 이루어진 알고리즘으로 배열의 아이템이 0개 혹은 1개일경우 어떠한 값이 오든 배열은 정렬된 상태인것을 이용하는 방식이다. 전체 배열을 0 혹은 1개의 아이템이 남을때까지 계속해서 2분할 한후 1개의 아이템을 가진 배열 2쌍씩 비교하여 정렬후 합병하며 전체 배열이 정렬될때까지 계속해서 비교후 정렬, 합병을 반복한다. 병합 함수 Merge Sort의 마지막단계인 정렬과 합병을 수행할 함수를 먼저 만들어 준다. function merge(arr1, arr2) { let result = []; let i = 0; let j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] < arr2[j]) { ..

Bubble Sort (버블 정렬) 배열의 첫 아이템을 시작으로 다음 아이템과 비교후 정렬, 이후 두번째 아이템과 그 다음 아이템을 비교후 정렬, 이렇게 순차적으로 모든 비교를 마친후 다시 배열의 첫 아이템과 다음 아이템을 비교후 정렬하며 반복적으로 이루어 진다. 버블 정렬 예시 function bubbleSort(arr) { let swapCheck; for (let i = arr.length; i > 0; i--) { swapCheck = true; for (let j = 0; j arr[j + 1]) { let tem = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tem; swapCheck = false; } } i..

이번 포스트에서는 Linear, Binary, Naive string search algorithm에대해 알아 보겠다. Linear Search Algorithm(선형 검색 알고리즘) 배열에 있는 데이터를 검색할때 제일 쉬운 방법으로 배열의 맨 앞부터 차례대로 확인하는 검색 알고리즘이다. 배열이 정렬되지 않앗을경우 사용하기 좋으며 indexOf, includes, find, findIndex와 같은 함수들이 이에 해당한다. Linear search의 Big O notation 선형검색을 하면서 배열의 제일 처음오는 데이터를 찾게될경우 O(1)이 되겠지만 최악의 경우 배열의 제일 마지막 데이터를 찾게 될경우 O(n)이 되므로 최종 Big O notation은 O(n)이 된다. 예시) indexOf의 원리 ..

객체의 Big O 입력 = O(1) 삭제 = O(1) 탐색 = O(n) 읽기 = O(1) let person = { name: "Mason", age: 30, isKorean: true, hobbies: ["book", "music", "swimming"], }; 위와 같은 객체에서 입력, 삭제, 읽기와 같은 작업들은 해당 key를 이용하여 접근하기 때문에 O(1)의 시간복잡도를 가지고있다. 하지만 탐색의 경우 O(n)의 시간복잡도를 가지고 있으며 이는 각 아이템들마다 접근하여 검색한다음 해당하는 key를 찾기때문이다. 예를 들어 true라는 value를 가지고있는 key를 찾는다고할때 순차적으로 name과 age의 value를 탐색하고 true의 값을 가진 isKorean으로 넘어와서 검색을 마치기때문..

이번 포스트에서는 어떠한 문제에 대한 여러 해결법중 제일 효율적인 해결법을 찾기 위한 방법인 Big O notation에 대해 알아보겠다. 알고리즘에따라 많은 데이터량을 다루는 것을 잘 할수도 있고 처리시간이 좀 더 걸리더라도 데이터량에 관계없이 처리속도가 일정할수도 있다. 또한 이렇게 시간이 기준이 아닌 메모리 할당, 즉 메모리 공간을 기준으로 효율을 측정할 수도 있다. 이러한 효율을 측정하는 기준이 시간복잡도 혹은 공간복잡도이며 복잡도를 표현하는 방식은 Big-O(빅-오) : 최악의 경우를 표현 Big-Ω(빅-오메가) : 최선의 경우를 표현 Big-θ(빅-세타) : 평균의 경우를 표현 이렇게 3가지가 존재한다. 위의 3가지중 대부분 Big-O notation을 사용하는데, 이는 어떠한 알고리즘의 최악..

GraphQL의 사전적 정의와 서버가동은 이전 포스트에 있습니다. (이전포스트: https://mason-lee.tistory.com/19) GraphQL을 사용하기 위해서는 기본적으로 typeDefs와 resolvers를 작성해 주어야됩니다. 기본사용 typeDefs typeDefs에서는 입력값(인자)와 출력값의 타입을 정해 놓습니다(Type Definition). import { gql } from "apollo-server"; const typeDefs = gql` type Movie { title: String! genres: String description: String } type Query { allMovies: [Movie]! } type Mutation { addMovie(title: ..