문제 출처 Lv.2 귤 고르기 - JavaScript https://school.programmers.co.kr/learn/courses/30/lessons/138476 문제 설명 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 ‘k’개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다..
다익스트라 알고리즘 네트워크에서 최단 경로를 찾는 알고리즘이며, 이 알고리즘은 엣지 가중치의 합이 최소가 되는 경로를 찾아줍니다. 즉, 그래프의 한 정점에서 다른 정점으로 가는 가장 짧은 경로를 찾는 문제를 해결하는데 사용됩니다. 1. 초기화: 시작 노드의 거리를 0으로, 나머지 모든 노드의 거리를 무한대로 설정합니다. 시작 노드를 현재 노드로 설정합니다. 2. 현재 노드에서 인접한 노드들의 거리를 계산합니다. 이 때, 기존에 설정한 거리보다 새로 계산한 거리가 짧으면 거리 정보를 업데이트합니다. 3. 모든 인접 노드에 대해 거리를 업데이트한 후에는 방문하지 않은 노드 중 거리가 가장 짧은 노드를 새로운 '현재 노드'로 설정합니다. 4. 모든 노드를 방문할 때까지 이 과정을 반복합니다. 다음과 같은 그래..
DFS(Depth-First Search) 그래프 탐색을 위한 알고리즘 중 하나로, 깊이 우선 탐색이라고도 합니다. DFS는 그래프의 모든 노드를 방문하고, 각 노드를 한 번씩만 방문하며 연결된 모든 노드를 탐색합니다. DFS의 작동 방식은 다음과 같습니다: 시작 노드를 방문하고, 방문한 노드를 "방문한 노드" 목록에 추가합니다. 현재 노드와 연결된 이웃 노드들을 확인합니다. 이웃 노드들 중 방문하지 않은 노드가 있으면, 그 이웃 노드로 이동하여 재귀적으로 탐색합니다. 모든 이웃 노드를 방문했거나 더 이상 방문할 이웃 노드가 없으면, 이전 단계로 돌아가서 탐색을 계속합니다. DFS는 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다. 스택을 사용하는 경우, 방문한 노드들을 스택에 차례로 쌓..
그래프 노드(node)와 그 노드들을 연결하는 간선(edge)으로 이루어진 자료 구조입니다. 그래프는 현실 세계에서 다양한 상호 관계를 표현하는데 사용됩니다. 예를 들면 지도에서 도시들을 노드로, 도로를 간선으로 표현하는 것이 그래프의 한 예입니다. JavaScript에서 그래프를 구현하는 방법 중 가장 일반적인 두 가지 방법은 "인접 행렬"과 "인접 리스트"입니다. 인접 행렬 (Adjacency Matrix) 인접 행렬은 2차원 배열로 그래프의 연결 정보를 표현합니다. 노드 간 연결 여부를 행렬의 값으로 표현하며, 노드 수가 N개인 그래프라면 NxN 크기의 행렬이 필요합니다. 예를 들어, 노드 1과 노드 2가 간선으로 연결되어 있다면, 인접 행렬의 1행 2열과 2행 1열에 해당하는 값에 연결 정보를 표..
