본문 바로가기

🧠 알고리즘31

[프로그래머스]광물 캐기 JS 맨처음에는 DFS로 접근했는데 뭔가 잘못 짰는지 시간 초과가 났다 그래서 그리디로 접근했다 💡접근방식 광물은 순서대로 캐야 하지만 곡괭이 순서는 상관이 없으므로 광물을 5개씩 묶음으로 잘라서 돌곡괭이 피로도 순으로 정렬해준다 곡괭이로 캘 수 있는 만큼 광물 묶음을 잘라준다 가지고 있는 곡괭이로 광물을 다 캐지 못할 수 있기 때문에 캘 수 없는 광물은 제거 피로도 순으로 정렬된 광물 묶음을 다이아 > 철 > 돌 곡괭이 순으로 캐기 function solution(picks, minerals) { //곡괭이 수 let pickCnt = picks.reduce((acc,cur)=>acc+cur, 0); //최종 피로도 let result=0; const pick = ['diamond', 'iron', 'sto.. 2023. 12. 27.

[프로그래머스] 소수찾기 JS 💡접근방법 numbers 배열에서 만들 수 있는 모든 숫자들을 찾기 해당 숫자가 소수인지 판별 중복되는 숫자가 있을 수 있으므로 set 사용 function solution(numbers) { const numArr = numbers.split(''); let visited = new Array(numbers.length).fill(false); const resultSet = new Set(); function isPrime(num){ if(num 2023. 12. 27.

[프로그래머스] 여행경로 JS 접근방법💡 모든 티켓들의 출발지를 키값으로 하는 인접리스트를 만들기 알파벳 순으로 정렬 dfs로 탐색 탈출 조건은 경로의 길이가 tickets의 length와 같을 때 function solution(tickets) { const adjacencyList = {}; let result=[]; //인접리스트 [key=출발지]:도착지[] tickets.forEach(t=>{ const [dep, arr]=t; const tmp=adjacencyList[dep]||[]; tmp.push(arr); adjacencyList[dep]=tmp; }); //알파벳 순으로 정렬 for(key in adjacencyList){ adjacencyList[key].sort(); } //재귀함수 dfs //path=지금까지의.. 2023. 12. 27.

[프로그래머스] 타겟 넘버 JS 💡접근 방식 1. 숫자 앞의 부호만 +,-로 바꿔주면 된다(이진트리 생각하기) 2. dfs로 모든 경우의 수 찾아주기 3. numbers의 마지막에 도달했을 때 return; function solution(numbers, target) { let answer = 0; //level=numbers 배열 요소 인덱스(트리에서 level) function dfs(level, sum){ //탈출 조건 if(level===numbers.length){ if(sum===target){ answer++; } return; } dfs(level+1, sum+numbers[level]); dfs(level+1, sum-numbers[level]) } dfs(0,0); return answer; } https://sch.. 2023. 12. 27.

[프로그래머스]두 원 사이의 정수 쌍 JS 💡접근방법 원의 방정식 활용하기! (x-a)^2 + (y-b)^2 = r^2 원의 중심이 원점이기 때문에 x^2 + y^2 = r^2 원의 방정식을 활용해서 x값에 따른 원의 y값을 구하기 각 x값에 따른 점의 범위 작은 원의 y값 2023. 12. 27.

[프로그래머스]연속된 부분 수열의 합 JS 💡접근 방식 투포인터 시작 포인터와 끝 포인터 두 가지를 사용하면서 범위를 넓혀나갑니다. 포인터 사이의 모든 원소의 합이 k이하면 끝 포인터 값을 늘리고 k초과면 시작 포인터 값을 늘리기 function solution(sequence, k) { //투포인터 //시작 포인터와 끝 포인터 두 가지를 사용하면서 범위를 넓혀나갑니다. //포인터 사이의 모든 원소의 합이 k이하면 끝 포인터 값을 늘리고 //k초과면 시작 포인터 값을 늘리기 let start = 0; let end = 0; let sum = sequence[0]; let range = [-Infinity, Infinity]; //끝 포인터가 배열의 범위를 벗어나면 탈출 = sum이 k보다 작기 때문에 while (end < sequence.len.. 2023. 12. 27.

이전 1 2 3 4 5 6 다음

티스토리툴바