알고리즘 기본기 다지기11. 그래프 알고리즘 (동적프로그래밍)

동적 프로그래밍(DP, Dynamic Programming)

동적 프로그래밍은 언뜻 보기에 많은시간이 소요될 것 같은 문제에 주로 적용한다.
복잡한 문제를 간단한 여러 개의 문재로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀때 사용한다.

동적 프로그래밍의 원리는 여러 개의 하위 문제(subproblem)으로 문제를 나눈 후,
해결을 결합하여 최종 목적에 도달하는 것이다.

동적 프로그래밍은 가능한 모든 방법을 고려해야한다는 단점이 있다. 이러한 단점을 극복하기 위해 그리디 알고리즘(Greedy algorithm)이 등장했다. 그리디 알고리즘은 항상 최적해를 구해주지 않지만, 최소 신장 트리 문제 등에서 최적해를 구할 수 있음이 입증되었다.

방향 그래프(Directed Graph)

모든 간선이 방향간선인 그래프를 말한다. 일방통행 도로, 항공편, 또는 작업스케줄리 처럼 정점과 정점 사이의 간선이 방향 간선으로 정의되는 네트워크 모델에 광범위하게 응용된다.

특성

• 방향 DFS : 간선들을 주어진 방향만을 따라 순회하도록 하면 DFS, BFS 순회 알고리즘들을 방향그래프에 특화할 수 ㅣㅆ다.
• 도달가능성 : 방향 그래프의 두 정점에 방향 경로가 존재한다면, 두 정점은 도달 가능하다고 말한다.
• 강연결성 : 방향 그래프의 두 정점에 방향 경로가 존재하여 도달이 가능하다면 그래프를 강연결(strongly connected)이라고 말한다.

이행적 폐쇄(transitive closure)

이행적 폐쇄는 방향 그래프에 관한 도달 가능성 정보를 제공한다. 컴퓨터 네트워크에서 "노드 a에서 노드 b로 메시지를 보낼 수 있을까?" 하는 문제에 대한 답을 제공한다.

• G*와 G는 동일한 정점으로 구성된다.
• G의 정점 u 로부터 정점 v != 정점 u까지의 방향 경로가 존재한다면, G* 에 정점 u로부터 v로 방향 간선이 존재한다.

위와같은 특징을 갖고 있다면 방향 그래프 G*는 그래프 G의 이행적 폐쇄이다.
대표적으로 Floyd-Warshall 알고리즘이 있다.

특징

• 부문제 단순성 : 부문제들이 j,k,l,m 등과 같은 몇 개의 변수로 정의 될 수 있음
• 부문제 최적성 : 전체 최적치가 최적의 부문제드레 의해 정의될 수 있음
• 부문제 중복성 : 부문제들이 독립적이 아니라 상호 겹쳐짐(해결이 상향식으로 구축되어야함)

연습문제

대표적으로 피보나치 수열(Fibonacci progression)에서 n-번째 수 찾기나 그래프의 이행적 폐쇄 계산하기 등이 있다.

백준

2839(설탕 배달) 1463(1로 만들기), 9095(1,2,3더하기) 1003(피보나치 함수) 11726(2xn타일링) 10870(피보나치 수 5) 1149(RGB 거리) 2579(계단오르기) 1912(연속합) 2748(피보나치 수 2) 12865(평범한 배낭) 2133(타일 채우기) 1699(제곱수의 합) 11049(행렬 곱셈 순서) 14002(가장 긴 증가하는 부분 수열4)

LeetCode

주요 알고리즘 문제 내용

• 피보나치 수열
• 최단 경로 문제
• 행렬의 제곱
• 타일링 문제
• 벨먼-포드 알고리즘
• 배낭문제

참고

백준 온라인저지 https://www.acmicpc.net/
LeetCode https://leetcode.com/
위키백과 https://ko.wikipedia.org/

문제 풀이

Github https://github.com/cri-kim/BlogPractice