일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 코딩테스트
- queue
- nestjs
- 프로그래머스
- TIL
- Interceptor
- html
- typescript
- 변수
- dfs
- winston
- Deep Dive
- 자료구조
- OOP
- REST API
- node.js
- 인접리스트
- 인접행렬
- bean
- logger
- java
- css
- 알고리즘
- Spring
- LifeCycle
- JWT
- javascript
- 탐욕법
- GraphQL
- MySQL
- Today
- Total
목록CS (33)
처음부터 차근차근
Rest API 중심 규칙 Rest API 설계 시 가장 중요한 항목은 다음의 2가지로 요약할 수 있다. URI는 정보의 자원을 표현해야 한다. 자원에 대한 행위는 HTTP Method(GET, POST, PUT, DELETE)로 표현한다. 다른 것들은 다 잊어도 위 내용은 항상 지켜야 한다. 참고 리소스 원형 도큐먼트 : 객체 인스턴스나 데이터베이스 레코드와 유사한 개념, 간단하게 문서 혹은 객체로 이해 컬렉션 : 서버에서 관리하는 디렉터리라는 리소스, 문서들의 집합으로 이해하면 편하다. 스토어 : 클라이언트에서 관리하는 리소스 저장소 1. URI는 정보의 자원을 표현해야 한다. resource는 동사보다는 명사를, 대문자 보다는 소문자를 사용한다. resource의 도큐먼트 이름으로는 단수 명사를 사..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/WTKSs/btsAO8iqtec/dOUSnMGgPMkXsdORfd5XDK/img.png)
GraphQL이란? GraphQL은 API를 위한 쿼리 언어이며 이미 존재하는 데이터로 쿼리를 수행하기 위한 런타임 입니다. GraphQL은 API에 있는 데이터에 대한 완벽하고 이해하기 쉬운 설명을 제공하고 클라이언트에게 필요한 것을 정확하게 요청할 수 있는 기능을 제공하며 시간이 지남에 따라 API를 쉽게 진화시키고 강력한 개발자 도구를 지원합니다. GraphQL은 페이스북에서 만든 쿼리 언어이며, 최근 핫한 쿼리 언어 중 하나입니다. Graph QL(이하 gql)은 SQL과 마찬가지로 쿼리 언어이다. SQL은 데이터베이스 시스템에 저장된 데이터를 효율적으로 가져오는 것이 목적이지만, gql은 웹 클라이언트가 데이터를 서버를 효율적으로 가져오는 것이 목적이다. 즉, gql의 문장은 주로 클라이언트 시..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/y4pdp/btsAurgWtHt/R709ec0qaBsr5kq0upUkwK/img.png)
Binary Tree(이진 트리) 부모 노드의 자식 노드 수가 2개 이하로 구성되어 있는 Tree를 의미한다. 이진 트리는 다음과 같이 분류 할 수 있다. 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미합니다. 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다. 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미합니다. 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미합니다. 균형 이진 트리(balan..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/OVQ0J/btsAnxDfQdY/csOpRQaOmg8ks9Czip7ndK/img.png)
Tree란? 트리는 자식노드와 부모 노드로 이루어진 계층적인 구조를 가지며, 무방향 그래프의 일종이자 사이클이 없는(순환 구조를 갖지 않는) 자료구조를 의미한다. 비선형 자료구조로 계층적 관계를 표현한다. Tree로 이루어진 집합을 숲(forest)이라고 한다. Tree의 특징 그래프의 한 종류이며, '최소 연결 트리'라고도 불린다. 계층 모델이다. 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다. Loop나 circuit이 없다. 당연히 self-loop도 없다. 즉, 사이클이 없다. 노드가 N개인 Tree는 항상 N-1개의 간선(edge)을 가진다. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/Cyffj/btsAqwC8yHC/Nka8rtzTAgEFYsNZFzZw61/img.png)
Backtracking이란?? 해(답)을 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가서 다시 해를 찾아가는 기법을 의미한다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 주로 DFS 등 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤, 그 이전으로 돌아가서 다시 다른 경우를 탐색하게 구현할 수 있다. 백트래킹 기법의 유망성 판단 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cyhJVv/btsAon7CIWI/kifAmRE39vBQu31KVMXP7K/img.gif)
너비 우선 탐색(BFS)이란?? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 의미한다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다., 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. DFS의 경우 BFS보다 좀 더 복잡하다. BFS의 특징 시작 노드에서 시작해서 거리에 따라 단계별로 탐색하기 때문에 직관적이지 않은 면이 있다. 재귀적으로 동작하지 않는다. 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 그렇지 않으면 무한 루프에 빠질 위험이 있다. BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 즉, ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/yVwrs/btsAqxPoYxM/HEkLvtrytfumKxmILR74D1/img.gif)
깊이 우선 탐색(DFS)이란?? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미한다. 탐색하는 방법은 아래 그림과 같다. 미로와 같이 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것을 의미한다. DFS의 경우 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 깊이 우선 탐색의 특징 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다. 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다. 이 알고리즘..
인접 행렬 구현 방법 자바스크립트는 다른 언어와는 다르게 2차원 배열을 구현하는 방법이 없다. (예시로 a[i][j] 이런식으로 구현할 수 없다) 따라서 Array.from 메서드를 사용하여 구현해줘야 한다. function Matrix(v) { // 자바스크립트에는 2차원 배열을 만들 때 a[0][0] 이런식으로는 만들 수 없다. // 따라서 2차원 배열을 만들 경우 이렇게 만들어야 한다. const a = Array.from(Array(10), () => new Array(10).fill(0)); const visited = Array.from(Array(10).fill(0)); a[1][2] = 1; a[1][3] = 1; a[3][4] = 1; a[2][1] = 1; a[3][1] = 1; a[4..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cYiGrB/btsAnzNPkbR/p4QU2Bxi50bhHO15AKl8a0/img.png)
Graph 관련 문제를 해결하기 위해 모델링할 경우에는, 두 가지 방법이 존재합니다. 인접 행렬 인접 리스트 인접 행렬 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다. 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다. 간단히 요약하자면 다음과 같다. adj[i][j] = 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0 다음 그래프를 한번 살펴보자 1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 합니다. 0 - 1 이 연결되어있기 때문에..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cg3JzE/btsAklimIQR/tzYrCXMuOSpih7Jm8Kbsh1/img.png)
Graph란?? 그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. -wikipedia 그래프는 트리와 비슷하게 정점과 간선으로 구성되어 있다. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다. 그래프는 노다 간에 여러 개의 간선이 존재할 수 있다. 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프( = 양방향 그래프)로 나눌 수 있다. Vertex & Edge Vertex(정점) 노드라고 불리며, 그래프를 형성하는 기본 단위이다. 정점은 분할할 수 없는 객체이자 "점"으로 표현되는 위치, 사람, 물건 등이 될 수 있다. Edge(간선) ..