[ALGOS STUDY] 2023-SUMMER DAY4 다이나믹 프로그래밍, 플로이드 와샬

다이나믹 프로그래밍

- 개념 : 큰 문제를 작은 문제로 쪼개서 답을 저장하고 활용하는 것 (이전의 결과들은 기억하면서 수행하기 위한 알고리즘)

 

- 다이나믹 프로그래밍 사용 조건

• 겹치는 부분 문제 : 동일한 작은 문제들이 반복해서 나타나야 함
• 최적 부분 구조 : 작은 문제들의 결과가 큰 문제에 상관없이 항상 동일해야 함.

 

- 다이나믹 프로그래밍 알고리즘 구현 방식

• bottom-up 방식
  • 아래에서부터 계산을 수행하고 누저시켜 전체 큰 문제를 해결하는 방식
  • 작은 문제의 결과들을 하나씩 저장해나간다.
• top-down 방식
  
  • n에서부터 호출을 시작해 인덱스 0까지 내려간다.
  • 해당 결과 값을 재귀를 통해 전이시켜 재활용

 

- 다이나믹 프로그래밍 구현 과정

1. 다이나믹 프로그래밍 조건 파악 및 적절성 판단
2. 관계식(점화식) 만들기
3. 메모하기 : 작은 부분의 결과값을 저장한다.
4. 기저 상태 파악 : 전체 결과를 위한 첫 시작점을 정한다.

 

📌 메모이제이션

• 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
• 동적 계획법의 핵심

 

- 문제 풀이 예시 : 백준 2748 피보나치 수 2 (https://www.acmicpc.net/problem/2748)

#include <iostream>
using namespace std;

long long fibo[92];

int main()
{
	int n;
	cin >> n;

	fibo[0] = 0;
	fibo[1] = 1;

	for (int i = 2; i <= n; i++) fibo[i] = fibo[i - 2] + fibo[i - 1];
	cout << fibo[n];
	return 0;
}

 

플로이드 와샬

- 개념 : 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용하는 알고리즘

 

-  점화식 : D_ab = min(D_ab, D_ak + D_kb)

 // k번 정점을 거쳐가는 경로를 고려하여 최단 경로 업데이트
 
 for (int k = 0; k < V; ++k)
    {
        for (int i = 0; i < V; ++i)
        {
            for (int j = 0; j < V; ++j)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

 

- 플로이드 와샬 vs 다익스트라

• 플로이드 와샬
  • 모든 지점에서다른 모든 지점까지의 최단 경로
  • 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택하고, 이에 따라 최단 거리 테이블 갱신
  • 2차원 테이블에 최단 거리 정보 저장
  • 다이나믹 프로그래밍에 속함.
• 다익스트라
  • 한 지점에서 다른 지점까지의 최단 경로
  • 단계마다 거쳐가는 노드를 기준으로 최단 경로를 구하므로 이전에 방문하지 않은 노드 중에서 최단 경로를 찾지 않음.
  • 1차원 리스트에 최단 거리 정보 저장
  • 그리디 알고리즘에 속함.

 

- 문제 풀이 예시 : 백준 11404 플로이드 (https://www.acmicpc.net/problem/11404)

#include <iostream>
#include <limits>
using namespace std;
#define INF (~0U>>2)
int cost[101][101], n, m;

int main()
{
	int a, b, c;
	cin >> n >> m;
	for (int i = 0; i < 101; i++)
	{
		for (int j = 0; j < 101; j++) 
		{ 
			if (i == j) cost[i][j] = 0;
			else cost[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		if (cost[a - 1][b - 1] > c) cost[a-1][b-1] = c;
	}

	for (int i = 0; i < n; i++)
	{
		for (int s = 0; s < n; s++)
		{
			for (int f = 0; f < n; f++)
			{
				if (cost[s][i] + cost[i][f] < cost[s][f]) 
                			cost[s][f] = cost[s][i] + cost[i][f];
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (cost[i][j] == INF) cout << 0 << " ";
			else cout << cost[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

---

ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 일시 자료는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 출처가 표기되었을 경우, 표기된 모든 출처를 옮겨 작성합니다. 

 

ALGOS 2023 여름방학 캠프의 경우 저는 주제 총정리 영상을 담당하였습니다. 5일동안의 주제를 간단히 정리하는 영상을 제작하였으며, 해당 글과 발표자료 제작 시 참고한 내용의 출처는 다음과 같습니다.

 

<출처>

https://wikidocs.net/206429

https://velog.io/@roo333/Floyd-Warshall-Algorithm

https://wikidocs.net/170477

https://didu-story.tistory.com/220

https://chanhuiseok.github.io/posts/algo-50/

파이썬으로 배우는 자료구조 프로그래밍 (유석종)