Mason

재귀를 이용하여 코딩테스트를 하던도중 계속해서 실행시간 초과로 실패하였는데 알고보니 DP라는 것을 이용해야 하는 문제 였다. 동적 계획법 (DP) 최소의 단위로 문제를 쪼개어 연산한 뒤 배열에 저장하고 그 값들을 계속해서 이용하여 연산 후 배열에 저장, 결국엔 최종 값까지 도달하는 알고리즘 설계 기법이다. 간단히 말해 최소 단위의 문제를 푼뒤 그 값들을 계속해서 재활용하여 최후의 값을 구하는 방식이다. DP의 특징 DP를 사용할때 문제를 최소단위에서부터 연산을 시작하여 나온 값을 이용해 연속적으로 연산을 하게되는데 이는 재귀 구조와 매우 비슷하다. 이렇게 답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야 하는 종류의 문제의 구조를 최적 부분 구조(OPtimal Substructure)라 부르며 ..

그래프 순회(Graph Travaersal)이란 트리 순회와 마찬가지로 그래프의 모든 정점에 접근하는 것이며 실생활에서 연관검색, 사용자 맞춤 추천, 최단거리검색등에 사용된다. 해당 포스트의 코드구현은 이전 포스트에서 작성한 인접리스트를 이용하였다. (이전 포스트: https://mason-lee.tistory.com/73) class Traversal { constructor(graph) { this.graph = graph; } } const graph = new Graph(); graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D"); graph.addVertex("E"); graph.addVertex..

그래프는 여러개의 정점(Vertex)들이 간선(Edge)들로 서로 복잡하게 연결되있는 관계를 표현한 자료구조이다. 직접적인 관계가 있는 경우에는 두 정점 사이를 직접적으로 이어주는 간선이 있으며 간접적인 관계라면 몇개의 정점들과 간선들에 걸쳐 이어진다. 리스트, 트리, 그래프 리스트, 트리, 그래프 모두 비슷한 구조를 가지고 있다. 리스트 : 하나의 노드에 다른 하나의 노드가 연결되있고 또 다른 노드들이 체인처럼 직렬로 연결된 형태 트리 : 리스트와 같이 하나의 진행방향을 가지지만 하나의 노드에 여러 노드가 병렬적으로 연결된 형태 그래프 : 각 노드들이 순서와 개수에 상관없이 무작위로 연결된 형태 위와 같은 특징을 가지고 있으며 리스트에서 그래프로 점차적으로 진화된 형태를 띄고 있다. 이에 따라 그래프는..

Binary Heap 힙은 트리의 한 종류로 힙자체로도 많은 종류가 있다. 그중 하나가 바이너리 힙이며 이진 탐색 트리와 비슷하지만 조금 다른 규칙을 가지고 있다. 최대 이진 힙을 예로들어 부모노드는 항상 자식 노드보다 큰 값을 가지며 자식노드들 간의 순서가 존재 하지 않는다. (최소 이진 힙의 경우 부모노드는 항상 자식 노드보다 작은 값을 가짐) 또한 항상 최적의 용량을 가진다. 즉 자식노드가 생성되기 전에 모든 형제노드들이 채워지며 균형잡힌 트리구조로 만들어 진다. 그리고 항상 왼쪽의 자식 노드 먼저 채워지게 된다. 이진힙의 데이터들을 그 순서대로 배열에 나열할경우 어떠한 데이터의 인덱스가 n이라면 그의 왼쪽자식의 인덱스는 2n+1, 오른쪽 자식은 2n+2의 인덱스를 가지게 된다. 반대로 (n-1)/..

Tree Traversal 트리가 가지고있는 모든 노드를 순회하는 알고리즘으로 모든 트리구조에서 사용할수 있다. Breadth First Search(너비 우선 탐색)과 Depth First Search(깊이 우선 탐색)이 사용된다. Breadth First Search(너비 우선 탐색) root부터 시작하여 가로방향인 형제 노드들을 먼저 탐색하는 알고리즘이다. Queue를 이용하며 기본적인 작동원리는 큐의 첫번째 아이템의 자식노드들을 순서대로 큐에 추가해주고 큐의 값을 새로운 배열에 넣어준뒤 큐에서 제거한다. 이후 큐에 아이템이 없어질때까지 반복하면된다. BFS(node, queue = [], result = []) { if (!node) return result; result.push(node.val..

이진 검색 트리를 알기 위해선 트리 구조와 이진 트리 구조를 알아야 한다. Tree (트리) 연결 리스트 처럼 노드로 이루어진 데이터 구조로 parent와 child 노드로 이루어저 있다. 연결 리스트는 한노드당 하나의 노드만을 한줄로만 연결 시키지만 트리의 경우 하나의 노드와 다른 여러 노드들로 연결시켜 여러갈래로 구성된다. 트리의 경우 몇가지 규칙을 가지고 있다. 부모노드는 여러 자식노드를 가질수 있지만 자식노드는 하나의 부모 노드만을 가지며 부모노드는 자식 노드만을 가리킬수 있다. 또한 트리의 시작점은 단하나의 노드에서 시작되며 이 노드를 root라 부른다. 몇가지 용어들을 더 정리 하자면 자식노드 루트에서 멀어지는 방향으로 연결된 노드 부모노드 자식노드와 반대의 개념 형제노드 같은 부모를 가진 노..

Stack 데이터의 모음이 되는 자료 구조중의 하나로서 단순하게 LIFO, Last In Last Out(후입선출)의 특징을 가진 자료구조이며 여러한 곳에서 사용된다. 예를들면 자바스크립트에서 재귀함수 호출시, Undo와 같이 이전 작업으로 되돌릴때, 인터넷 브라우저의 방문기록을 쌓고 뒤로가기를 사용할때 혹은 트리나 그래프같은 알고리즘의 중간 매개체로도 사용된다. 배열을 이용한 Stack push()와 pop() 혹은 shift()와 unshift()의 조합을 이용하여 배열을 스택으로 사용할수 있지만 배열의 특성상 shift()와 unshift()의 경우 배열안의 아이템들의 인덱스를 모두 바꿔주는 작업이 생기므로 push()와 pop()을 이용한다. Linked list를 이용한 Stack class N..

이중 연결 리스트 단일 연결 리스트와 마찬가지로 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진수)의 버킷을 만든다. 받은 숫자형 데이터들의 첫번째 자릿수를 해당되는 버킷에 배치시킨후 버킷의 순서대로 배열을 재배치 시킨다. 이후 재배치된 데이터들의 두번째 자릿수를 이용하여 동일한 작업을 진행하며 반복적으로 작업을 수행하며 필요에 따라 반복적으로 계속해서 진행된다. 몇개의 보조 함수들이 필요하며 배열의 가장 큰수를 구하고 그수가 가진 자릿수를 구하며 데이터의 특정 자릿수에대한 값을 구하는 함수들이 필요하다. 최대 자릿수 알아..