본문 바로가기

the others/Algorithm13

GCD (최대 공약수) & LCM (최소 공배수) & 유클리드 호제법 📍 GCD : Greatest Common Divisor : 최대 공약수 📍 LCM : Least Common Multiple : 최대 공배수 📌 유클리드 호제법 ? 유클리드 호제법은 두 양의 정수 간의 최대 공약수를 구할 수 있는 방법이다. 단, a 가 b 보다 항상 크다는 전제가 있어야 성립한다. -> 당연한 이야기인게, a = bq + r 공식에서 이미 b는 a의 약수로 속해 있다. a = bq + r 식은 a와 b 간의 관계를 정의한 식이다. -> a가 b 보다 크다면, b*q 값과 어떤 나머지 정수가 더해져 a를 완성할 것이다. 여기서 나머지 값(r) 이 0이게 되면 a와 b 사이에서는 b가 가장 큰 최대 공약수가 되는 것이다 ! 만약 r이 0이 아니라면 ? r은 b와 어떤 정수 q의 곱으로 a.. 2021. 11. 10.
[ Graph - BFS ] 인접 행렬 길 찾기 ✅ BFS 기초 개념 잡기 https://blog.naver.com/wpghks7/221598474816 BFS의 기초 개념을 잘 설명해놓은 블로그가 있어 첨부한다. 📍 제한 사항 주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다. 📍 예시 const result = getDirections( [ [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0] ], 0, 2 ); console.log(result) // true 📍 코드 공부 0과 2는 직접적으로 연결되어있지는 않다. 그러나 둘은 간선으로 연결되어있으므로 true 를 반환하도록 식을 짜야한다. 어떻게 해야할까 ?? 그리고 만약 첫번째 간선에서 원하는 결과가 탐색되.. 2021. 10. 13.
자바스크립트 프로그래머스 거스름돈 문제 풀이 📌 문제 ◾ 해설 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다. 5원을 1개 사용해서 거슬러 준다. 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성.. 2021. 10. 12.
Dynamic Programming 동적 프로그래밍 📌 동적 프로그래밍이란 ? 동적 프로그래밍이라고 해서 동적으로 ?!? 프로그래밍이 이루어지는 건 아니다 ㅋㅋㅋ 큰 문제를 작은 문제로 나누어 푸는 법을 말한다. -> 그럼 분할 정복 아닌가 ? 📍 Divide and Conquer 분할 정복이란 ? 분할 정복도 큰 문제를 작은 문제로 나누어 푸는 법이다. 그러나 동적 프로그래밍과는 큰 차이점이 있다. 분할 정복은, " 작은 문제 " 에서 반복이 일어나지 않는다. 동적 프로그래밍은, " 작은 문제 " 에서 반복이 일어난다. -> 불필요한 일들이 반복적으로 일어난다. 즉, 분할 정복은 진짜 큰 문제를 여러 개로 작게 작게 나눠서 푸는 방식이라면, 동적 프로그래밍은 어짜피 반복되는 작은 문제들을 한 곳에 묶어 놓거나(?) 기록(?) 하는 식으로 불필요한 반복들.. 2021. 10. 11.
[ Queue ] 프린터 📍 제한 사항 ✔ 인쇄 작업 목록은 칸으로 이루어져 있습니다. ✔ 각 칸에는 한 개의 문서만 위치할 수 있습니다. ✔ 문서는 1초에 한 칸만 이동할 수 있습니다. ✔ 인쇄 작업 목록의 크기는 bufferSize이고 최대 용량 capacities 만큼 문서를 담을 수 있습니다. 📍 예시 만약, 인쇄 작업 목록의 크기가 2이고 최대 용량이 10Kib라면 크기가 [7, 4, 5, 6] Kib인 문서들이 최단 시간 안에 순서대로 모두 인쇄되는 과정은 다음과 같습니다. 1초가 지나면 인쇄 작업 목록에는 7Kib 크기의 문서가 추가됩니다. 2초일 때 인쇄 작업 목록의 최대 용량이 10Kib이기 때문에 4Kib 문서는 작업 목록에 들어갈 수 없습니다. 동시에 7Kib 문서는 작업 목록에서 1칸 앞으로 이동합니다. 3.. 2021. 10. 9.
Binary Search Tree 구현 : pre-order / in-order / post-order 📌 Binary Search Tree class BinarySearchTree { constructor(value){ this.value = value; this.left = null; this.right = null; } insert(value) { if(value this.value){ if(this.right === null){ this.right = new BinarySearchTree(value); } else{ this.right.insert(value); }.. 2021. 9. 23.
자바스크립트 모든 부분 집합(멱집합) 구하기 📌 멱집합 PowerSet? 구할 수 있는 모든 부분 집합의 집합 === 멱집합 "모든 부분집합 모음"이라고 쉽게 생각하자. 예를 들어, [1, 2, 3, 4, 5]와 같은 배열의 멱집합을 구한다고 한다면, 말 그대로 "부분" 집합이니까 각 요소들은 "있다"vs"없다" 라는 2가지 상태를 지닐 수 있다. 1이 있어도 부분집합, 없어도 부분집합이다. (믿기지 않겠지만 빈 배열도 부분집합으로 친다 !) 그래서 2(가지 상태)^5(요소 개수) 32개의 부분집합을 구할 수 있다. 32개의 부분집합을 모두 담은 집합을 멱집합이라고 할 수 있다. 📌 Tree로 구현하기 DFS완전 탐색을 이용해 그려보면, 일정한 패턴을 볼 수 있다. 왼쪽 노드를 선택했을 때 오른쪽 노드는 선택되지 않는다. "있다"와 "없다" 2가지.. 2021. 9. 7.
백준 자바스크립트 입력 방식 메모 ● test case (1줄 \n1줄 기준) good morning hello world! ● test case 받아오기 // 줄 바꿈 기준으로 가져오기 const fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split('\n'); console.log(input); // ['good morning', 'hello world!'] ● test case (여러줄 \n여러줄 기준) case 1 5 1 2 3 4 5 case 2 4 2 3 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 ● test case 받아오기 const solution = (N, data) => { console.log(N); console... 2021. 9. 4.
01 Big O Notation ( in JavaScript ) Udemy | JavaScript Algorithms and Data Structures Masterclass 01 Big O Notation ● Big O Notation 이란 ?? 좋은 코드, 더 나은 코드란 무엇일까? 란 질문을 던졌을 때 우리는 3가지 정도를 고려해 볼 수 있다. 01 기존 코드보다 처리 속도가 더 빠른가? 02 기존 코드보다 메모리를 덜 잡아먹는가? 03 기존 코드보다 로직이 더 직관적인가? 1번 조건을 평가하기 위해 쓰이는 도구가 바로 Big O Notation이다. "시간 복잡도"라고 부르기도 한다. 알고리즘의 수행 시간을 분석할 때 이 시간 복잡도를 사용한다. 수행 시간은 실행 환경에 따라 다르게 측정되므로, 기본 연산의 실행 횟수로 수행 시간을 평가한다. Big O 표기법.. 2021. 9. 3.

티스토리툴바