본문 바로가기

🧠 알고리즘31

[백준] 도로의 개수 1577 JS 문제 해결 방식 우선 N,M의 범위가 100이하여서 n^2으로 풀었습니다. DP문제라고 판단하여 테이블로 값을 갱신하면서 풀었습니다 (0,0)에서 시작해서 (N,M)까지 가는 최단거리이기 때문에 우상단을 향해 가는 값들만 고려했습니다. DP[i][j] = DP[i][j-1] + DP[i-1][j]; 그중에서 공사 중인 길은 제외하고 값을 더해나갔습니다. 로직 상에는 문제가 없는 것 같았는데 제출을 하자마자 다 틀리더라구요 알고보니 경로를 set에 저장할 때 키값의 문제였습니다 처음에는 ${a}${b}${c}${d} 이런 식으로 키값을 줬었는데 구분자 없이 키값을 주니 a,b,c,d값이 다름에도 같은 값으로 인식되어서 틀린 것 같아요 const filePath = process.platform === 'l.. 2024. 1. 29.

[프로그래머스] 마법의 엘리베이터 JS 문제링크 풀이 방법 처음에는 한 번 bfs로 해봤는데 수가 커서 그런지 2개 빼고 다 시간초과가 걸리더라구요 그냥 규칙을 찾아서 카운트 해줬습니다 고려해야 하는 점은 수가 5일 때였습니다. 수가 5일 때 다음 자리수가 5 이상이면 +5를 더해서 다음 자리수를 +1 해주고 다음 자리수가 5 미만이면 -5 해줬습니다 5보다 큰 경우에는 무조건 다음 자리 값을 올려줬습니다 만약 마지막 자리수인 경우에는 1을 푸쉬해서 자리수를 올려줬습니다 function solution(storey) { let cnt=0; const storey_arr = String(storey).split('').map(Number).reverse(); for(let i=0;i 2024. 1. 12.

[프로그래머스] 숫자 변환하기 JS 풀이방법! bfs로 배열값을 갱신하면서 풀었습니다 x에서부터 3가지 방법으로 갈 수 있는 값들을 방문하면서 횟수가 적으면 table을 갱신하고 큐에 넣어주었습니다. 그런데 생각해보니 배열값을 최소값으로 갱신하는게 아니라 true,false로 방문 여부만 갱신해도 상관없는 전형적인 bfs 문제였습니다 그리고 이번 문제는 배열의 shift를 사용하는 경우 시간초과가 발생해서 직접 큐를 구현했습니다 예전에 백준에서 https://www.acmicpc.net/problem/13549 숨바꼭질 3 문제를 풀었는데 이 문제의 경우는 이동할 때 0초가 걸리는 경우가 있어서 최소값을 갱신하면서 풀었습니다 문제의 조건을 잘 생각하면서 풀어야겠네요 최소값 갱신 function solution(x, y, n) { //bfs.. 2024. 1. 11.

[프로그래머스] 택배 배달과 수거하기 JS 문제 링크 간단해 보이는데 엄청 오래 걸렸습니다..!! 우선 최소로 움직이기 위해서는 최대한 먼 곳부터 많이 배달하고, 먼 곳부터 많이 수거해야 합니다 가장 멀리에 있는 배달,수거 장소에서부터 배달과 수거를 cap만큼 진행합니다 배달과 수거를 모두 cap만큼 진행하는 것은 갈 때 cap만큼 배달하고, 올 때 cap만큼 수거하면 되기 때문입니다 deliveries 배열과 pickups 배열이 존재하는 동안 배달, 수거 2개의 함수를 만들어서 먼 곳부터 배달과 수거를 반복했습니다 둘 중 시작점이 더 먼 곳의 왕복 거리를 result에 추가해줬습니다 function solution(cap, n, deliveries, pickups) { // 가장 먼 거리를 최소로 왔다갔다 해야 함 // 최대한 먼 곳부터 많이.. 2024. 1. 10.

[다익스트라][백준] 117799 최소비용 구하기2 JS 문제링크 한 노드에서 다른 노드까지의 최소 비용을 구하는 것이기 때문에 다익스트라! 다익스트라 : 한 정점에서 다른 모든 정점까지의 최소 비용을 구하는 알고리즘 다익스트라는 우선순위큐를 사용하는데 JS에는 우선순위큐 라이브러리가 없기 때문에 직접 구현 접근 방법 1. 버스 정보 인접리스트, 각 노드까지의 최소 비용을 저장할 배열(minArr), 이전에 방문한 노드를 저장할 배열(pre)을 만든다. 2. 우선순위 큐에 시작 노드를 넣어준다 3. 큐가 빌 때까지 노드를 꺼내서 minArr와 pre배열을 업데이트 한다 3번에서 배열들을 업데이트 할 때 1. minArr에 있는 값이 우선순위 큐에서 꺼낸 값보다 작을 경우, 꺼낸 값은 최소 비용이 아님으로 continue; 2. minArr에 있는 값보다 우선순.. 2024. 1. 10.

[프로그래머스] 시소 짝꿍 JS 문제링크 풀이 방법 쌍의 개수를 구하는 것이었기에 조합을 떠올렸습니다 두 수의 2,3,4배수 값 중 하나라도 같으면 됩니다 나올 수 있는 비율은 2:3, 2:4, 3:2, 3:4, 4:2, 4:3 쌍이기 때문에 모든 비율에 대한 수를 찾지 않고 특정수를 기준으로 큰 수만 구하기로 했습니다 function solution(weights) { //쌍을 구하라 = 조합 //두 수의 2,3,4배수 값이 하나라도 같으면 됨 //나올 수 있는 비율은 2:3, 2:4, 3:2, 3:4, 4:2, 4:3이지만 //쌍이기 때문에 하나의 수를 기준으로 큰 수만 구하기 let cnt=0; const table = {}; weights.forEach(w=>{ table[w]=(table[w]||0)+1; }); for(let.. 2024. 1. 9.

이전 1 2 3 4 ··· 6 다음

티스토리툴바