목록알고리즘 (26)

프린세스 다이어리

[Algospot] 고대어 사전 문제 자바스크립트 풀이

1. 풀이 순서 문제 입력에 따라 2차원 배열을 만들어주는 함수를 하나 만든다.(makeGraph) dfsAll() 수행하여, dfs() 종료 시마다 현재 정점을 기록한다.(order) 위상정렬 결과를 얻기 위해 그 기록을 뒤집어서 결과를 도출한다.(order.reverse()) 추가로 DAG 조건에 부합하는지 검사하여 예외처리 한다. 2. 해답 const makeGraph = (numOfTest, words) => { // 1. 2차원 배열을 26*26 크기로 초기화해줌. let graph = Array.from(Array(26), () => Array(26).fill(0)); // 2. 들어온 단어들을 돌아줌. 이 케이스에서는 나름의 알파벳 순서대로 정렬돼 있으므로 지금거([j])랑 이전거([j-1=..
자료구조, 알고리즘 2022. 4. 17. 17:58
[LeetCode] Fibonacci Number - 자바스크립트 풀이

문제 링크 1. 접근 방법 (1) 이전에 계산해 둔 결과를 활용하여 지금 연산을 하는 메모이제이션 방식이다. (2) cache 객체를 만들어 놓고, 함수를 재귀적으로 실행할 때 cache에 해당 값이 이미 존재하면 그 값을 리턴한다. if (Object.keys(cache).includes(n)) { return cache.n; } (3) cache에 해당 값이 없으면, 값을 리턴한다. 피보나치 배열에서는 인덱스 0, 1은 각각 값이 0과 1이고, 그 다음 인덱스부터는 이전 인덱스에 해당하는 값과 이이전 인덱스에 해당하는 값을 더한 값이 할당된다. if (n < 2) { result = n; } else { result = recur(n - 2) + recur(n - 1); } (4) cache에 인덱스..
자료구조, 알고리즘 2021. 12. 5. 23:01
[LeetCode] Search in a Binary Search Tree - 자바스크립트 풀이

문제 링크 1. 접근 방법 (1) 이진탐색트리에서 루트를 기준으로 왼쪽 노드의 value는 작은 수, 오른쪽 노드의 value는 큰 수다. 이 특성을 이용해서 재귀로 풀면 된다. (2) 찾는 val이 루트의 value보다 크면 오른쪽을 재귀로 탐색한다. (3) 찾는 val이 루트의 value보다 작으면 왼쪽을 재귀로 탐색한다. if (root.val < val) { return searchBST(root.right, val); } else { return searchBST(root.left, val); } (3) edge case 예외처리 해 준다. if (!root) return null 2. 전체 해답 /** * Definition for a binary tree node. * function Tre..
자료구조, 알고리즘 2021. 11. 30. 18:17
[LeetCode] Swap Nodes in Pairs - 자바스크립트 풀이

1. 접근 방법 (1) 종료조건이 있고 반복되는 연산이 있으므로 재귀로 풀 수 있다. (2) 앞에 두 노드를 바꾸고 + 나머지 리스트를 합친다. 그리고 그 나머지 리스트 중 앞에 두 노드를 바꾸고 + 나머지의 나머지 리스트를 합친다. 결국, 한 단계 내에서 수행할 연산은: 앞에 두 노드를 바꾸고 + 두번째 노드에 나머지 리스트를 합치는 작업이다. let temp = head.next; head.next = temp.next; temp.next = head; head.next = swapPairs(head.next) (3) 예외처리를 추가한다. 앞의 두 노드의 위치를 바꿀 필요가 없는 경우는 그냥 리턴해준다. if (head == null) return head; if (head.next == null) ..
자료구조, 알고리즘 2021. 11. 30. 08:53
[LeetCode] Valid Perfect Square - 자바스크립트 풀이

1. 접근 방법 mid의 제곱이 바로 찾는 값이 되면 true를 반환하고, 이진탐색으로 left와 right를 옮겨가며 마지막까지 남은 mid값이 조건을 충족하지 않는다면 false를 반환한다. 2. 전체 풀이 /** * @param {number} num * @return {boolean} */ var isPerfectSquare = function(num) { if (num === 1) return 1; let left = 1; let right = Math.floor(num / 2); while (left
자료구조, 알고리즘 2021. 11. 29. 18:42
[LeetCode] Pow(x, n) 문제 - 자바스크립트 풀이

문제 링크 1. 접근 방법 (1) 이진탐색 분야로 구분돼 있으나 도무지 이진탐색이 떠오르지 않아 재귀로 풀었다. 연산을 쪼개어 작은 연산의 결과를 다음 연산에도 계속 쓰기 때문에 재귀가 잘 어울리는 문제다. (2) 분할정복의 원리를 이용하여 시간복잡도 O(logN)로 풀어낼 수 있다. 거듭제곱을 이용하여(x^4 * x^4 = x^8 이 되는 원리) 풀면 속도가 한 번 당 절반으로 줄어든다. 그냥 단순 반복문 O(N)으로 풀어도 되기는 하는데 주어지는 값의 범위가 너무 커지면 시간초과가 날 수 있다. n이 짝수면 절반으로 줄여서 제곱하고, n이 홀수면 1 뺀 값을 절반으로 줄여서 제곱한 후, 한 번 x를 추가로 곱해서 리턴한다. if (n % 2 === 0) { const answer = getPow(x,..
자료구조, 알고리즘 2021. 11. 29. 12:22
[LeetCode] Find K Closest Elements - 자바스크립트 풀이

문제 링크 1. 접근 방법 (1) 주어지는 배열이 오름차순 정렬돼 있고, 특정 조건에 따라 피벗 값을 기준으로 검사 위치를 변경해가며 푸는 문제이므로 이진 탐색 문제다. (2) left는 나중에 slice할 범위의 왼쪽 끝 인덱스다. (3) right가 arr.length - k로 초기화되어 있는 이유는 left 인덱스로부터 k만큼 자르기 위해 가능한 최대 인덱스이기 때문이다. let left = 0; let right = arr.length - k; (4) left
자료구조, 알고리즘 2021. 11. 28. 23:31
[LeetCode] Search for a Range - 자바스크립트 풀이

문제 링크 두시간 가까이 걸림.. 1. 접근 방법 (1) 중복을 허용한 오름차순 배열이 주어지고 + O(logN) 시간복잡도로 풀으라고 했으며 + 피벗을 기준으로 왼쪽과 오른쪽의 값을 비교해야 하는 문제이므로 이진탐색으로 푼다. (2) getIndex 라는 함수를 만들어서, 배열, 타깃, isLeftArray를 파라미터로 받아 주어진 타깃 범위의 첫 인덱스 또는 범위의 마지막 인덱스를 리턴하도록 한다. const getIndex = (nums, target, isLeftIndex) => { if (nums.length === 0) return -1; let left = 0; let right = nums.length - 1; let mid = 0; if (isLeftIndex) { // ... } els..
자료구조, 알고리즘 2021. 11. 28. 17:32
Prev 1 2 3 4 Next