본문 바로가기

🧠 알고리즘31

[프로그래머스] 리코쳇 로봇 JS 문제링크 풀이 방법 bfs로 접근하긴 했는데 큐에 넣어야 하는 노드들과 방문 체크해야 하는 노드들을 잘못 생각해서 계속 오답처리가 나더라구요 스터디원님의 풀이 보고 감을 잡아서 다시 풀었습니다! 이전에 풀었던 bfs와 다르게 지나친 모든 노드를 방문 처리 하는게 아니라 끝에 다다른 노드만 방문 처리를 해서 최단 거리를 찾을 수 있었습니다 1. 출발점과 목표점의 좌표를 저장합니다. 2. 시작점을 방문 처리하고 큐에 넣어줍니다. 3. 큐에서 꺼낸 지점부터 상하좌우로 돌면서 한 뱡향으로 갈 수 있는 만큼 끝까지 갈 것 4. 도착한 끝지점을 방문하지 않은 상태면 cnt+1하고 큐에 넣어줌 (지나가는 모든 노드를 방문처리 하면 안됨!! 왜냐하면 지나갔던 노드들을 다시 지나가야 하는 경우가 존재, 하지만 이미 한 .. 2024. 1. 3.

[프로그래머스] 과제 진행하기 JS 문제링크 풀이 방법 1. 시간은 모두 분(숫자)으로 변환, 과제를 시작 시간 기준으로 오름차순 정렬합니다 2. 과제 큐에서 새로운 과제를 하나 꺼냅니다 3. 새로운 과제 시작 시간이 되지 않고, 임시 저장된 과제가 있으면 4. 앞으로 할 과제의 시작 시간 전까지 임시 저장 과제들을 꺼내서 진행합니다 5. 현재 과제가 계획된 마지막 과제라면 끝까지 마무리합니다 6. 다음 과제가 있다면 다음 과제 시작 시간과 과제 종료 시간을 비교하여 완료 배열 또는 임시 과제 스택에 넣어줍니다 7. 계획된 과제를 모두 진행할 때까지 반복합니다 8. 계획된 과제가 끝나면 스택에서 pop되는 순서대로 과제가 진행됩니다 function timeToNumber(time) { const [hours, minutes] = time... 2024. 1. 3.

[프로그래머스][PCCP 기출문제] 3번 / 아날로그 시계 JS풀이 문제 링크 PCCP 3번 풀이 방법 생각보다 시간이 걸려서 다른 분의 풀이를 참고했습니다. 이 풀이가 직관적이고 이해가 쉬운 것 같아요 참고 블로그 시침, 초침과 분침, 초침이 겹쳤는지를 확인하려면 1초마다 각도를 확인하면 됩니다. 현재 시간 기준으로 초침의 각도가 시침의 각도보다 작고, 1초 뒤에 시침의 각도보다 크거나 같다면 겹쳐진 것이므로 카운트를 1 증가합니다 분침도 마찬가지입니다. 다만 3가지가 겹쳤을 경우에는 1번만 카운트 해야 하므로 1을 빼줍니다. 1. 내 풀이 function solution(h1, m1, s1, h2, m2, s2) { //초당 움직이는 초침, 분침, 시침 각도 const SECONDS_ANGLE = 360 / 60; const MINUTES_ANGLE = 360 / 6.. 2023. 12. 29.

[프로그래머스][PCCP 기출문제] 2번 / 석유 시추 JS풀이 문제 링크 PCCP 2번 풀이 방법 정답을 내기 위해 필요한 값들은 모든 석유 덩어리의 크기 시추관을 뚫을 수 있는 열에서 접근 가능한 석유 덩어리의 크기의 합 각 열에서 접근 가능한 석유 덩어리의 크기의 합을 저장하기 위해 land의 열의 크기와 같은 1차원 배열(oilArr)을 만듭니다. land의 모든 원소를 방문하면서 bfs로 모든 석유 덩어리의 크기를 구합니다. 한 덩어리를 구할 때마다 각 col별로 석유 덩어리의 크기를 oilArr에 더해줍니다. bfs를 사용할 때에는 시간 제한에 걸릴 경우를 대비해서 직접 큐를 구현하는 편입니다 1. 내 풀이 class Node { constructor(val) { this.val = val; this.next = null; } } class Queue { .. 2023. 12. 29.

[백준] 2573 빙산 js 풀이 💡 접근법 햇수를 계산한다 1-1. 매년 빙산의 개수를 저장한다 iceCnt 1-2. 빙산의 높이를 바꿔줄 때마다 빙산의 개수 -1 해주고(iceCnt--) 1-3. 바꿔야 할 빙산이 남지 않았을 때, 새로운 해가 시작되는 것으로 간주한다(year++) 모든 빙산이 녹을 때까지 빙산의 높이를 조절한다.(bfs사용) 2-1. 빙산의 높이를 가지고 있는 배열은 2개를 사용한다. (why? 배열을 1개만 사용하여 업데이트 해줄 경우, 같은 해에 녹아서 0이 된 빙산이 인접 빙산의 높이를 조절할 때 바다로 카운트 되기 때문에) 2-2. 오리지널 배열(=새해가 시작되고 아직 빙산이 녹지 않은 배열)기준으로 인접 바다를 탐색하면서 임시 배열에 변한 빙산의 높이를 업데이트 해준다(bfs사용) 2-3. 높이가 0보다 .. 2023. 12. 28.

[위상정렬][백준] 2252 JS 풀이 위상정렬 : 방향 그래프에서 노드들간 선행 순서를 위배하지 않고 정렬하는 알고리즘 구현법 1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다 2. indegree가 0인 정점들을 모두 큐에 넣는다 3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가한다 4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킨다. 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가한다 5. 큐가 빌 때까지 3,4번 과정을 반복한다 좀 더 자세한 설명이 필요하다면 출처: 바킹독 블로그 https://blog.encrypted.gg/1020 위상 정렬 문제에 적용하기 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 .. 2023. 12. 28.

이전 1 2 3 4 5 6 다음

티스토리툴바