알고리즘 수행평가

다이나믹 프로그래밍(Dynamic Programming)이란?

다이나믹 프로그래밍은 컴퓨터 과학 및 알고리즘 분야에서 매우 중요한 개념 중 하나입니다. 이 기법은 중복 계산을 피하고 문제를 효율적으로 해결하기 위해 사용됩니다. 다이나믹 프로그래밍의 핵심 아이디어는 큰 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 최소화하는 것입니다.

예를 들어, 피보나치 수열을 계산하는 경우를 생각해보겠습니다. 다이나믹 프로그래밍을 사용하면 중간 계산 결과를 저장하여 같은 계산을 여러 번 수행하지 않고도 피보나치 수열을 빠르게 계산할 수 있습니다.

최단 경로(Shortest Path) 알고리즘

그래프 내에서 두 정점 사이의 최단 경로를 찾는 것은 다양한 실제 문제에 적용되는 중요한 문제입니다. 다양한 최단 경로 알고리즘 중에서 가장 잘 알려진 것은 다익스트라 알고리즘과 벨만-포드 알고리즘입니다.

• 다익스트라 알고리즘: 다익스트라 알고리즘은 하나의 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘으로, 음수 가중치를 가진 간선이 없는 경우에 사용됩니다. 이 알고리즘은 그리디 기법을 활용하여 최단 경로를 찾습니다.

• 벨만-포드 알고리즘: 벨만-포드 알고리즘은 음수 가중치를 가진 간선이 포함된 그래프에서도 최단 경로를 찾을 수 있는 알고리즘입니다. 하지만 다익스트라 알고리즘보다는 느리며, 음수 사이클을 감지할 수 있는 장점이 있습니다.

그래프(Graph)

그래프는 객체 간의 관계를 나타내는 자료 구조로, 실제 세계의 다양한 현상을 모델링하는 데 사용됩니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성되며, 다양한 종류의 그래프가 있습니다.

• 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프로, 두 정점 간의 연결 관계만을 표현합니다.

• 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프로, 한 정점에서 다른 정점으로의 방향성을 나타냅니다.

• 가중 그래프(Weighted Graph): 간선에 가중치(weight)가 할당된 그래프로, 간선을 통해 정점 사이의 거리, 비용 또는 가중치를 표현합니다.

그래프는 다양한 알고리즘 및 문제 해결에 활용되며, 네트워크 분석, 라우팅, 소셜 네트워크 분석, 게임 개발 등 다양한 분야에서 중요한 역할을 합니다.