알고리즘

leetcode 코딩테스트 연습 - 2666. Allow One Function Call (JavaScript)

이 문제는 클로저를 활용하여, 단 한 번만 호출되는 함수를 만드는 것이 목적이다. isCalled라는 변수를 사용하여 한 번 호출된 뒤에는 다시 호출될 수 없도록 문제를 해결하였다. var once = function(fn) { let isCalled = false; return function(...args){ if(!isCalled) { isCalled = true; return fn(...args); }else { return; } } }; 자바스크립트의 함수 특징을 사용한 문제였다.

BFS(Breadth-First Search) 알고리즘 구현하기 (자바스크립트)

BFS는 최단 경로를 탐색하기 위해서 많이 사용되는 알고리즘으로, DFS와는 다르게 인접한 노드를 순서대로 방문하지만 각 인접 노드의 자식을 방문하는 건 나중에 이루어진다. 자바스크립트로 이를 구현해보면 다음과 같다. // 그래프의 인접 리스트 표현 const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E'] }; function bfs(graph, startNode) { const visited = new Set(); // 방문한 노드를 저장하는 Set const queue = [startNode]; // 탐색할 노드를 저장하는 큐 visited.add(startNode); /..

leetcode 코딩테스트 연습 - 2621. Sleep (JavaScript)

/** * @param {number} millis */ async function sleep(millis) { return new Promise((resolve, reject) => { const timer = setTimeout(() => { resolve(millis); }, millis); }) } /** * let t = Date.now() * sleep(100).then(() => console.log(Date.now() - t)) // 100 */ leetcode의 문제들은 생각보다 다양한 것 같다. async 함수를 구현해야하는 코딩테스트 연습문제는 처음 접한 것 같다. 어려운 문제는 아니었지만, Promise를 반환하는 함수의 리마인드를 할 수 있었다.

leetcode 코딩테스트 연습 - 2722. Join Two Arrays by ID (JavaScript)

이번 문제는 객체를 값으로 가지는 두 배열을 합치는 문제였다. 객체의 id값은 유일해야 하고 양 배열에 id가 같으면, 이 객체를 합해야 하는 문제였다. 문제 접근 자체는 어렵지 않았지만, Time Limit Exceeded을 맞이해버렸다. /** * @param {Array} arr1 * @param {Array} arr2 * @return {Array} */ var join = function(arr1, arr2) { const answer = [...arr1]; const memo = {} for(let el of arr2) { if(el.id >= 0) { let pointer = null; if(memo[el.id] >= 0) { pointer = memo[el.id]; } else { for(..

leetcode 코딩테스트 연습 - 2624. Snail Traversal (JavaScript)

이번 문제는 Array의 prototype에 고차 함수를 직접 구현하는 문제였다. this가 호출한 배열을 가르킨다는 것을 이번 문제를 해결하면서 처음 알게되어 의미가 깊다. /** * @param {number} rowsCount * @param {number} colsCount * @return {Array} */ Array.prototype.snail = function(rowsCount, colsCount) { if(rowsCount * colsCount !== this.length) { return []; } const result = []; for(let i = 0; i < rowsCount; i++) { result.push([]); } let row = 0; let isAscending =..

leetcode 코딩테스트 연습 - 1844. Replace All Digits with Characters (JavaScript)

지금까지 프로그래머스를 이용하여 코딩테스트 문제를 풀어왔는데, 이번에는 leetcode를 이용하기로 하였다. 영어로 되어 있어 영어 공부를 할수도 있고, 문제가 다양하며 제출한 정답의 런타임이나 메모리 사용량도 알려주는 장점이 있는 플랫폼이다. 이번에 풀어본 문제는 간단한 문제로 아스키 코드를 이용한 문제였다. 자바스크립트에서 아스키 코드의 사용은 다소 생소하였기에 (C언어에서는 문자열이 숫자처럼 계산되었던 기억이 있다) 검색을 통해서 String.fromCharCode()나 char.charCodeAt() 과 같은 메서드를 알아내었다. /** * @param {string} s * @return {string} */ var replaceDigits = function(s) { let answer = "..

프로그래머스 코딩테스트 연습 - 롤케이크 자르기 JavaScript

이번 문제는 간단하게 생각하면, 이중 for문을 사용하여 계산할 수 있는 문제였다. 본질적으로 배열을 둘로 나누어 양 쪽의 값을 비교하는 문제였다. 따라서, 시간초과를 내지 않으며 문제를 해결하기 위해서 객체를 사용하여 배열의 데이터를 관리하였다. function solution(topping) { let answer = 0; const left = {}; let leftCount = 0; const right = {}; let rightCount = 0; topping.forEach(el => { if(!left[el]) { left[el] = 1; leftCount++; } else { left[el] += 1; } }); for(let t of topping) { if(right[t]) { righ..

자바스크립트 최단거리 알고리즘 (다익스트라 알고리즘, Dijkstra)

최단거리를 구하는 알고리즘은 다양한 방법으로 구현할 수 있다. 최단거리 알고리즘은 코딩테스트에서도 많이 사용되고, 생각보다 최단거리를 구해야할 경우가 종종 있기에 이번 기회에 정리하도록 하였다. 이번에는 자바스크립트로 가장 기본적인 최단거리 알고리즘 방법인 다익스트라(Dijkstra) 알고리즘을 구현해보도록 하였다. 🥩 다익스트라 알고리즘은 최단거리를 구하는데 사용되는 대표적인 알고리즘 중 하나이지만, 그 외에도 벨만-포드 알고리즘, A* 알고리즘, 플로이드-워셜 알고리즘 등 다양한 알고리즘을 통해서 최단거리를 구할 수 있다. 🧀 알고리즘의 선택은 문제의 제약사항과 성능 요구사항에 따라 달라질 수 있다. 다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘으로 아래는 다..