4주차 스터디(23.12.01)-2

 

이번에 사용한 알고리즘들인

Manacher Algorithm, Dijkstra, Floyd-Warshall Algorithm에 대해 정리 해보았습니다.

 

1. Manacher Algorithm

 

문자열에서 가장 긴 회문 (Palindrome)을 찾기 위한 알고리즘입니다.

 

2. Dijkstra Algorithm (데이크스트라 알고리즘)

 

Non-negative weighted graph가 주어져있을 때, 각 Vertices들의 최소 weight 간선을 찾아내는 문제입니다.

 

3. Floyd - Warshall Algorithm (플로이드 워셜 알고리즘)

2에서의 데이크스트라가 Non-negative만 해당이 되었다면, Floyd Warshall의 경우에는 음의 가중치 또한 허용합니다.