다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용되는 알고리즘이다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. 이때, 거리가 음수인 간선은 포함할 수 없다. 하지만, 현실 ...

프로그래머스 - Level2 배달 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 다익스트라 알고리즘을 적용해서 풀었다. 그래프 문제는 처음이라 자료를 찾아가며 풀었다. 1번 마을에서 K 시간 안에 배달이 가능한 마을이 몇 개 있는지 구해야 한다. 주어진 시간 안에 이동하기 위해서는 최단 시간으로 이동하는 것이 좋기 때문에...

TL; DR DFS 는 스택과 재귀를 이용한다. BFS 는 큐와 반복문을 이용한다. 문제에서 요구하는 조건에 따라 DFS 나 BFS 둘 중 하나를 선택한다. 미로찾기 알고리즘이란? 미로찾기 알고리즘은 코딩 테스트에서 자주 등장하는 알고리즘이다. 시작 지점과 도착 지점이 주어지며, 탈출할 수 있는 경로를 출력하거나 탈출까지 걸리...

프로그래머스 - Level2 게임 맵 최단거리 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 1️⃣ DFS (실패 : 정확성 OK, 효율성 0점) 처음에는 DFS 로 접근해서 풀었다. (0, 0) 좌표에서 (n, m) 까지는 가기 위해서는 좌상단에서 우하단으로 가기 때문에 우, 하, 상, 좌 순으로 방향을 탐색했다. c...

프로그래머스 - Level2 방문 길이 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 문제 자체가 어렵지는 않았지만, 지나온 길을 어떻게 저장할 것인지가 가장 중요했던 문제다. 참고로 JavaScript 에서 배열끼리 비교를 한다면, 원하는 대로 되지 않을 것이다. 예를 들어, 다음과 같은 2차원 배열이 있다고 해보자. const a...

프로그래머스 - Level2 모음 사전 문제 설명 사전에 알파벳 모음 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 “A”이고, 그다음은 “AA”이며, 마지막 단어는 “UUUUU”입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가...

프로그래머스 - Level2 피로도 문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 “최소 필요 피로도”와 던전 탐험을 마쳤을 때 소모되는 “소모 피로도”가 있습니다. “최소 필요 피로도”는 해당 던전을 탐험하기...

프로그래머스 - Level2 메뉴 리뉴얼 문제 설명 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 “...

프로그래머스 - Level2 점프와 순간 이동 문제 설명 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸...

프로그래머스 - Level2 영어 끝말잇기 문제 설명 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다. 앞사람이 말한 단어의 마...