본문 바로가기

분류 전체보기110

Heap Sort ( 힙 정렬 ) 힙(Heap) 힙이란? 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 heap 은 우선순위 큐를 위해서 만들어진 트리자료구조이다. 힙에는 최소힙과 최대힙이 있음 heap의 특징 heap은 완전이진트리의 형태이다. 완전이진트리 설명보러가기 heap은 트리내에서 중복된 값을 허용한다. heap은 느슨한 정렬(반 정렬) 상태를 가진다. 최소힙 작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함 최대힙 가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음 힙 정렬을 다시 말하자면, 최소 힙이나 최대 힙을 이용하여 정렬하는 방법입니다. 내림차순 정렬을 위해서는 최대 힙을 사용하고, 오름차순 .. 2021. 12. 16.
Quick Sort ( 퀵 정렬 ) Quick Sort 퀵 정렬은 1960년에 찰스 앤터니 리처드 호어(C.A.R hoare)가 처음 제안한 방법으로 이후 많은 사람들이 수정 보완하여 완성된 정렬 알고리즘이다. 이 알고리즘은 처음 소개된 이후로 반세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다. in place가 아닌 방법이 더 직관적으로 이해하기 쉬우므로 이 방법을 먼저 정리하고 그 다음 in place 방법을 정리하겠다. Basic Quick Sort - Not In Place 퀵 정렬은 분할정복 전략을 사용한 알고리즘이다. 즉, 정렬하는데 가장 간단한 배열은 바로 요.. 2021. 12. 16.
merge Sort ( 합병정렬 ) 합병정렬이란? 위의 그림과 같은 방식으로 작동해 배열을 정렬시켜주는 알고리즘입니다. 합병 정렬은 비교 기반 정렬 알고리즘으로 시간복잡도는 O(NlogN)입니다. 시간복잡도 최악 시간복잡도: O(nlogn) 평균 시간복잡도: O(nlogn) 최선 시간복잡도: O(nlogn) 합병정렬 javascript로 구현하기 병합정렬은 크게 두 가지 함수로 이루어져 있다. function merge(left, right) : 이미 소팅된 배열 left, right 받아서 하나로 합치는 순수한 함수 function mergeSort(arr) : 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수 이 때, merge함수는 순수한 함수이고, mergeSort는 재귀로 함수를 콜한다는 것을 인.. 2021. 12. 15.
Nest.js[Active Recore & Data Mapper Pattern Active Record Pattern Active Record 패턴은 모델 안에 모든 쿼리들을 정의해두고 CRUD 작업들을 모델의 메소드를 통해 실행하게 된다. 즉, Active Record 패턴은 모델 안에서 데이터베이스에 접근하는 패턴이라고 볼 수 있을 거 같다. import {BaseEntity, Entity, PrimaryGeneratedColumn, Column} from "typeorm"; @Entity() export class User extends BaseEntity { @PrimaryGeneratedColumn() id: number; @Column() firstName: string; @Column() lastName: string; @Column() isActive: boolean.. 2021. 12. 11.
GraphQl GraphQL은 페이스북에서 만든 쿼리 언어 스키마를 통해, 사용자만의 명령어를 만들고 사용할 수 있다. 번들 크기가 줄어, 클라이언트 속도가 빠르다! 아폴로 스튜디오를 이용해, 작성한 코드를 쉽게 테스팅 해볼 수 있다. Structed Query Language(이하 sql) 와 언어적 구조차이가 큼 SQL - 데이터베이스 시스템에 저장된 데이터를 효율적으로 가져오는 것이 목적 주로 백엔드 시스템에서 작성하고 호출 GQL - 웹 클라이언트가 데이터를 서버로부터 효율적으로 가져오는 것이 목적 주로 클라이언트 시스템에서 작성하고 호출 탄생배경 다시말해, REST 방법론이 있는데도 새로운 언어인 GraphQL 이 탄생해야했던 배경은 무엇인가? RESTful API 로는 다양한 기종에서 필요한 정보들을 일일히.. 2021. 12. 10.
Selection Sort(선택 정렬) Selection Sort 선택 정렬은 매우 단순한 정렬 알고리즘으로 구현하기 매우 쉬운 알고리즘이다. 선택 정렬 알고리즘은 이렇게 진행된다. 먼저 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교환한다. 이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다. 그 값을 맨 앞 위치 바로 다음 위치와 교체한다. ... 반복 버블 정렬이 각 회전이 끝날 때마다 맨 마지막 데이터의 위치가 정해졌던 것과 반대로 선택 정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다. 다음의 그림을 보면 이해가 쉽다. 장점 선택 정렬도 위의 두 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이므로 이해하기도 쉽고 구현하기도 쉽다. 단.. 2021. 12. 9.

티스토리툴바