본문 바로가기

Algorithm65

[Algorithm] 백준 10818번 최소 최대 문제 Node.js 여러줄 입력 받기 Node.js 여러줄 입력 받는 방법 Node.js 환경에서 터미널 입력을 받기 위해서 사용하는 모듈은 readline 모듈이다. 여러줄 입력을 받기 위해서는 close 이벤트가 emit되기 전까지 입력값들을 한곳에 모아주는 것이다. realine 모듈은 rl.close() 메서드가 실행되기 전까지 계속해서 입력을 받기 때문에 count를 지정해서 입력받을 line 수를 지정할 수 있다. const readline = require('readline'); const { stdin : input, stdout : output } = require('process'); const rl = readline.createInterface({input, output}); let count=0; let inputVa.. 2022. 6. 4.
[Algorithm] Binary Search 알고리즘 Javascript (반복, 재귀, 트리구조) How to Imprement Binary Search Algorithm in Javascript? 이진(이분) 탐색 Binary Search 이진 탐색(Binary Search)란 검색 대상 데이터를 절반씩 나누어 가며 검색하는 방법이다. 데이터를 순차적으로 탐색하는 순차탐색(Linear Search)는 정렬되어 있지 않은 데이터를 검색할 때 유용하지만 시간 복잡도가 O(n)이기 때문에 효율성이 높지 못하다. 이진 탐색을 사용할 경우 데이터를 절반씩 쪼개가며 검색하기 때문에 효율성 면에서 활용도가 높은 편이다. 이진 탐색의 시간 복잡도는 O(LogN)이다. 선행조건 이진 탐색을 수행하기 위해서는 선행조건이 필요하다. 먼저 주어진 데이터의 수를 미리 알고 있어야 한다. 배열로 주어진 경우 arr.leng.. 2022. 6. 3.
[Algorithm] 분할정복 거듭제곱 분할제곱 알고리즘 Javascript 고속 거듭제곱 구하기 거듭제곱을 구하기 위해서 일반적으로 Math.pow() 함수를 사용하거나 거듭제곱 연산자(**)를 사용한다. 하지만 이 경우 시간 복잡도가 O(n)이기 때문에 거듭제곱해야 할 횟수가 늘어나면 날 수록 엄청난 연산수가 필요하다. 즉, 메모리 활용이 비효율적이게 된다. 거듭제곱을 할 때 고속으로 거듭제곱할 수 있는 방법이 있다. 바로 분할제곱 방법이다. 분할제곱에서는 승수가 홀수일 때와 홀수인 경우로 구분해서 빠르게 거듭제곱을 처리할 수 있다. 예를 들어 2^11을 구한다고 하면 11번의 연산이 반복되어야 한다. 하지만 분할제곱의 경우 3번만에 답을 구할 수 있다. 분할제곱 혹은 고속 거듭제곱을 이용할 경우 시간복잡도는 O(Log N)으로 획기적으로 빨라지게 된다. 분할 제곱의 핵심적인.. 2022. 6. 2.
[Algorithm] DFS Tree 순회 알고리즘 DFS 트리 순회 알고리즘 DFS 알고리즘으로 트리 구조를 순회하는 문제는 다양하게 활용된다. 트리 구조에서 각 정점을 순회하는 알고리즘은 크게 DFS와 BFS로 구분된다. 루트 노드 부터 단말 노드까지 순회한 뒤 다음 자식 노드를 순회하는 방식이다. BFS 알고리즘은 루트 노드에 연결된 모든 자식노드를 다 순회한 뒤 다음 레벨의 자식노드를 순회한다. BFS 알고리즘은 최단거리를 구하는 문제에서 사용된다. 현재 연결된 정점을 모두 순회한 뒤 다음 레벨의 정점으로 넘어가는 과정에서 최단거리를 쉽게 구할 수 있기 때문이다. BFS 알고리즘을 구현하는 대표적인 방식은 Queue 자료구조를 이용하는 것이다. 반면 DFS 알고리즘으로 최단거리를 구할 수 있지만 BFS 알고리즘 보다는 더 많은 연산이 필요할 수도 .. 2022. 5. 30.
[Algorithm] SUDOKU Solver 스도쿠 알고리즘 Javascript 문제 스도쿠(sudoku) 는 9x9 로 이뤄진 퍼즐에 1 부터 9 까지 숫자를 입력하는 게임이다. 조건은 가로줄과 세로줄 그리고 각 9칸의 숫자 중 중복이 있어서는 안된다. 일부 비어있는 칸의 배열을 입력받아 스도쿠를 완성하라. 풀이 스도쿠에서 찾아야 하는 숫자는 크게 3개의 조건을 가지고 있다. 먼저 3가지 조건을 비교할 수 있는 2차원 배열을 생성한다. 숫자를 찾는 로직은 유효성 검사 함수와 토글 함수를 사용해서 1부터 9까지 순회하면서 가능한 모든 경우의 수를 비교한다. 만약 숫자를 찾는 과정에서 진행이 불가능한 경우(중복 숫자가 발견되는 경우) 토글 함수를 호출해서 이전상태로 백트래킹을 하면서 새로운 숫자를 찾는 과정을 반복한다. ① 조건 필터 2차원 배열 생성 숫자가 포함된 3x3 박스내에 중.. 2022. 5. 29.
[Algorithm] 동적 계획법 타일링 알고리즘 문제 Javascript 동적 계획법(Dynamic Programming) 동적 계획법은 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각한다. 가장 하위의 케이스의 해를 구하고 큰 문제의 해를 구해나가는 Bottom-up 방식이다. 쉽게 말해서 이전에 했던 계산을 재활용해서 다음 케이스의 답을 구해나가는 과정이다. 동적 계획법 접근 방식은 큰 그림에서 분할정복법(Divide and Conquer)과 유사하다. 분할정복법 또한 이전에 계산했던 풀이를 재활용해서 새로운 문제의 답을 구해나간다. 동적 계획법은 분할정복법과 달리 이전에 풀었던 풀이를 cache에 저장한 후 다음 케이스의 풀이를 구해나간다. 이 때 사용하는 방법이 메모이제이션(Memoization)이다. Tiling 알고리즘 문제 문제 세로 길이 2.. 2022. 5. 26.
[Algorithm] 바코드 문제 DFS 알고리즘 기초 Javascript 문제 1,2,3 으로만 구성된 수열 바코드를 생성해야 한다. 무조건 1,2,3만 붙여서 바코드를 만들면 쉽겠지만, 조건이 붙어있다. 바코드에서 인접한 두개의 부분 수열이 동일한 경우 바코드로 제작할 수 없다. 입력값으로는 바코드의 길이 len이 주어진다. 생성 가능한 바코드 중 가장 작은 바코드를 반환하라. 생성 불가능한 바코드 112 12311231 123131 1212 부분 수열이란 주어진 수열에서 연속된 모든 구간을 의미한다. 인접한 두 부분 수열이란 첫번째 부분 수열과 두번째 부분 수열이 연속된 경우를 의미한다. 자릿수에 상관없이 인접한 부분 수열이 같은 경우 바코드를 생성할 수 없다. 출력 예시 let output = barcode(3); console.log(output); // "121" o.. 2022. 5. 25.
[Algorithm] Advanced Bubble Sort 알고리즘 Javascript 여러 자료를 규칙에 따라 나열하는 정렬 알고리즘은 다양한 종류가 있다. 삽입정렬, 버블정렬, 선택정렬, 쉘 정렬, 힙 정렬, 이진 병합 정렬, 퀵 정렬, 버킷 정렬 등 키값을 비교하는 방식에 따라 다양한 정렬이 있고, 각기 시간복잡도도 다르다. Bubble Sort 알고리즘 버블정렬? 버블 정렬은 각 위치와 인접한 오른쪽 값을 비교해서 데이터를 스왑(swap) 하는 정렬 방식이다. 첫번째 부터 시작한 비교와 스왑을 통해 마지막 위치에 가장 큰 값이 위치하게 된다. 정렬이 끝난 마지막 위치를 제외한 나머지 위치들의 데이터를 다시 순회하면서 정렬 작업을 반복하게 된다. 특정 요소가 오른쪽 값들과 비교하면서 뒤로 밀리는 모습이 거품같다고 해서 버블 정렬이라고 불린다. 버블 정렬의 시간복잡도는 O(n²) 다. .. 2022. 5. 25.
[Algorithm] Javascript BFS / DFS 알고리즘 문제 기초 How to solve DFS / BFS Alogorithm problem in Javascript? 문제 입력값으로 방향이 없는 간선들의 목록이 주어진다. 연결된 정점의 갯수는 몇개인가? 주어진 배열 edges는 시작정점과 도착정점의 정보를 담은 2차원 배열이다. 반환값은 number 타입의 데이터다. 예시 예를 들어 아래와 같은 입력값이 주어진다고 했을 때 그래프를 시각화 하면 다음과 같다. 따라서 결과값은 3이다. const result = connectedVertices([ [0, 1], [2, 3], [4, 5], ]); console.log(result); // 3 소스 코드 구현 그래프 문제는 크게 DFS와 BFS 두가지 알고리즘으로 풀어볼 수 있다. 그 전에 공통적으로 입력받은 2차원 배열.. 2022. 5. 24.
[Algorithm] Javascript Graph 인접 행렬 길 찾기(BFS 알고리즘 기초 문제) 문제 입력값으로 인접행렬인 2차원 배열과 시작정점(from), 도착정점(to)가 주어진다. from 정점으로 부터 to 정점까지 갈 수 있는 경우의 수가 존재하는지 boolan 값으로 반환하라. 예시 const result = getDirections( [ [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0], ], 0, 2 ); 위의 예시를 그림으로 시각화 하면 아래와 같다. 소스코드 구현 이번 문제는 전형적인 BFS(Breadth-First-Seach) 알고리즘 문제다. 주어진 인접행렬의 from 정점부터 시작해서 가능한 모든 정점을 queue에 저장 한 후 queue의 요소들을 순회하면서 최종 도착지점까지의 길이 존재하는지 확인할 수 있다. ① 연결 가능.. 2022. 5. 24.
[Algorithm] Javascript 인접 행렬(Adjacency Matrix) 생성하기 How to implement adjacency matrix in Javascript? 인접행렬 생성하기 문제 입력값으로 방향에 관한 정보와 정점에 관한 정보를 담은 2차원 배열을 받는다. 이를 토대로 인접행렬을 반환하라. 입력값으로 주어지는 2차원 배열은 3가지 정보를 가지고 있다. 0 번째 요소 : 간선의 시작 정점 1 번째 요소 : 간선의 도착 정점 2 번째 요소 : 방향("directed" OR "undirected) 소스 코드 구현 ① 인접 행렬을 구하는 과정은 주어진 입력값 중 가장 큰 수를 구하는 것에서 시작한다. ② max 값을 토대로 인접행렬을 담을 2차원 배열을 생성한다. ③ 방향성에 따라서 간선의 정보를 인접행렬에 좌표를 찍는다. function createAdjacencyMatrix.. 2022. 5. 24.
[Algorithm] Javascript Graph 자료구조 인접 리스트(Adjacency List) 구현하기 Graph 인접 리스트란? 인접 리스트(Adjacency List)는 각 정점이 어떤 정점과 인접하고 있는지를 리스트 형태로 표현한다. 각 정점은 하나의 리스트를 가지게 되며 인접한 다른 정점을 리스트에 담고 있다. 서울 - 부산 - 제주, 3개의 정점이 있다고 가정하자. 서울은 부산으로의 간선을 가지고, 부산은 제주로의 간선을 가지며, 제주는 서울로의 간선을 가지게 된다. 위 그래프를 인접 리스트로 구현하면 다음과 같다. 그래프 자료구조에서 인접 리스트는 객체로 구현된다. 각 정점은 Key값이 되고 정점과 연결된 간선들의 정보는 배열로 Value 값이 된다. 굳이 인접행렬을 사용하는 이유? 그래프 자료구조에서 정점과 간선의 정보를 담기 위해서 일반적으로 인접행렬을 사용한다. 하지만 인접행렬의 가장 큰 .. 2022. 5. 24.
[Algorithm] Javascript Graph 자료구조 인접행렬(Adjacency Matrix) 구현하기 How to implement Graph Data Structure in Javascript? Graph 인접행렬 구현하기 그래프(Grpah) 자료구조는 노드를 간선으로 연결해 관계를 표현할 수 있는 자료구조다. 네비게이션에서 최단거리를 구하는 알고리즘을 구현할 때 그래프 자료구조를 사용한다. 정점(Vertex)와 간선(Edge)로 구성된다. 그래프 자료구조는 크게 방향성 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분된다. 또한 그래프 자료구조는 모든 정점을 순회하기 때문에 루트 노드, 부모 노드, 자식 노드의 개념이 없다. [Algorithm] Javascript Graph Data Structure 그래프 자료구조 알고리즘 Javascript Graph D.. 2022. 5. 24.
[Algorithm] Javascript Tree 자료구조 구현하기 (소스코드 포함) Tree 자료구조 구현하기 Tree 자료구조는 데이터를 계층적으로 표현하기 위한 자료구조다. 하나 이상의 노드를 가지고 있으며 각 노드들은 간선(Edge)로 연결된다. 방향성이 있는 비순환 그래프의 한 종류로 3가지 트리 종류가 있다. 이진 트리(Binary Tree) : 자식 노드 수가 최대 2개인 트리 포화 이진 트리(정 이진 트리 Full BInary Tree) : 모든 레벨에서 노드가 꽉 채워진 트리다. 단말노드(Leaf Node)를 제외한 모든 노드의 자식 노드가 2개인 트리. 완전 이진트리(Complete Binary Tree) : 단말노드(Leaf Node)를 제외한 모든 노드가 꽉 채워진 형태의 트리 Tree 자료구조는 2개의 멤버변수와 2개의 메소드를 가진 클래스로 구현이 가능하다. 소스.. 2022. 5. 24.
[Algorithm] 시간복잡도 개선 부분집합 문제 문제 두개의 배열 base, sample을 입력받아 sample이 base의 부분 집합인지 여부를 확인 후 boolean값을 반환하라. base, sample 배열은 number 타입 요소를 가진다. 제약조건 base.length > 70,000 sample.length > 70,000 소스코드 구현 첫번째 솔루션 시간복잡도를 고려하지 않는다면 단순하게 문제를 풀 수 있다. 두개의 반복문을 순회하면서 sample의 요소와 base 요소를 비교하면서 결과값을 result 배열에 담아 출력하면 된다. const isSubsetOf = function (base, sample) { let result = new Array(sample.length).fill(false); for(let i=0; ia-b); ②.. 2022. 5. 24.

티스토리툴바