혼잣말처럼 넘기는 알고리즘 (파트2)

[이미지 출처: jkfran.com]
▷ 파트1  알고리즘? / 정렬 / 탐색
▼ 파트2
1. 그래프	1) 개념  2) 순회  3) 최소 신장 트리(MST)  4) 최단 경로  5) 네트워크 플로 문제
2. 동적 프로그래밍	1)  개념  2) 최장 공통 부분 수열  3) 행렬의 연쇄적 곱셈
▷ 파트3  스트링 알고리즘 / NP-완전 문제 / 유전 알고리즘
기타. 참조자료

① 일반적인 강의형 포스팅보다는 개인적인 노트정리입니다.

// 💬 이 주석은 자체적인 언어(?)로 해석/재구성한 메모다.

② 참조 서적중 초판이 1994년 이고 2020년 이후에도 개정판이 나온거 같은데 그걸로 봐도 되지 않을까 싶지만 제가 가지고 있던건 구판이다보니 이걸 기준으로.

③ 참조한 주요 서적은 C기준이다보니 저는 예제코드를 JAVA, C#, 파이썬 3.x에서 오가고자 합니다.

④ 예제는 웹 컴파일로도 가능하긴 하지만, 가급적 브레이크 포인트를 걸면서 보는쪽이 좋을거 같아 로컬에서 구동할 개발 환경 세팅자료 참조 넣어둡니다.
→ 비주얼 스튜디오 코드(VS code)를 다용도 세팅 -자바, C#, 파이썬- [🔗티스토리][🔗블로거]

⑤ 클라우드 드라이브에 올려둔 소스 코드의 변경이력은 해당 포스팅에 별도로 남기지 않습니다.

⑥ 시간 날 때마다 작성을 하다보니 자체 제작한 예시 그림은 스타일이 균일치 못 한 경우가 있습니다.

▼ 1. 그래프

1) 개념 📂

 "그래프(graph)는 정점(vertext)과 간선(edge)으로 구성된 비선형 자료구조이다. 정잠과 간선은 다양한 정보를 가질 수 있는데, 일반적으로 정점은 인덱스 그리고 간선은 가중치(weight)로 나타내는 경우가 많다. ...(중략)...이웃한 두 역이 '서울역'과 '시청'간의 거리 또는 이동시간의 간선의 가중치가 될 수 있다. 최소 시간 또는 최단 거리로 이동할 수 있는 지하철 경로를 찾는 문제에서는 기본적으로 지하철 노선을 그래프로 표현해서 해결한다. 이 밖에 그래프로 표현할 수 있는 예는 무수히 많으며, 최단 경로 탐색, 프로젝트 분석, 전기회로 분석 등 매우 다양한 실질적인 문제에 많이 응용되고 있다."

(p.209, 알고리즘, 2024)

 "꼭지점의 집합 V와 변의 집합 E를 가지는 그래프 G는 G = (V, E)와 같이 표현한다. 변은 두 꼭지점을 연결하는 역할을 수행하는데, 만일 변 e가 꼭지점 v와 w를 연결하는 경우 v와 w는 e에 의해 발생(incident)되었다고 하고 v와 w는 서로 인접(adjacent)한다고 한다."

(p.219, 이산수학, 2021)

/* 💬 한 붓그리기 문제, 지하철 환승경로, 쾨니히스베르크 다리 문제 등등. 추상화를 거치고 나면 그래프 알고리즘으로 풀 수 있는 문제가 생각보다 많다.

 현대사회에서 수학이 생각보다 더 실용적인데, 봐둬야 하는 부분이 많아질수록 연계시의 복잡도도 점점 어려워지고... 사람 살려. 사실 어느 분야건 깊이 들어가면 안 그런 경우가 거의 없겠지만서도... 살려줘.*/

① 인접 행렬/리스트
 그래프를 구현한다면, 2차 배열 기반인 '인접 행렬'(Adjacency Matrix)과 연결 리스트 기반인 '인접 리스트'(Adjacency List)로 가능. 인접 행렬에서 간선이 존재치 않을때는 0이 ∞로 표기.

[그림. 인접행렬 / 출처: programiz]

[그림. 인접리스트 / 출처: programiz]

인접 행렬 내용/읽기: A[i, j]는 정점 i에서 j에 직접 연결된 간선에 대한 정보.

인접 리스트 내용/읽기: 정점 n번에 직접 연결된 정점들 목록 나열.

2) 순회 📂

[그림. BFS와 DFS차이 / 출처: geeksforgeeks]

2-1) 너비 우선 탐색 (BFS, Breadth First Search)	2-2) 깊이 우선 탐색 (DFS, Depth First Search)
- 인접리스트로 구현 O(|V|+|E|) - 인접행렬로 구현    O(|V|²) - FIFO기반. 같은 레벨 정점을 다 방문하고서 다음 레벨 정점들을 방문해간다. 큐로 연산가능.	- 인접리스트로 구현 O(|V|+|E|) - 인접행렬로 구현    O(|V|²) - LIFO기반. 최근 방문한 정점과 연결된 (이웃)정점을 방문해간다. 스택/순환 호출로 연산가능.
//수도코드. 큐 기반 시작정점.visited = true;//방문과 출발이 같이 이뤄짐. addQueue(큐데이터, 시작정점); 정점 delVertex = null; while(큐데이터 != null) {    delVertex = delFromQueue(큐데이터);//FIFO 주의.    for(정점 nextVertex : delVertex.인접한_정점들)    {//for each       if(nextVertex.visited==true){ continue; }       nextVertex.visited = true;       addQueue(큐데이터, nextVertex);    } }	//수도코드. 스택 기반 pushStack(스택, 시작정점); 정점 topVertex = null; while(스택 != NULL) {    topVertex = 스택.top;    topVertex.visited = TRUE;//방문처리    do{       for(정점 nextVertex : topVertex.인접한_정점들)       {//for each          if(nextVertex.visited == true){ continue; }          pushStack(스택, nextVertex);}          topVertex = popStack(스택);       } while(스택 != NULL) } ------------------------------------ //수도코드. 순환 호출 기반. recursionForDFS(그래프, currentVertex) {    currentVertex.visited = TRUE;//방문처리    for(정점 nextVertex : currentVertex.인접한_정점들)    {//for each       if(nextVertex.visited == true){ continue; }       recursionForDFS(그래프, nextVertex);    } }

/* 💬 트리 환경에서는 중위 순회(Inorder Traversal 혹은 Left-Root-Right), 전위 순회(Preorder Traversal 혹은 Root-Left-Right), 후위 순회(Postorder Traversal 혹은 Left-Right-Root)로 3가지 갈래가 있다.

 그래프 형태중 사이클이 없으면 트리이긴 한데,

 방송대 교재 기준으로 3가지 순회법은 '컴퓨터과학 개론'(2021)의 자료구조 파트에서는 다뤄지나, (방송대)알고리즘에서는 난이도 조절 이슈때문인지 p.217에서 약간 다루는 비중. 포스팅하면서 교재를 2개 이상 참조하는 이유이기도. */

2-3) 응용

① 위상정렬

[그림. 위상정렬 예시 / 출처: leetcode]

 "위상정렬(Topological sort)은 무사이클 방향 그래프(DAG, Directed Acyclic Graph)에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것이다.

...(중략)... 깊이 우선 탐색을 활용하여 구할 수 있다. 깊이 우선 탐색을 하다가 더이상 주변 정점이 없어서 되돌아갈 때, 즉 트색에서 탑의 데이터를 제거할 때 제거한 정점을 역순으로 나열하면 된다."

(p.224, 알고리즘, 2024)

 "Topological Sorting for a graph is not possible if the graph is not a DAG.

...(중략)...

DAGs are a special type of graphs in which each edge is directed such that no cycle exists in the graph, before understanding why Topological sort only exists for DAGs, lets first answer two questions:"

(geeksforgeeks, 2024)

/* 💬 예를 들면, 크리스마스 트리 LED장식등이나 내부 인터넷허브망 연결 배선을 절단하지 않고, 반쯤 꼬여있는걸 풀어서 한 줄로 늘어뜨리는 선정리. 그래프내 모든 변이 교차되지 않는다는점에서 평면 그래프(planar graph)의 일종으로 봐야 하나?

 이 말은 곧, 노드와 정점이 많은 문제에서 위상정렬은 그리 좋은 선택이 되기 어려움. 이재규(1996)의 표현을 빌리자면, 진입차수(혹은 내차수)가 0인 정점을 효율적으로 찾아야 하는 비용때문이기도. */

[그림. DFS를 통한 위상정렬 예시도 / 출처: leetcode]

/* 💬 위 예시에는 생략됐지만, 전체 로직상 pop된 정점들로 꼬리부터 채워질 배열(길이가 고정)과 DFS를 처리할 스택이 필요. */

② 그래프의 연결성(connectivity) //교재에 따라서 '그래프의 연결도'라 하기도

연결성	"Connectivity(연결도) 분석은 network 설계에서 가장 흔히 나타나는 문제이다. 즉 그래프가 얼마나 튼튼하게 연결되었는지, 몇 개의 edge를 제거할 경우에도 얼마나 버틸 수 있는지(faulttolerant), 임의의 두 정점 간에 서로 독립된(mutually disjoint) 경로는 몇 개가 존재하는지등을 분석하는 것" (조현규, 2019) /* 💬 연결성이 높다는건 정점간 연결이 여러 겹이니 몇 개정도 제거해도 흐름이 틀어지지 않는다? */
연결 성분 (Connected component)	무방향 그래프에서 while(아직 탐색하지 않은 정점 존재) {    if(탐색중 큐나 스택이 비었다)    {       그 때까지 탐색한 정점들을 하나의 성분으로    } } /* 💬 DFS기준으로 말하면,  더는 파고 들어갈 다음 정점이 없을 때(직계가 끊어짐)까지의 구간을 하나의 연결 성분으로 묶음.  연결 성분 1에만 (최조)시작 정점이 들어가고, 나머지 연결 성분은 해당 정점이 안 들어가는 분할. */
강연결 성분 (Strongly connected component)	방향 그래프에서 두 정점에 왕복 경로가 존재하는 '최대 부분 그래프'.  다르게 말하면 정점a가 있을때,  정점a->정점b, 정점a->정점c처럼 다른 정점으로 진출하는 경로만 있고, 다른 정점에서 정점a로 진입하는 경로가 없으면 정점 a만 포함된 1개 짜리 강연결 성분으로 묶음.

3) 최소 신장 트리(MST) 📂

- 가중 무방향 그래프(Weighted undirected graph)에서 싸이클 없이 모든 정점을 연결한 그래프.

- |V정점| = n개 일때, 총 (n-1)개의 간선이 존재하며,

 가중치 총합이 가장 작은것을 '최소 신장 트리'(MST, Minimum Spanning Tree, 최소 비용 신장 트리)라 한다.

- 최소 신장 트리에 쓰이는 크루스칼과 프림 모두 욕심쟁이 방법(탐욕 알고리즘)을 사용하고, 결과값은 순서가 보장된 경로T.

/* 💬 욕심쟁이 방법은 반드시 최선의 결과가 아니니 '최소'를 써야 하는건가도 싶지만, 다른 표현이 있을까를 물어보면... 글쎄올시다? 그냥 관용적 표현?

 주요 참조자료에는 없지만,

 (자료구조 기준)욕심쟁이 방법을 쓰는 MST에 '솔린 알고리즘'(Sollin Algorithm. 혹은 보르브카 알고리즘 Borůvka's algorithm)도 다뤄짐. 까먹지 않게 참조자료 메모 하나. [🔗Boruvka’s algorithm | Greedy Algo-9] */

3-1) 크루스칼 알고리즘	3-2) 프림 알고리즘
ⓐ 그래프내 간선들 오름차순정렬. k=0 ⓑ (정렬된 간선들중) k번 간선을 T[]에 추가시 싸이클이 없으면,  그대로 경로에 추가하나 싸이클이 생기면 경로에 추가하지 않고 k++ ⓒ ∀정점이 연결? 종료 : 단계 ⓑ로	ⓐ 가중 그래프에서 임의의 정점 하나에서 출발(혹은 맨 앞번호)하고 usedVertex에 추가. ⓑ T[]에 직접 연결됐고,  가중치가 낮으며 싸이클이 형성되지 않는 정점을 T[]와 usedVertex에 추가. ⓒ ∀정점이 연결? 종료 : 단계 ⓑ로
//수도코드. 간선목록[] = 가중치 기준 간선 오름차순;// O(E·logE) 경로T = {}; for(간선 tmpE : 간선목록[]) {//for each. 향상된 for문   if(경로T에 tmpE 넣으면 싸이클 형성 == true)   {       continue;   } 경로T = 경로T ∪ tmpE; }	//수도코드. allVertexSet = 그래프내 모든 정점이 들어간 집합; 경로T = {}; usedVertex = {V₁}; while( |경로T| != |usedVertex| ) {   tmpVertexSet = allVertexSet - usedVertex; // 💬 사실 교집합∩이 덜 헷갈리지 않나?   for(정점 tmpV : tmpVertexSet)   {//for each. 향상된 for문   if(경로T에 tmpV 넣으면 싸이클 형성 == true)   {   continue;   } 경로T = 경로T ∪ tmpV; usedVertex = usedVertex ∪ tmpV; } }

4) 최단 경로 📂

데이크스트라 알고리즘(Dijkstra  혹은 다익스트라)	벨만-포드 알고리즘 (Bellman-Ford  혹은 Bellman–Ford–Moore)	플로이드 알고리즘 (Floyd  혹은 플로이드 와샬)
- 가중치가 양수인 간선만 있는 그래프. - 단일 출발점 최단 경로. - 시간 복잡도: ① 인접행렬. O(|V|²) ② 인접리스트+힙.     O((|V|+|E|)·log|V|) - 욕심쟁이 방법.	- 가중치가 음수인 간선이 있는 그래프. 음의 가중치가 없으면 오히려 데이크스트라가 효율적. - 단일 출발점 최단 경로. - 시작 복잡도: O((|V|·|E|) - 동적 프로그래밍. n개의 정점에서 최대 n-1개의 간선으로 최단 경로를 연산.	- 가중치가 음수인 간선이 있는 그래프. - 모든 쌍 최단 경로. - 시간 복잡도: O(|V|³) → |V|² > |E| 인 경우는 차라리 데이크스트라 - 동적 프로그래밍.

→ 동적 프로그래밍 자체는 파트2-2. 동적 프로그래밍이지만, 그래프에서 최단 경로 종류로써 개념 파악용.

4-1) 데이크스트라 알고리즘

/* 💬 매 정점마다 가까운 지점으로 옮겨가니 욕심쟁이 방법. 무방향 그래프의 경우, 방향 제약이 없다는 차이를 빼면 동일하다.

 참고로 매 정점마다 다음 정점으로 이동하는건 욕심쟁이(탐욕 알고리즘)이 맞으나,

 종착점에서 나오는 정체 경로값을 내기 위해 매 정점마다 이전 거리를 계속 누적하는 부분은 동적 프로그래밍이기도 하지만 방송대 시험에서는 그냥 욕심쟁이 방법만으로 정의해서 어쩐지 틀려버렸고, 내 학점은;;;

 문제해결법 이름이 욕심쟁이랑 동적인거지, 알고리즘 이름 자체는 아니지 않나?*/

예시. 가중 방향 그래프에서 벨만-포드 알고리즘으로 최단 경로 찾기(출발점: 1)

📌초기화. (순서가 보장된)집합S={} 출발 정점을 제외한 나머지 정정의 d(거리)를 (최적화 되기전인)∞로 초기화

📌연산. ⓐ 출발 정점인 1을 집합S에 넣어서 S={1}. 1→1이니 d=0 ⓑ 1에서 인접한 정점2, 정점3중 가중치가 가장 작은 1→3 선택. S={1, 3} ⓒ 3에서 인접한 정점2, 정점5중 가중치가 가장 작은 3→2 선택. S={1, 3, 2} ⓓ 2에서 인접한 정점4, 정점5중 가중치가 가장 작은 2→5 선택. S={1, 3, 2, 5} ⓔ 5에서 인접한 정점4, 정점6중 가중치가 동일하기에     정점 번호가 빠른 5→4 선택. S={1, 3, 2, 5, 4} ⓕ 4에서 인접한 정점6중 가중치가 가장 작은 4→6 선택. S={1, 3, 2, 5, 4, 6} 연산결과. 경로 순서는 S={1, 3, 2, 5, 4, 6}이고, 전체 가중치(혹은 거리)가 10인 경로.

4-2) 벨만-포드 알고리즘

예시. 출발 정점이 1인 가중 방향 그래프에서 벨만-포드 알고리즘 최단 경로 찾기

📌초기화. [그림. 벨만-포드 초기화 / 출처: geeksforgeeks] (순서가 보장된)집합S={} 출발 정점을 제외한 나머지 정정의 d(거리)를 (최적화 되기전인)∞로 초기화 총 6개의 정점이 있으므로, 간선은 최대 5개까지 존재.

📌연산. ⓐ 출발 정점인 1을 집합S에 넣어서 S={1}. 1→1이니 d[1]=0 ⓑ 간선 1개 허용. A→B로 d[B]=5 갱신. ⓒ 간선 2개 허용. A→B→C로 d[B]+2 ⇒ d[C] = 6 갱신. A→B→D로 d[B]+1 ⇒ d[D] = 7 갱신. ⓓ 간선 3개 허용. A→B→C→E로 d[C]+1 ⇒ d[E] = 7 갱신. A→B→D→F로 d[D]+2 ⇒ d[F] = 9 갱신. ⓔ 간선 4개 허용. A→B→C→E→D로 d[E]-1 ⇒ d[D] = 6 갱신. A→B→D→F→E로  d[F]-3 ⇒ d[E] = 6 갱신. ⓕ 간선 5개 허용. A→B→C→E→D→F로 d[D]+2 ⇒ d[F] = 8 갱신. A→B→D→F→E→D    d[E]-1  ⇒ d[D] = 5 갱신. 하지만 모든 정점 순회X 연산결과. A→B→C→E→D→F인 d[F] = 8 가 최단 경로. "The core of the algorithm is a loop that scans across all edges at every loop. For every 𝑖≤|𝑉|−1, at the end of the 𝑖-th iteration, from any vertex v, following the predecessor trail recorded in predecessor yields a path that has a total weight that is at most distance[v], and further, distance[v] is a lower bound to the length of any path from source to v that uses at most i edges." (en.wikipedia.org, "Bellman–Ford algorithm") "We will go on relaxing all the edges (n - 1) times where, n = number of vertices" (javatpoint, "Bellman Ford Algorithm") /* 💬 영문 위키백과와 오래된 학습 사이트중 하나인 javatpoint도 정점보다 1개 적은 간선 갯수로 나오지만, geeksforgeeks에서는 정점 갯수 여서 이런 변종(?)도 있다 정도로.  역시 자료는 하나만 보면 안 된다. */ 만약, 정점 갯수 대로 간선을 6개 허용하면? (geeksforgeeks 기준) A→B→C→E→D→F→E로 d[F]-3 ⇒ d[E] = 5 갱신. A→B→D→F→E→D→F로 d[D]+2 ⇒ d[F] = 7 갱신. [그림. 벨만-포드 예시 / 출처: geeksforgeeks]

4-3) 플로이드 알고리즘

예시. 플로이드 알고리즘으로 최단 경로 구하기

📌초기화. [그림. 방향그래프의 인접행렬 초기화] - d⁰: 정점마다 직접연결된 경로는 가중치 / 자기 자신은 0 / 나머지는 ∞. - 점화식 dⁿ[i][j]   = min(dⁿ⁻¹[i][j], dⁿ⁻¹[i][k]+dⁿ⁻¹[k][j])   = n-1번 정점 경유하고 i→j혹은 i→k→j인 최단 경로. (단, n-1=0이면 중간 경로 X) - 중간경로가 X이면, X→(도착)나 (출발)→X도 min에서 같은값을 처리 하는셈이라 중간경로가 X일때는 X행과 X열은 연산 대상에 제외. - (인접행렬)주대각원소는 자신→자신으로 제자리 걷기이라서 연산 대상에 제외.

📌연산. dᴬ일때. 순서상 A보다 앞 번호는 없으므로 d⁰ dᴬ[B][C] = min(d⁰[B][C], d⁰[B][A]+d⁰[A][C]) = B→A 경로X dᴬ[B][D] = k→D 경로X dᴬ[C][B] = min(d⁰[C][B], d⁰[C][A]+d⁰[A][B]) = C→A 경로X dᴬ[C][D] = D로 진입하는 경로X dᴬ[D][B] = min(d⁰[D][B], d⁰[D][A]+d⁰[A][B]) = min(∞, 5+2) = 7 ⋯ [갱신O] dᴬ[D][C] = min(d⁰[D][C], d⁰[D][A]+d⁰[A][C]) = min(∞, 5+3) = 8 ⋯ [갱신O]   dᴮ일때. B를 경유하기 위해 B로 진출 가능한건 A와 C. dᴮ[A][C] = min(dᴬ[B][C], dᴬ[A][B]+dᴬ[B][C]) = min(-3, 2-3) = -3 ⋯ [갱신X] dᴮ[A][D] = k→D 경로X dᴮ[C][A] = min(dᴬ[C][B], dᴬ[C][B]+dᴬ[B][A]) = B→A 경로X dᴮ[C][D] = k→D 경로X   //윗첨자-라틴에 C가 없음. d^C일때. C를 경유하기 위해 C로 진출 가능한건 A와 D→A. d^C[A][B] = min(dᴮ[A][B], dᴮ[A][C]+dᴮ[C][B]) = min(2, 3-2) = 1 ⋯ [갱신O] d^C[A][D] = k→D 경로X d^C[D][A] = min(dᴮ[D][A], dᴮ[D][C]+dᴮ[C][A]) = C→A 경로X d^C[D][B] = min(dᴮ[D][B], dᴮ[D][C]+dᴮ[C][B]) = min(7, 8-2) = 6 ⋯ [갱신O] /* 💬 dᴮ[D][C]는 D→C로 직접 연결되지는 않지만, 앞 단계에서 만들어진 테이블을 참조하면 (D→A→C)=(D→C)=8이 가능.(가설적 삼단논법 혹은 추이라 불리는 그거.)  이런 부분때문에 동적 프로그래밍 방법. */   dᴰ일때. D를 경유하기 위해 D로 진출 가능한건 존재X 즉, 연산 종료.

위의 단계별 연산은 테이블상 아래와 같다. [그림. 플로이드 알고리즘 단계별 테이블과 최단경로 정보 테이블] - '최단 경로 정보P'는 테이블 기본값을 0으로 놓고, 직행이 아닌 경유가 있는쪽이 지름길인 경우에 해당 경유하는 정점을 넣는다. 또한 특정 칸이 2번 이상 갱신되면, 최근에 갱신됐던 경유 정점으로 입력. - 테이블 P를 읽는 법. P[A][B] = A→B = A→C→B = A→(P[C][B]) = A→(C→(중간점)0→B)    ⇒ (최적화된)전체 경로 A→C→B P[D][B] = D→B = D→(중간점)C→B = D→(P[C][B]) = D→(C→(중간점)0→B)    ⇒ (최적화된)전체 경로 D→C→B

5) 네트워크 플로 문제 📂

5-1) 개념
- 네트워크N=(V정점, E간선, s시작점, t도착점, c용량)로 정의되는 방향그래프이고, 시작점s(source)에서 도착점t( sink)로 전송하는 플로 값(value of flow)를 최대화 시키는 문제.

- 모든 간선에는 음수가 아닌 가중치가 있으며, 간선을 통해 전송하는 최대의 값을 '용량'(capacity).

- flow는 유량, 흐름등으로도 쓰임.

- 용량 제약 조건: 임의의 간선에서 플로는 항상 0 이상(음수 존재X)이고, 간선의 용량을 초과불가.

- 플로 보존 제약 조건: 시작점과 도착점이 아닌 모든 정점으로 들어오는 양과 나가는 양은 동일(유입되는 용량 그대로 유출.)


5-2) 포드-풀커슨 알고리즘(Ford-Fulkerson)
① 개념

- 엄밀히 말하면 종료가 보장되지 않아 알고리즘의 조건중 유한성에 벗어나 알고리즘이라 할 수 없으나,

 플로값을 증가시킬 경로가 존재하지 않을때까지 증가 경로를 탐색하는 방법은 간단하고 직관적. 경로를 찾는 법칙/순서가 별도로 있지 않음.

- 종료가 보장되는 개선판으로는 에드몬즈-카프 알고리즘(BFS적용)이 있다.

- 순방향으로 가면 간선의 가중치만큼 플로가 증가하나, 역방향은 간선에 부여된 플로를 줄임.

② 수도코드

- 시간 복잡도

O((|E|·F)

O((|V|·|E|²)  ← (개선판)에드몬스-카프 알고리즘 기준

FordFulkerson(argNetwork) {//argNetwork=(V정점, E간선, s시작점, t도착점, c용량)    모든간선의 플로 = doInit(0);    tmp = 0;    while( 증가 경로p가 존재==true )    {       tmp = min(모든 잔여 용량);       for(증가 경로상의 모든 간선)       {          if(순방향 간선) f(u, v)+=tmp;          else            f(u, v)-=tmp;       }    }    return sum(도착점에 들어온 모든 간선의 플로); }

③ 예시

예시. 포드-풀커슨 알고리즘 예시.

📌초기화. [그림. 플로 네트워크 예시-초기화 / 출처: programiz] - 간선에는 '플로/용량'값을 표기하며, 모든 간선의 플로는 0으로 초기화.

📌연산. ⓐ S→T경로중, S→A→B→T.    c(B→T)=2이므로 S→A는 [2/8] ⓑ S→T경로중, S→D→C→T.    c(C→T)=5이나, c(S→D)=3이므로 S→D는 [3/3] [그림. 플로 네트워크-중간단계 / 출처: programiz] ⓒ 아직 사용하지 않은 간선 D→B을 역방향 간선으로 만들고,    D.용량-D.플로=1이므로 B→D는 [1/7].    B에서 진출하는 플로는 총 3이니 S→A는 [3/8], A→B는 [3/9] ⓓ 더는 증가 경로가 존재X. 연산 종료. 연산결과. [그림. 플로 네트워크-연산 결과 / 출처: programiz]

▼ 2. 동적 프로그래밍

1) 개념 📂

① 주요 용어

 "동적 프로그래밍(dynamic programming)은 제 1장에서 살펴본 바와 같이 문제의 크키가 작은 소문제에 대한 해를 저장해 놓고 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법이다. 이때 소문제들이 서로 독립일 필요가 없다.

 동적 프로그래밍 방법은 최솟값 또는 최댓값을 구하는 최적화 문제에 주로 사용된다. 특히 최적성의 원리(priciple of optimality)가 반드시 성립하는 최적화 문제가 동적 프로그래밍 방법의 대상이 된다."

(p.289, 알고리즘, 2024)

 "주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다."

(ko.wikipedia.org, "동적 계획법")

"Identify Subproblems: Divide the main problem into smaller, independent subproblems.

Store Solutions: Solve each subproblem and store the solution in a table or array.

Build Up Solutions: Use the stored solutions to build up the solution to the main problem.

Avoid Redundancy: By storing solutions, DP ensures that each subproblem is solved only once, reducing computation time."

(geeksforgeeks, "Dynamic Programming or DP")

- 대표적인 문제: 피보나치 수열, 최장 공통 부분 수열(LCS), 행렬의 연쇄적 곱셈

/* 💬 영문 위키백과쪽 설명과 피보나치 수열의 재귀법을 합쳐서 보면, 수학적으로 최적화가 적용된 재귀법인 Down-Top방식.

 경로문제에도 언급한거지만,

 벨만-포드와 플로이드(-와샬)도 중급 난이도의 동적 프로그래밍 문제이고 이후에 다뤄지는 행렬의 연쇄적 곱셈이 상급 난이도라고(geeksforgeeks 기준) */

2) 최장 공통 부분 수열 📂

2-1) 개념

 "Given two strings, S1 and S2, the task is to find the length of the Longest Common Subsequence, i.e. longest subsequence present in both of the strings."

(geeksforgeeks, "Longest Common Subsequence (LCS)")

- 최장 공통 부분 수열(LCS. Longest Common Subsequence)에서 말하는 수열은 문자열에서 연속적이지 않더라도 순서는 유지되어야 한다.

예. ABCDEF와 AXBZCKMD가 있으면 일차하면건 ABCD로 처리.

/* 💬 약어 표기는 같은 이름이 비슷한 '최장 공통 부분문자열'하고 혼동하지 말 것. */

- 점화식.

LCS(i, j) = ∊                               (i = 0 또는 j = 0인 경우)

          = LCS(i-1, j-1) ⏐ x ᵢ              (x ᵢ = y ᵢ인 경우)

          = max {LCS(i, j-1), LCS(i-1, j)}  (x ᵢ ≠ y ᵢ인 경우)

2-2) 수도코드

- 시간 복잡도: O(n·m)

             (n: 스트링X 길이, m: 스트링Y 길이) // 💬 2차원 행렬 크기 그대로

getLCS(X[1~n], Y[1~m]) {   LCS[n+1][m+1];    LCS[0][0] = 0;//테이블 입력상, [0][0]는 문자열 대조에는 안 쓰임.    for (i=1; i<=n; i++)  {   LCS[i][0] = 0   }//테이블내 첫 열 초기화.    for (j=1; j<=m; j++) {   LCS[0][j] = 0   }//테이블내 첫 행 초기화.    for (i=1; i<=n; i++)    {       for (j=1; j<=m; j++)       {             if (X[i]==Y[j]){   C[i][j] = C[i-1][j-1] + 1;   }             else            {   C[i][j] = max(C[i][j-1], C[i-1][j]);   }       }    }    return LCS; //LCS의 길이를 보내려면, LCS[n][m] (배열의 맨 끝) }

2-3) 예제. 스트링 ABB와 ABD의 LCS 구하기

📌초기화. - LCS[0][0]=0과 첫행&첫열은 0으로

📌연산. ⓐ for-i가 1인 구간. - X[1] == Y[1]이니 LCS[1][1] = LCS[0][0]+1 ⓑ for-i가 2인 구간. - X[2] == Y[2]이니 LCS[2][2] = LCS[1][1]+1 ⓒ for-i가 3인 구간. - X[3] == Y[2]이니 LCS[3][2] = LCS[2][1]+1 ∴  LCS의 길이 = 2, LCS=AB

3) 행렬의 연쇄적 곱셈 📂

3-1) 개념

- 두 행렬의 곱에서 A*B != B*A이 되지만, 셋 이상의 행렬은 결합법칙상 어느 구간부터 곱하건 결과값은 동일. 중간과정에서 나오는 행렬의 크기가 달라지고 총 연산수가 다를뿐.

- n개의 행렬을 곱하는 연산에서 '최적성의 원리'로 보면, 일부분에서 최적의 곱셈순서를 포함시키는것.

/* 💬 구글링을 해보면,
한국어 자료에서는 연쇄 행렬 (최소)곱셈이 좀 더 일반적인 표기 같긴한데 영문 표기는 Matrix chain multiplication, Chained matrix multiplication등으로 표기가 된다. 같은 기법에 다른 이름 혹은 표기 방식으로 손발이 안 맞게 되는 경우만 생각하면 머리가 아프다.

 영문은 Chained matrix multiplication쪽 결과가 많으니 이쪽을 기준. */

3-2) 수도코드

- 시간 복잡도: O(n²)

getChainedMatrixMultiplication(int dims[]) {    int j, k = 0;    dLeng = dims.length - 1;    cost[1+dLeng][1+dLeng];    mat[1+dLeng][1+dLeng];//최적화된 곱셈 순서    for (i = 1; i <= dLeng; i++){   cost[i, i] = 0;   } //대각원소들 = 0;    for (s = 1; s <= dLeng - 1; s++)    {       for (i = 1; i <= dLeng - s; i++)       {          j = i + s;          cost[i][j] = min(cost[i][k]+cost[k+1][j]+dim[i-1]*dim[j],                           k = i이상 && j미만);          mat[i][j] = 최소 비용이 될때의 k값;       }    }    return (costCnt, mat); }

3-3) 예제. dim = {M1 = 5X4, M2 = 4X2, M3 = 2X3}인 3개의 행렬에 대한 연쇄적 곱셈 문제

📌초기화. - cost[i, i] = 0으로 루프문 돌리던대로.

📌연산. - 행렬 곱셈에서 기본 곱셈 횟수는 5·4·2·3로 d={5, 4, 2, 3} 확인. ⓐ for-s가 1인 단계. // 💬 열j = (i: 1~(행렬3개 - (s is 1))) + (s is 1) ⇒ j = {2, 3} cost[1][2] = cost[1][1] + cost[2][2] + d[0]Xd[1]xd[2] = 0+0+5*4*2 = 40 → mat[1][2] = 1 cost[2][3] = cost[2][2] + cost[3][3] + d[1]Xd[2]xd[3] = 0+0+4*2*3 = 24 → mat[2][3] = 2 ⓑ for-s가 2인 단계. // 💬 열j = (i: 1~(행렬3개 - (s is 2))) + (s is 2) ⇒ j = {3} cost[1][3]  = min(cost[1][1] + cost[2][3] + d[0]Xd[1]xd[3],        cost[1][2] + cost[3][3] + d[0]Xd[2]xd[3])  = min(0 + 24 + 5*4*3, 40 + 0 + 5*2*3) = min(84, 70) = 70 → mat[1][3] = 2  ∴  최소화된 곱셈 연산 횟수 = 70 최적화된 곱셈순서 M1*(M2*M3)

▼ 기타. 참조자료

1) 서적

강태원, 정광식 저. 자료구조, 한국방송통신대학교출판문화원, 2023년.

이관용, 김진욱 저. 알고리즘, 한국방송통신대학교출판문화원, 2024년.

이재규 저. C로 배우는 알고리즘 2, 세화, 1996년.

손진곤 저. 이산수학, 한국방송통신대학교출판문화원, 2021년.

2) 대학교 공개자료

Data Structure Visualizations, 미국 샌프란시스코 대학교 (by. David Galles) [🔗메인페이지]

> Algorithms (접속: 2024-06-30)

3) 튜터링 사이트

사이트명
대학공개강의 - KOCW	응용 그래프이론 - 부산대학교(조환규) [🔗메인페이지] - 8. 연결도
algorithmtutor	Data Structures - Binary Search Trees (BST) with code in C++, Python, and Java
Baeldung	Baeldung on CS [🔗메인페이지] Baeldung/Algorithms [🔗메인페이지]
geeksforgeeks	Binary Search Tree [🔗메인페이지] - Insertion in Binary Search Tree (BST) (갱신: 2023-07-28) - Searching in Binary Search Tree (BST) (갱신: 2023-12-21) - Deletion in Binary Search Tree (BST) (갱신: 2024-04-17)   BFS and DFS on Graph - BFS vs DFS for Binary Tree (갱신: 2024-02-19) - Difference between BFS and DFS (갱신: 2024-05-29)   Dynamic Programming or DP (갱신: 2024-07-30) - Longest Common Subsequence (LCS) (갱신: 2024-07-06) - Matrix Chain Multiplication | DP-8 (갱신: 2022-12-20)   Greedy algorithm on Graph - Boruvka’s algorithm | Greedy Algo-9 (갱신: 2023-03-17)   Shortest Paths in Graph - How to find Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm (갱신: 2024-07-05) - Floyd Warshall Algorithm (갱신: 2024-05-04)   Maximum flow in a Graph - Ford-Fulkerson Algorithm for Maximum Flow Problem (갱신: 2023-06-01)
javatpoint	Shortest Path - Bellman Ford Algorithm (방문: 2024-08-05)   All-Pairs Shortest Paths - Floyd-Warshall Algorithm (방문: 2024-08-05)
leetcode	discuss/general-discussion [🔗메인페이지] - Introduction to Topological Sort (방문: 2024-07-19)
programiz	Greedy Algorithms - Ford-Fulkerson Algorithm (방문: 2024-08-06)

4) 개인 블로그

4-1) 티스토리

[Algorithms] Asymptotic Notation | 점근적 표기법 (접속: 2024-06-18)

4-2) 블로거

혼잣말처럼 넘기는 자료구조 (파트4) (접속: 2024-07-07)

5) 웹사이트

ko.wikipedia, "최장 공통 부분 수열" (접속: 2024-08-16)(수정: 2022-08-23), https://ko.wikipedia.org/wiki/최장_공통_부분_수열

en.wikipedia, "Bellman–Ford algorithm" (접속: 2024-08-06)(수정: 2024-06-09), https://en.wikipedia.org/wiki/Bellman–Ford_algorithm

en.wikipedia, "Dynamic programming" (접속: 2024-08-07)(수정: 2024-08-03), https://en.wikipedia.org/wiki/Dynamic_programming

▼ 기타. 변경 내력

일자	변경 내력
2024-08-17	초안 및 일반 공개. [🔗blogger] [🔗티스토리]. 포스팅 신규 양식 적용(ver.202408)