본문 바로가기

분류 전체보기

 (138)
NestJS로 API 만들기 - 1 IntroductionNestJS는 백엔드를 구성할 수 있게 한다.node.js 위에서 움직이는 프레임워크다.Typescript에 기반하고 있다.yarn보다 npm이 더 안정성 있으므로 package는 npm을 사용한다. $ npm i -g @nestjs/cli$ nest new project-name 백엔드 API를 구성하기 위해 Insomnia Core를 다운로드 해야 한다. Architecture of NestJSmain에서 모듈로 이동하고, 모듈에서 컨트롤러로 이동하고, 서비스로 이동하면 텍스트를 나타내는 부분을 알 수 있다.서비스는 클래스며 함수를 가지고 있다. 모듈은 어플리케이션의 일부로, 기능을 담당할 수 있다.인증을 담당하는 어플리케이션이 있다면 유저 모듈이 되는 것이다. @로 나타내는 부..
[면접대비] 공간 복잡도(Space complexity) 공간 복잡도알고리즘이 얼마나 많은 메모리를 소모하는가.메모리 소모와 빅 오 표기법newArray 등 새로운 배열을 원소 N개에 따라 생성하는 경우: O(N)새로운 배열을 생성하지 기존 배열의 원소를 바꾸는 경우: O(1)추가로 소모한 공간은 보조 공간(auxiliary space)라 부른다.입력도 포함하여 공간 복잡도를 계산하는 경우도 있다. 이 경우도 틀린 경우는 아니다.시간 복잡도와 공간 복잡도의 선택애플리케이션이 매우 빠르고, 처리할 메모리가 충분하다면 시간복잡도가 낮은 경우가 적절하다.속도는 크게 중요하지 않지만 메모리를 절약해야 하는 경우 공간복잡도가 낮은 경우가 적절하다.근본적으로는 최소 허용 속도와 메모리 한도를 아는 것이 좋다.재귀함수와 공간 복잡도: O(N)재귀함수를 호출하는 경우 호출 ..
[면접대비] 트라이(trie) 트라이(trie)트라이는 다른 구조처럼 명확한 정의가 있는 것이 아니라, 조금씩 다르게 구현한다.트라이 노드는 자식 노드의 개수에 제한이 없다.트라이 노드마다 해시 테이블을 포함하여, 키는 알파벳이고 값은 트라이의 다른 노드다.트라이 구조의 단어 저장 구현각 알파벳은 key를 나타낸다.*는 단어가 끝났음을 알려준다. 값은 null이다.*의 값을 인기도와 같이 순위를 지정할 수 있다면, 자동완성 기능을 제공할 때 인기도에 따라 제공할 수도 있다.{*, 't'}에서 *와 t는 모두 key다. 트라이 구조의 시간복잡도탐색: 검색 문자열 내 문자 수에 따라 달라진다. O(K)변수를 만든다. 처음 시작할 때 이 변수는 루트 노드를 가리킨다.검색 문자열의 첫 문자를 키로 하는 자식이 있는지 확인한다.자식이 없다면 ..
[면접대비] 힙(heap) 힙(heap)이진트리에 속한다.다음의 힙 조건(heap condition)중 하나를 만족시켜야 한다.각 노드의 값은 그 노드의 모든 자손 노드의 값보다 커야 한다. 최대 힙.각 노드의 값은 그 노드의 모든 자손 노드의 값보다 작아야 한다. 최소 힙.트리는 완전해야 한다. 즉 빠진 노드 없이 완전히 채워져야 한다.바닥줄에는 빈 자리가 있ㅇ르 수 있다.빈 자리의 오른쪽으로는 어떤 노드도 없어야 한다.힙의 시간복잡도탐색: 각 노드를 모두 검사해야 하므로 검색 연산을 구현하지 않는다. 읽기 연산이 선택적으로 있을 수 있다.삽입: 이진트리의 줄(line)은 모두 O(logN)개다. O(logN)새 값을 포함하는 노드를 생성하고 바닥 레벨의 가장 오른쪽 노드 옆에 삽입한다.삽입한 노드와 부모 노드를 비교한다.새 노..
[면접대비] Tree Tree계층적 관계(Hierarchical Relationship)을 표현하는 자료구조다.비선형 자료구조에 해당한다.Tree에 쓰이는 용어루트(root): 가장 상위 노드부모(parent): 연결된 상위 노드자식: 연결된 하위 노드자손(descendant): 그 노드에서 생겨난 모든 노드조상(ancestor) 그 노드를 생겨나게 한 모든 노드레벨(level): 트리에서 같은 줄을 의미프로퍼티(property): 균형잡힌 정도하위 트리의 노드 개수가 같으면 그 트리는 균형(balanced) 트리다.하위 트리의 노드 개수가 다르면 그 트리는 불균형(imbalanced) 트리다.Binary  Search Tree(이진 탐색 트리)루트 노드에서 두개의 서브 트리로 나누어지고, 나누어진 서브 트리도 두개로 나누어..
[면접대비] 퀵정렬 퀵정렬(Quicksort)매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 효율적이다.분할(partitioning) 개념에 기반한다.분할배열의 임의의 수를 고른다. 이 수는 피벗(pivot)이라고 부른다.피벗보다 작은 수는 피벗의 왼쪽에, 큰 수는 피벗의 오른쪽에 둔다.배열에서 분할 구현 방법1. 왼쪽 포인터를 한칸씩 옮기며 피벗과 값을 비교한다. 피벗보다 크거나 같으면 멈춘다(값 A).2. 오른쪽 포인터를 한칸씩 옮기며 피벗과 값을 비교한다. 피벗보다 작거나 같으면 멈춘다. 또는 배열 맨앞에 도달해도 멈춘다(값 B).3-1. 값 A의 위치와 값 B의 위치를 바꾼다. 다시 1을 반복한다.3-2. 값 A의 위치가 값 B의 위치를 넘어선 경우 왼쪽 포인터의 값과 피벗을 교환한다.결과적으로 완전히 정렬되지는..
[면접대비] 재귀함수 재귀함수함수가 자기 자신을 호출할 때를 뜻한다. 재귀함수의 반복되지 않는 조건, 기저조건함수가 반복되지 않는 경우에 대한 조건을 기저 조건이라 부른다.기저조건이 없다면 단기 메모리에 더이상 데이터를 저장할 공간이 없을 때까지 호출 스택이 늘어간다.이 경우 스택 오버플로(stack overflow)오류가 발생하고, 컴퓨터는 재귀를 강제로 중단한다. 아래의 카운트다운 함수에서는 0이 기저 조건에 해당한다. 재귀함수의 실행 순서재귀함수는 실행된 함수가 다 끝나기 전 같은 함수가 불리게 된다.3번 반복되는 재귀함수의 경우 다음과 같이 stack으로 함수를 호출하고 처리한다.3번 함수와 2번 함수가 다 끝나지 않았으므로 스텍에 남아 있는다.1번 함수가 return을 반환하여 완료되면 스텍에서 팝하여 제거된다.차례..
[면접대비] Stack, Queue와 Javascript 예제 선형 자료구조적용 가능한 Methodpush: 리스트 제일 뒤에 추가pop: 리스트 제일 앞에 삭제shift: 리스트 제일 앞에 추가unshift: 리스트 제일 뒤에 삭제Stack바구니 안에 층층이 쌓이는 것과 같은 구조다.가장 나중에 들어간 것이 먼저 나오고, 가장 먼저 들어간 것이 나중에 나온다.Last In First Out(LIFO)First In Last Out(FILO) Javascript와 Stack의 구현 예제 Stack이 사용되는 예시재귀 알고리즘웹 브라우저의 뒤로가기 기능실행 취소기능Stack의 시간복잡도삽입: 가장 최근에 들어온 데이터를 찾고 데이터를 추가한다. O(1)삭제: 가장 최근에 들어온 데이터를 삭제한다. O(1)Queue줄을 서는 것과 같은 구조다.가장 처음에 들어간 것이 ..
[면접대비] Array, Linked List 복잡도(Complexity)알고리즘의 성능, 효율성을 나타내는 척도다.최악의 경우를 가정해서 알고리즘 성능을 파악한다.시간 복잡도(Time Complexity): 알고리즘의 수행 시간에 대한 척도.공간 복잡도(Space Complexity): 알고리즘의 메모리 사용량에 대한 척도.보통 시간 복잡도와 공간 복잡도는 반비례한다.시간 복잡도 구하기입력을 기준으로 할 때 필요한 연산 횟수에 따라 결정된다.시간 복잡도가 너무 크면 주어진 시간이 초과될 수 있다.공간 복잡도 구하기고정 공간: 코드가 저장되는 공간 등.가변 공간: 알고리즘에 따라 달라지는 공간. 변수를 저장하는 공간, 순환 스택 등.내부에서 생성된 배열 등의 차원에 따라 결정된다.재귀함수일 경우 스텍이 쌓이면서 공간 복잡도가 높아질 수 있다. 공간 ..
[면접대비] RESTful API REST(Representational State Transfer)ful API: REST 의 기본 원칙을 성실히 지킨 서비스 디자인이다. Resource Oriented Architecture으로, API 설계의 중심에 자원(Resource)이 있고 HTTP Method 를 통해 자원을 처리하도록 설계하는 것이다.REST 6 가지 원칙Uniform InterfaceStateless: 상태저장 없이 요청만을 단순 처리 할 수 있음.Caching: HTTP의 캐싱 기능 활용 가능.Client-ServerHierarchical systemCode on demand REST API 제대로 알고 사용하기 : NHN Cloud MeetupREST API 제대로 알고 사용하기meetup.nhncloud.com RE..

티스토리툴바