Algorithm
-
[CodeKata] 프로그래머스 : 7.10(토), 경주로 건설Algorithm 2021. 7. 10. 17:30
🧮 풀이 DFS로 초기 접근했으나, 최단경로를 구해야하므로 BFS로 변환해서 구현해보다가 모범답안 풀이를 하게 되었다. 🖇 리뷰 모든 노드에 이동하는 최소 건설비용을 저장하는 BFS + 다익스트라 알고리즘 을 활용했다. function solution(board) { let answer = 987654321; const dy=[1,0,-1,0]; const dx=[0,1,0,-1]; const len=board.length; const arr=Array.from(Array(board.length),()=>Array(board.length).fill(0)); const queue=[]; const bfs=()=>{ queue.push([0,0,1,0]); queue.push([0,0,0,0]); while..
-
[CodeKata] 프로그래머스 : 7.3(토), 합승 택시 요금Algorithm 2021. 7. 4. 21:48
🥋 Oooth More!! (Level 3) 🧮 풀이 각 경로별로 최단비용을 계산하는 플로이드-와샬 알고리즘을 기반으로 푸는 문제임을 인지했다. 하지만, 구체적인 풀이를 구현하지 못해 모범답안을 분석하였다. 🖇 리뷰 function solution (n, s, a, b, fares) { const board = new Array(n).fill().map(_ => new Array(n).fill(Infinity)); for(let i = 0; i { const [x, y, weight] = pos; board[x-1][y-1] = weight; board[y-1][x-1] = weight; }); for(let k = 0..
-
[CodeKata] 프로그래머스 : 6.19(토), 다단계 칫솔 판매 / 단어 변환Algorithm 2021. 6. 14. 19:18
🥋 Oooth More!! (Level 3) : 다단계 칫솔 판매 문제가 길지만 그림을 보면 이해하기 편하다. 트리 기반 문제로, enroll과 referral 배열끼리 대칭되며 하위-상위 요소의 관계가 성립된다. seller와 amount 배열도 대칭되며, amount는 판매한 수량이므로 map() 을 통해 *100 을 하여 가격으로 만들어주면 좋을 것 같다. 마지막으로, seller의 각 요소들부터 트리를 타고 올라간다. 상위에 10%, 본인은 90%를 분배하는 식으로 최상위 노드까지 올라간다. 이렇게 했을 때, 트리의 모든 노드들(enroll) 개개인의 수입의 총합이 얼마인지를 계산하면 된다. 🧮 풀이 DFS의 방법으로 풀어보았으나, 케이스 10~12번에서 런타임 에러 및 시간초과가 발생하여 개선된..
-
[CodeKata] 프로그래머스 : 6.11(금), 보석 쇼핑 / 이중우선순위큐Algorithm 2021. 6. 10. 14:17
🥋 Oooth More!! (Level 3) : 보석 쇼핑 🧮 풀이 DFS, BFS, 순회 등 다양한 방법으로 풀었지만 정확성 일부오답과, 효율성 시간 초과 등이 있어 좋은 모범답안을 해석했다. 🖇 리뷰 function solution(gems){ var count = new Set(gems).size; // 보석 종류가 몇개인지 var gemMap = new Map() // 보석 종류 => 보석 자리를 저장하기 위한 맵 var gemLength = [] // 보석을 모두 포함하는 구간을 저장할 배열 gems.forEach((gem, i)=> { gemMap.delete(gem) gemMap.set(gem, i) if(gemMap.size === count){ gemLength.push([gemMap.v..
-
[CodeKata] 프로그래머스 : 6.5(토), 셔틀버스Algorithm 2021. 6. 6. 17:50
🥋 Oooth More!! (Level 3) * 해설링크 : https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ 🧮 풀이 해당풀이로 풀었으나, 정답률이 87.5로 나왔다. (몇 가지 예외처리가 잘 안된듯) function toMinute(time) { time = time.split(":"); return time[0] * 60 + Number(time[1]) } function toTime(m) { return String(Math.floor(m/60)).padStart(2,'0') + ":" + String(m%60).padStart(2,'0') } function solution(n, t, m, timetable) { let kor..
-
[CodeKata] 프로그래머스 : 5.30(일), 순위 & 불량 사용자Algorithm 2021. 6. 1. 01:40
🥋 Oooth More!! (Level 3) : 순위 * 출처 : http://contest.usaco.org/JAN08.htm 🧮 풀이 그래프와 DFS를 통해 풀어보려 했으나 오답률이 높아, 모범답안을 보고 해석리뷰를 하였다. 🖇 리뷰 function solution(n, results) { var answer = 0; const graph = Array.from({ length: n+1 },() => Array(n+1).fill(false)); results.map((item) => { const [win,lose]=item; graph[win][lose]=1; //이긴 경우 1 graph[lose][win]=-1; //졌을 경우 -1 graph[win][win]=0;//자기자신 graph[lose]..
-
[CodeKata] 프로그래머스 : 5.21(금), 디스크 컨트롤러Algorithm 2021. 5. 21. 18:30
🥋 Oooth More!! (Level 3) 🧮 풀이 확실히 3단계에 들어오면서 알아야 할 자료구조도 많다. 이번 우선순위 큐 문제도 그리하여, 모범답안과 함께 개념을 공부하였다. 🖇 리뷰 - 풀이 function solution(jobs) { var answer = 0; jobs.sort((a,b)=>a[0]-b[0]);// 첫 작업은 가장 먼저오는 걸로 const pq=[];//우선 순위 큐 (시작이 가능한 일들이 들어가며 작업시간 오름차순정렬됨) let i=0, time=0; while(i 자식노드가 부모 노드보다 무조건 크거나 작다. 하지만, 전체트리에서 가장 아래노드가 가장 크거나 작은 값은 아니라는 의미 * 최대 힙(Max Heap) : 부모 노드는 항상 자식 노드보다 크거나 같다. * 최소 ..
-
[CodeKata] 프로그래머스 : 5.12(수), 입국심사Algorithm 2021. 5. 12. 17:37
🥋 Oooth More!! (Level 3) * 출처링크 : hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf 🧮 풀이 * 6, 9번에서 실패가 발생하였다. function solution(n, times) { let min = 0; let max = n * Math.min.apply(null, times); while (max - min >= 0) { const mid = Math.floor((max - min) / 2) + min; const totalTime = times.reduce((acc, cur) => acc + Math.floor(mid/cur), 0); if (totalTime < n) { min = mid + 1; } else if (totalTi..