본문 바로가기

Algorithm65

[Algorithm] Queue 알고리즘 Printer Spooler 구현하기 문제 Queue 자료구조의 대표적인 활용 사례는 프린터 스풀러다. 출력할 문서들은 Printer Buffer에 차례대로 저장되고, 먼저 저장된 문서부터 출력이 시작된다. 입력으로는 bufferSize, capacities, 문서로 구성된 배열인 documents 3가지가 주어진다. 인쇄할 문서의 크기가 나열된 배열 documents가 모두 인쇄되는데 걸리는 최소 시간을 반환하라. 제한사항 인쇄 작업 목록은 칸으로 이루어져 있음 각 칸에는 한개의 문서만 위치가능 문서는 1초에 한 칸씩만 움직일 수 있음 인쇄 작업 목록의 크기는 bufferSize고 최대 용량 capacities 만큼 문서를 담을 수 있음 1 0 ){ count++; // Debugging console.log(` queue : ${queu.. 2022. 5. 24.
[Algorithm] Queue 알고리즘 문제, 박스 포장 Javascript 문제 박스를 포장하는 긴 줄이 있다고 가정한다. 박스를 포장하는 공간이 협소하기 때문에 들어온 순서대로 포장을 마치고 나가야 한다. 들어온 사람들은 모두 포장을 할 수 있지만, 가장 먼저 들어온 사람이 포장을 완료해야 이 후 포장을 마친 사람들도 나갈 수 있다. 뒷 사람이 포장을 완료하였어도, 첫 사람이 포장을 다 완료하지 못했다면 대기해야 하는 상황이다. 예를 들어 앞 사람이 포장해야 할 박스가 3개고 2번째 사람이 포장해야할 박스가 1개라면, 첫 사람이 3개의 박스 포장을 완료한 후 같이 나갈 수 있다. 전체 박스를 포장해야하는 사람들 중 한번에 몇명씩 나갈 수 있는지 최대값을 반환하라. 제약조건 1 2022. 5. 23.
[Algorithm] 웹 브라우저 앞으로 가기 뒤로 가기 구현하기 브라우저 앞으로 가기 뒤로가기 스택 알고리즘을 활용한 실예제 중 대표적인 것이 웹 브라우저 앞으로 가기와 뒤로 가기다. 웹 브라우저에서 앞으로 가기와 뒤로가기는 스택(Stack) 자료구조를 활용해서 구현되었다. 브라우저에서 앞으로 가기와 뒤로가기를 구현하기 위한 조건은 아래와 같다. 새로운 페이지에 접속하는 경우 pre 스택에 원래 페이지를 push하고 next 스택을 비워준다. 뒤로 가기 버튼을 클릭하는 경우 현재 페이지를 next 스택에 push 한다. pre 스택의 Top 위치에 있는 페이지를 pop하여 현재 페이지로 사용한다. 앞으로 가기 버튼을 클릭하는 경우 원래 페이지를 pre 스택에 push 하고 next 스택에서 pop하여 현재 페이지로 사용한다. 브라우저에서 앞으로 가기와 뒤로 가기 버튼.. 2022. 5. 23.
[Algorithm] Advanced Fibonacci using Memoization Memoization 함수형 프로그래밍 언어인 Javascript에서 계산 결과를 저장해두는 방식으로 하위 함수를 호출하는 방식이다. 값을 저장할 객체를 생성하고 하위 함수에서 계산된 값을 객체에 저장하면서 재귀 알고리즘을 최적화 할 수 있다. 예시 advanced fibonacci algorithm function fibonacci(n) { // Memoization 객체 const fibo_cache = {}; // 하위 함수 // 하위 함수에서는 fibo_cache를 참조하고 있기 때문에, // fibo_cache는 메모리 상에서 제거되지 않고 값을 유지하게 된다. // subFunc() 함수의 렉시컬 환경에서는 지속적으로 fibo_cache를 참조해서 // 로직을 구성할 수 있다. const su.. 2022. 5. 23.
[Algorithm] Javascript 알고리즘, 프레젠테이션 순서 정하기 문제 문제 1 2022. 5. 22.
[Algorithm] 재귀 알고리즘 문제 Javascript 피보나치 문제 문제 0 2022. 5. 22.
[Algorithm] 순열(Permutation) 경우의 수 구하는 알고리즘 문제(feat. 재귀(Recursion) 함수 사용) 문제 입력값으로 임의의 수 N(1 2022. 5. 20.
[Algorithm] Data Structure Tree , 트리 자료구조란? 이진 탐색 트리 (BST, Binary Search Tree) Tree 자료구조란? Tree 자료구조는 나무를 거꾸로 뒤집은 형태로 데이터를 표현하는 자료구조를 의미한다. 그래프의 자료구조 중 단방향 그래프의한 종류다. 한개의 뿌리(Root)로 부터 가지가 사방으로 뻣은 형태로 데이터 흐름이 전개된다. 데이터가 아래에 하나 이상의 데이터에 무방향으로 연결되어 있는 계층적인 자료구조의 형태를 가지고 있다. 트리 자료구조는 그래프와 함께 대표적인 비선형 자료구조에 속한다. Tree 자료구조는 계층적으로 표현되고, 아래로만 데이터가 뻗어나가기 때문에 사이클이 존재하지 않는다. Tree 자료구조는 제일 꼭대기 Node인 루트(Root)에서 시작한다. 아래에 간선으로 연결된 노드(Node)로 구성되어 있따. 노드는 수평관계와 수직관계로 구성되는데 수직관계의 경우 부모/자식 .. 2022. 5. 16.
[Algorithm] Javascript Graph Data Structure 그래프 자료구조 알고리즘 Javascript Graph Data Structure Graph 자료구조는 여러 점들이 복잡하게 연결되어 있는 관계를 표현한 자료구조다. Graph 자료구조는 정점(Vertex)와 간선(Edge)로 구성된다. 두 정점이 직접적인 관계가 있다면 선으로 연결되고 간접적으로 연결되어 있다면 여러개의 선을 거쳐 연결된다. Graph 자료구조는 크게 무방향 그래프와 방향 그래프로 구분된다. 한 정점에서 다른 정점으로의 방향이 정해진 경우 반대 방향으로 흐름이 흘러갈 수 없다. 방향 그래프 또한 양방향 간선과 단방향 간선으로 구분된다. Graph 자료구조 인접행렬 두 정점(Vertex)을 연결하는 간선이 있다는 말은 두 정점이 인접해있다는 것이다. 정점간의 관계를 코드로 표현하기 위해서는 인접행렬을 사용한다. .. 2022. 5. 16.
[Algorithm] Data Structure and Algorithm Stack vs Queue 자료구조란? 자료구조란 여러 데이터들의 묶음을 저장 및 사용 방법을 정의한 것이다. 데이터란 실생활을 구성하고 있는 값을 의미한다. 잘 정리된 데이터는 새로운 인사이트를 만들어낼 수도 있고, 사용성을 높이기 때문에 데이터의 활용도를 높이기 위해 자료구조가 탄생하게 된다. 실생활에서 데이터를 효율적으로 사용하기 위한 방법인 자료구조는 알고리즘 문제에서도 자주 출제된다. 알고리즘 문제에서 자주 등장하는 자료구조는 Stack, Queue, Tree, Graph 4가지 종류다. 선형 자료구조 Stack Stack 쌓아올리다 라는 뜻을 가지고 있다. 말 그대로 데이터를 입력된 순서대로 쌓아올리고 가장 위에서 부터 데이터를 출력하는 LIFO(Last In First Out) 형식을 취하고 있다. 스택의 특징 ① 입.. 2022. 5. 16.
[Algorithm] 조합(Combination)과 순열(Permutation) 알고리즘 Javascript 조합(Combination) 알고리즘 조합은 수를 정렬하는 방법 중 순서를 신경쓰지 않는 방식이다. 임의의 N개의 수로 구성된 집합을 의한다. 순서에 상관없이 m개의 원소를 선택하게 된다. 즉 N개의 원소로 구성된 배열에서 m개의 원소로 구성된 부분 집합을 찾는 과정이다. [1,2,3]의 집합에서 2개의 원소를 출력하라는 문제가 주어질 때 아래 3개의 경우가 참값이 된다. [1,2] [1,3] [2,3] 조합의 공식 순열(Permutation) 알고리즘 순열은 순서를 고려하여 n개의 집합에서 r개의 원소를 추출하는 작업을 의미한다. 3개의 원소를 가진 배열에서 2개의 원소를 추출한다고 하면 총 6개의 결과값이 도출된다. [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] 순열 공식 소스 코드.. 2022. 5. 14.
[Algorithm] 하노이의 탑 알고리즘 Javascript 구현하기 재귀 알고리즘? [Algorithm] 재귀 알고리즘이란 recursion algorithm what is recursive algorithm? How can I solve recursion algorithm? 재귀 알고리즘 알고리즘에는 여러가지 방법이 존재한다. 그 중에서도 분할 정복법의 한 유형인 재귀 알고리즘은 문제를 더 작은 구조의 문제.. about-tech.tistory.com [Algorithm] Javascript Recursion Memory Leak 재귀 함수와 메모리 사용량 분석 알아보기 [Algorithm] 재귀 알고리즘이란 recursion algorithm what is recursive algorithm? How can I solve recursion algorithm? 재귀 알.. 2022. 5. 14.
[Algorithm] Tail Recursion 이란? Optimization 꼬리 재귀 예제 피보나치 수열 Tail Call Tail Recursion을 이해하기 전에 Tail Call 부터 알아보자. Javascript에서 함수를 호출하면 콜 스택 이라는 영역에 함수 정보를 저장하게 된다. 참조 형식의 메모리 할당 방식을 사용하는 Javascript에서는 함수를 호출하는 순간, 함수에 관한 정보, 함수 내 변수 값들을 저장하는 실행 컨텍스트를 관리한다. 여기서 Tail Call은 상위 함수에서 해야할 일을 만들지 않는 호출 방식이다. 원래 자리로 돌아가 남은 로직을 수행하기 위해 Stack 메모리가 할당 되는데 이 과정에서 메모리 누수가 발생할 수 있기 때문에, Tail Call을 사용해 가장 밑단의 함수에서 모든 일을 다 처리하고 , 상위 함수에는 추가적으로 더 해야 할 로직을 두지 않는 방식이다. Tai.. 2022. 5. 13.
[Algorithm] Javascript Recursion Memory Leak 재귀 함수와 메모리 사용량 분석 알아보기 [Algorithm] 재귀 알고리즘이란 recursion algorithm what is recursive algorithm? How can I solve recursion algorithm? 재귀 알고리즘 알고리즘에는 여러가지 방법이 존재한다. 그 중에서도 분할 정복법의 한 유형인 재귀 알고리즘은 문제를 더 작은 구조의 문제.. about-tech.tistory.com 재귀 알고리즘 실행 컨텍스트 Javascript 실행 함수는 실행 컨텍스트(Execution Context)에 저장된다. 함수가 호출 될 때 실행 컨텍스트에 함수 실행에 대한 정보를 차곡차곡 쌓아나간다. 함수 실행 시 제어 흐름의 위치, 변수의 현재 value, this 값 등 다양한 내부 정보를 담고 있다. 실행 컨텍스트는 메모리를 사.. 2022. 5. 13.
[Algorithm] 재귀 알고리즘 Tree UI 구현하기 Tree 자료구조 with 재귀 알고리즘 재귀 알고리즘을 사용하기 최적화된 환경이 바로 트리 자료구조다. 자식 노드들을 찾아가면서 해당 노드들을 반복적으로 렌더링 하는 과정에서 몇번의 반복이 예측하기 힘든 반복문 보다는 재귀 알고리즘이 적합하다. 문제 : 트리 구조의 데이터를 재귀함수를 이용해 렌더링 하세요 풀이 : 재귀 알고리즘을 구성할 때는 탈출 조건(base case)와 재귀 로직으로 구분해서 생각해야 한다. ① 첫번째 순서로 currentNode에 추가할 'li' 태그를 생성하고 자식 노드의 배열이 포함되어 있는지 여부를 체크한다. const res = document.createElement('li'); const hasChildren = Array.isArray(menu[i].children).. 2022. 5. 13.

티스토리툴바