dfs
-
[CodeKata] 프로그래머스(Lv3) : 사라지는 발판Algorithm 2022. 4. 24. 03:02
🥋 Oooth More!! (Level 3) 🧮 풀이 DFS를 적용해야한다고 생각은 했지만, A와 B가 최적의 경로로 이동하는것을 어떻게 반영할지에 대해 감이 잡히질 않았다. (완전탐색을 통해 해결해야 한다) 🖇 리뷰 위에서 언급했듯, 완전탐색을 통해 A와 B가 모든 경로를 우선 방문한다. 탐색하면서 A 또는 B는 각자 이기거나 질 수 있는 사람인데, 이길수 있는 사람은 최소로, 질 수 있는 사람은 최대로 이동경로를 이동하려한다. const solution = (board, aloc, bloc) => { const dx = [0, 0, 1, -1] const dy = [1, -1, 0, 0] const yMax = board.length const xMax = board[0].length const df..
-
[CodeKata] 프로그래머스(Lv3) : 양과 늑대(KAKAO)Algorithm 2022. 4. 2. 19:25
🥋 Oooth More!! (Level 3) 🧮 풀이 이진트리 문제이기 때문에 난이도가 있을거라고 생각했지만, DFS를 적용해서 풀 수 있었던 문제였다. 🖇 리뷰 function solution(info, edges) { let answer = 1; const length = info.length; const graph = Array.from({length}, () => []); for(let i = 0; i { let [currentNode, sheep, wolves] = current; const newN..
-
[CodeKata] 프로그래머스(Lv3) : N-QueenAlgorithm 2022. 3. 26. 21:10
🥋 Oooth More!! (Level 3) 🧮 풀이 DFS를 통해 문제를 풀이해보았다. 처음엔 n x n의 2차원 board를 넘기려했으나 n에 따라 시간복잡도가 제곱배로 증가할 것으로 예상되었고 1차원 배열로 Queen들의 좌표를 관리했다. function solution(n) { let answer = 0; function dfs(queens, row) { if (queens.length === n) { answer++; return; } for (let col = 0 ; col Math.abs(qc-col) === row - qr).length > 0) continue; dfs..
-
[CodeKata] 프로그래머스(Lv3) : 하노이의 탑Algorithm 2022. 3. 20. 17:28
🥋 Oooth More!! (Level 3) 🧮 풀이 하노이의 탑 공식을 찾아보니, 아래와 같은 프로세스였다. 이를 재귀함수로 구현하는 것을 못하여 모범답안을 참고하였다. A기둥의 (n-1)번째 원판을 B기둥으로 이동시킨다. A기둥의 n번째 원판을 C기둥으로 이동시킨다. B기둥의 (n-1)번째 원판을 C기둥으로 이동시킨다. 🖇 리뷰 function solution(n) { let answer = []; const hanoi = (n, start, mid, end) => { if (n === 1) answer.push([start,end]) else { hanoi(n-1, start, end, mid) answer.push([start,end]) hanoi(n-1, mid, start, end) } } h..
-
[CodeKata] 프로그래머스 : 7.19(월), 여행경로 / 베스트앨범Algorithm 2021. 7. 20. 21:56
🥋 Oooth More!! (Level 3) : 여행경로 🧮 풀이 function sortTickets(list) { return list.sort((a,b) => { return a[1] < b[1] ? -1 : 1; }) } function solution(tickets) { let answer; function dfs(acc, res) { if (res.length === 0) { answer = [answer, acc].sort().shift(); return; } const now = acc[acc.length-1]; for (let i in res) { const [d, a] = res[i]; if (d === now) { const copiedRes = [...res]; const [next..