개요Dynamic Programming(DP)은 복잡한 문제를 간단한 여러 개의 하위 문제(subproblem)로 나누어 해결하는 알고리즘 설계 기법이다. DP는 각 하위 문제의 해를 저장하여 중복 계산을 피하고, 전체 문제의 최적해를 효율적으로 구하는 데 사용된다. 특히 Optimization Problem을 해결하는 데 매우 효과적이다. 내용Optimization Problem이란? Optimization Problem(최적화 문제)은 주어진 조건 하에서 어떤 값을 최소화하거나 최대화하는 문제를 말한다. 예를 들어, 비용을 최소화하거나 이익을 최대화하는 것이 대표적인 최적화 문제이다. 이러한 문제는 하나 이상의 목표를 가지고 있으며, 그 목표를 달성하기 위한 최적의 값을 찾는 것이 주된 목적이다. D..
다익스트라 알고리즘이란?다익스트라 알고리즘은 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 가중치가 있는 그래프에서 최단 경로를 찾기 위해 사용되며, 음의 가중치를 가지는 간선이 없는 경우에 유효하다. 다익스트라 알고리즘은 주로 우선순위 큐를 사용하여 현재까지 발견된 최단 경로를 저장하고, 이를 기반으로 다른 정점으로의 경로를 지속적으로 업데이트하는 방식으로 작동한다. 다익스트라 알고리즘 구현문제 설명아래와 같은 가중치 그래프가 있다고 할 때, 1번 정점에서 모든 정점으로 가는 최소 거리 비용을 출력하라. (없으면 Impression 출력) 코드 구현import java.util.ArrayList;import java.util.Arrays;import java..
Union-Find (Disjoint Set)이란? Union-Find, 또는 Disjoint Set 자료구조는 서로소 집합을 관리하는 자료구조(알고리즘)이다. 이 자료구조는 여러 개의 원소들이 각각의 집합에 속해 있을 때, 두 원소가 같은 집합에 속해 있는지 확인하거나, 두 집합을 하나로 합치는 작업을 빠르게 수행할 수 있다. 이 자료구조는 그래프에서 연결된 컴포넌트를 찾거나 사이클을 검출하는 데 자주 사용된다. Union-Find 구현 방법Union-Find는 두 가지 주요 연산으로 구성된다 이름 그대로 Union 연산과 Find 연산이 그것이다. Union 연산 Union 연산은 두 집합을 하나의 집합으로 합치는 연산이다. 두 원소의 루트를 찾아 하나의 루트로 통일하는 방식으로 진행된다. 이때 랭크..
