다이나믹 프로그래밍, 최단 경로, 그래프 알고리즘 개념 정리

다이나믹 프로그래밍

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 컴퓨터 과학과 알고리즘 설계 분야에서 사용되는 중요한 문제 해결 기법 중 하나입니다. 이 기법은 주로 최적화 문제나 최단 경로 문제와 같은 문제들을 해결하는데 사용됩니다.

다이나믹 프로그래밍의 핵심은 중복 계산을 피하고 계산 결과를 저장하여 재활용하는 것입니다.

 

다이나믹 프로그래밍 단계

1. 문제를 작은 부분 문제로 나눕니다.

2. 각 부분 문제를 해결하기 위한 연산을 정의합니다.

3. 작은 부분 문제들을 해결하면서 결과를 저장합니다.

4. 저장된 결과를 활용하여 더 큰 부분 문제를 해결합니다.

5. 최종적으로 전체 문제의 해결 방법을 얻습니다.

 

다이나믹 프로그래밍의 두 가지 유형

상향식 다이나믹 프로그래밍 : 작은 부분 문제부터 시작하여 점진적으로 큰 문제로 나아가는 방식이다. 이러한 방식은 반복문을 사용하여 구현하기 쉽고, 메모리를 덜 사용하는 경향이 있다.

하향식 다이나믹 프로그래밍 : 큰 문제를 해결하기 위해 작은 부분 문제를 호출하며, 플요한 부분 문제의 결과를 저장하고 활용하는 방식이다. 주로 재귀 함수와 메모이제이션을 사용하여 구현된다.

 

최단 경로 알고리즘

최단 경로 알고리즘이란?

그래프에서 두 정점 사이의 가장 짧은 경로를 찾는 데 사용되는 알고리즘입니다. 이러한 알고리즘은 다양한 응용 분야에서 사용됩니다.

 

최단 경로 알고리즘 종류

단일 출발점 최단 경로 알고리즘 : 하나의 출발점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다.

모든 쌍 최단 경로 알고리즘 : 그래프 내 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다.

다익스트라 알고리즘 : 음의 가중치를 가지지 않는 그래프에서 사용되며, 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는다. 그리디 알고리즘의 한 종류로, 현재까지 찾은 최단 경로를 선택하는 방식을 사용한다.

벨만-포드 알고리즘 : 음의 가중치를 가지는 그래프에서도 사용할 수 있고, 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는다. 이 알고리즘은 동적 프로그래밍의 원리를 사용하며, 음의 사이클이 없는 경우에만 정확한 결과를 얻을 수 있다.

 

그래프 알고리즘

그래프 알고리즘이란?

그래프 알고리즘은 그래프 이론에 기반한 알고리즘으로, 그래프 구조에서 다양한 정보나 관계를 분석하고 추출하는 데 사용됩니다. 그래프는 노드와 그 노드를 연결하는 간선으로 이루어진 추상적인 자료 구조로, 현실 세계에서의 다양한 문제를 모델링하고 해결하는 데에 사용됩니다.

 

그래프 알고리즘 종류

최단 경로 알고리즘 : 그래프에서 두 노드 간의 최단 경로를 찾는 데 사용된다. 이러한 알고리즘에서는 다익스트라 알고리즘, 벨만-포드 아록리즘 등이 포함된다.

최소 신장 트리 알고리즘 : 그래프에서 모든 노드를 연결하면서 최소 가중치의 간선으로 이루어진 트리를 구성하는 알고리즘이다. 프림 알고리즘과 크루스칼 알고리즘이 대표적인 예시이다.

네트워크 플로우 알고리즘 : 그래프에서 데이터의 흐름을 모델링하고 최적의 데이터 전달 경로를 찾는 데 사용된다. 포드-풀커슨 알고리즘 등이 있다.