처음부터 차근차근

Backtracking이란?? 해(답)을 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가서 다시 해를 찾아가는 기법을 의미한다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 주로 DFS 등 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤, 그 이전으로 돌아가서 다시 다른 경우를 탐색하게 구현할 수 있다. 백트래킹 기법의 유망성 판단 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking..

너비 우선 탐색(BFS)이란?? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 의미한다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다., 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. DFS의 경우 BFS보다 좀 더 복잡하다. BFS의 특징 시작 노드에서 시작해서 거리에 따라 단계별로 탐색하기 때문에 직관적이지 않은 면이 있다. 재귀적으로 동작하지 않는다. 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 그렇지 않으면 무한 루프에 빠질 위험이 있다. BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 즉, ..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42626 문제 설명 내 풀이 class MinHeap { constructor() { this.heap = []; } // 부모 인덱스, 자식 인덱스 구하는 메소드 getParentIndex(childIndex) { return Math.floor((childIndex - 1) / 2); } getLeftChildIndex(parentIndex) { return 2 * parentIndex + 1; } getRightChildIndex(parentIndex) { return 2 * parentIndex + 2; } swap(idx_1, idx_2) { [this.heap[idx_1], th..

오늘 한 일 DFS 구현 인접 행렬, 인접 리스트 구현 기업지원 진행 DFS DFS 구현 방법을 Javascript로 정리하였다. 재귀함수와 스택을 이용하는 방법으로 정리 코딩테스트를 풀어보면서 적용해야 할 것 같다. 깊이 우선 탐색이란 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미하며, 예시로 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법입니다. 깊이 우선 탐색의 특징은 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있으며, 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 점입니다. DFS 구현 방법은 재귀함수를 이..

깊이 우선 탐색(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..

Graph 관련 문제를 해결하기 위해 모델링할 경우에는, 두 가지 방법이 존재합니다. 인접 행렬 인접 리스트 인접 행렬 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다. 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다. 간단히 요약하자면 다음과 같다. adj[i][j] = 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0 다음 그래프를 한번 살펴보자 1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 합니다. 0 - 1 이 연결되어있기 때문에..

Graph란?? 그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. -wikipedia 그래프는 트리와 비슷하게 정점과 간선으로 구성되어 있다. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다. 그래프는 노다 간에 여러 개의 간선이 존재할 수 있다. 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프( = 양방향 그래프)로 나눌 수 있다. Vertex & Edge Vertex(정점) 노드라고 불리며, 그래프를 형성하는 기본 단위이다. 정점은 분할할 수 없는 객체이자 "점"으로 표현되는 위치, 사람, 물건 등이 될 수 있다. Edge(간선) ..

오늘 한 일 저번주 동안 Infograb 채용 과제를 진행했다. Heap 구현 코어자바스크립트 Prototype, class Infograb 채용 과제 저번주 동안 infograb 채용 과제를 진행 로그인, 로그아웃 기능이였으며, HTML 페이지를 리턴하는 과제 Passport를 처음 사용해봤으며, 이를 통해 NestJS가 어떻게 구성되어있는지 조금 더 자세히 알게 됬다. 저번주동안 바빠서 TIL을 적지 못했다. 채용 관련 Test 과제와 발표 준비로 인해 바빠서 적지 못한 점이 아쉬웠다. Test의 내용은 간단하였다. Login, Logout이 되는 서버 구현 그 외 모든것이 자유 Passport-local, Passport-JWT를 구현한 로그인, 로그아웃 기능 구현 나는 Passport를 사용해..

NestJS란?? Nest는 효율적이고 확장 가능한 Node.js 서버 측 애플리케이션을 구축하기 위한 Framework입니다. JavaScript를 사용하고 TypeScript로 빌드되며 완벽하게 지원하며 (개발자가 순수 JavaScript로 코딩할 수 있음) OOP, FP(Functional Programming) 및 FRP(Functional Reactive Programming) 요소를 사용할 수 있게 해줍니다. Node.JS 기반의 서버 사이드 Framework이다. 효율적이고 안정적이며 확장 가능한 Server Application을 구축하기 위한 Framework라고 보면 된다. Enterprise급 Application 구축에 적합하다. (Node진영의 Spring 대항마로 나온 느낌..)..