다이나믹 프로그래밍 알고리즘
다이나믹 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위한 효율적인 알고리즘 디자인 기법 중 하나입니다. DP는 큰 문제를 작은 하위 문제로 나누고, 이전에 계산한 결과를 저장하여 중복 계산을 피하며 문제를 해결합니다.
기본 개념
작은 하위 문제로 나누기
중복 계산을 피하기 위한 결과 저장
상향식 접근 방식 (Bottom-up) 또는 하향식 접근 방식 (Top-down)으로 구현 가능
예시
피보나치 수열 계산
배낭 문제 (Knapsack Problem) 해결
그래프에서 최단 경로 찾기 (Dynamic Programming을 사용하는 경우도 있음)
최단 경로 알고리즘
최단 경로 알고리즘은 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘입니다. 최단 경로 문제는 다양한 상황에서 발생하며, 다익스트라 알고리즘과 벨만-포드 알고리즘 등 다양한 알고리즘이 사용됩니다.
기본 개념
그래프에서 정점과 간선으로 구성
간선에 가중치가 할당되어 있을 수 있음
최단 경로를 찾는 방법은 다양하며, 문제에 따라 알맞은 알고리즘 선택
예시
다익스트라 알고리즘을 사용한 최단 경로 찾기
벨만-포드 알고리즘을 사용한 최단 경로 찾기
A* 알고리즘을 사용한 최단 경로 찾기
그래프 알고리즘
그래프는 정점과 간선으로 이루어진 자료 구조로, 현실 세계의 다양한 상호 관계를 표현하는 데 사용됩니다. 그래프는 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나뉘며, 그래프 알고리즘은 이러한 그래프를 다루는 데 사용됩니다.
기본 개념
정점과 간선으로 구성
다양한 문제를 해결하기 위해 다양한 알고리즘이 존재
그래프 순회, 최단 경로, 연결 요소 등 다양한 작업 수행
예시
깊이 우선 탐색 (DFS) 및 너비 우선 탐색 (BFS)
크루스칼 알고리즘을 사용한 최소 신장 트리 찾기
그래프에서 사이클 찾기 (서로소 집합 활용)
그래프에서 연결 요소 찾기
