본문 바로가기

알고리즘/리트코드

 (18)
289. Game of Life 각 칸에 이웃하는 주민의 수를 구해야하고, 그 주민수를 저장해놓고 비교할 때 사용해야한다. 따라서 객체에 저장을 해놓고 사용했다. 이웃하는 주민이 2보다 작거나, 3보다 크다면, 그 칸을 0으로 바꿔준다. 만약 3이라면 1로 바꿔준다. const gameOfLife = function(board) { const hash = {}; const directions = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]]; for (let r = 0; r < board.length; r++) { for (let c = 0; c < board[r].length; c++) { let numLiveNeighbors = 0; for (let [x, y] of..
704. Binary Search O(log n ) . 문제이름도 이진탐색이다. const search = function(nums, target) { let start = 0,end = nums.length-1 while(start
62. Unique Paths 우선 m이 row를 뜻하므로 1줄이라면 별까지 가는 경우의 수는 1개일 수밖에 없다. 1줄이 아니라면 옛날에 그 미로찾기같은거 할 때 경우의 수 구하는 방법에서 여기까지 오는데 가능한 경우의 수를 써놓고 한칸전진하면 이전 경우의 수들 더해서 작성하는 그 방식으로 문제를 풀었다. const uniquePaths = function(m, n) { if (m == 1) return 1; const arr = Array.from ({length: m}, () => Array.from ({length: n} , () => 0)) for (let i = 0 ; i < n ; i++) { arr[0][i] = 1 } for (let i = 0 ; i < m ; i++) { arr[i][0] = 1 } for (let..
46. Permutations 파이썬으로 재귀 구현할 때랑 다른 느낌이다. JavaScript로 알고리즘문제풀이가 더 익숙해지도록 문제를 더 많이 풀어야겠다. 배열에 원소가 있으면 넘어가고 없으면 추가해준후 dfs를 돌렸다. const permute = function(nums) { const res = [] dfs(res, [], nums) return res }; const dfs = (res, arr, nums) => { if (arr.length === nums.length) { res.push([...arr]) return } nums.forEach(n => { if (!arr.includes(n)) { dfs(res, [...arr, n], nums) } }) }그냥 for문이 더 깔끔한 느낌이다. const permute..
53. Maximum Subarray 처음엔 간단한듯 싶다가도 약간 해맸다. const maxSubArray = function(nums) { for (let i = 1; i < nums.length; i++) { nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]); } return Math.max(...nums) };
187. Repeated DNA Sequences 완전 탐색을 선택했다. Set, Map은 이터러블이므로 Array.from 으로 배열로 바꿀 수 있다. const findRepeatedDnaSequences = function(s) { if (s.length < 10) return [] let set = new Set(), res = new Set() let start = 0 for (let end = 9; end < s.length; end++) { let substr = s.substring(start, end + 1) if (set.has(substr)) res.add(substr) else set.add(substr) start++ } return Array.from(res) } const findRepeatedDnaSequences = fun..
127. Word Ladder 문제의 조건에서 중요한 점 시작 단어는 리스트에 들어가지 않는다. 한번에 하나의 단어만 바뀔 수 있다. 끝 단어가 단어리스트에 존재해야만 한다. 없을시 0 리턴 bfs인데 다음 원소가 조건에 따라 달라지는 형태의 bfs 한번의 bfs에서 될 수 있는 모든 단어를 찾아야한다. 따라서 for문의 첫번째는 단어 두번째는 모든 알파벳에 대하여 탐색한다. 그리고 변할 수 있는 단어를 찾으면 그 단어를 set에서 지운다. const ladderLength = function (beginWord, endWord, wordList) { // 없으면 컷. if (!wordList.includes(endWord)) return 0 const wordSet = new Set(wordList) let queue = [begi..
136. Single Number 느낌이 다른 풀이 3가지 const singleNumber = function(nums) { const obj = {} for (let num of nums) { obj[num] ? obj[num]++ : obj[num] = 1 } for (const [k, v] of Object.entries(obj)) { if (v == 1) { return k } } };function singleNumber(nums) { const map = {}; for (let n of nums) { if (map[n] == null) map[n] = 0; map[n]++; } for (let n in map) { if (map[n] === 1) return Number(n); } }const singleNumber = fu..

티스토리툴바