동적계획법2 [나만 볼 알고리즘] 최단 경로 문제 - 플로이드 워셜 최단 경로 문제 최단경로(Shortest Path)문제는 일상에서 매우 흔한 알고리즘 문제이다. 지도에서의 네비게이션 기능이나, 게임 상에서 유저의 길찾기 기능 등 다양한 분야에서 해당 문제를 마주칠 수 있다. 알고리즘 문제에서 최단 경로 문제는 주어진 그래프에서 특정 정점의 쌍에 대한 최단 경로를 구하는 것이 제일 흔한 형식이다. 최단 경로 문제와 관련된 알고리즘으로는 플로이드 알고리즘, 다익스트라 알고리즘, 벨만 알고리즘, A* 알고리즘 등이 있다. 플로이드 알고리즘 주어진 그래프에서 모든 정점의 쌍에 대한 최단 경로를 구해야 할 때 사용되는 알고리즘이 바로 플로이드(또는 Floyd-Warshall) 알고리즘이다. 모든 정점 간의 최단 경로를 한번에 구할 수 있다는 장점이 있다. 플로이드 알고리즘으로.. 2023. 7. 7. [나만 볼 알고리즘] 동적계획법 - LCS 예제 동적계획법? 반복 순회를 해야되는 문제를 해결하기 위해 우리는 재귀함수를 이용해 쉽게 접근 할 수 있다. 하지만 단순하고 무식한 브루트포스(완전탐색)의 방식은 지수적 시간복잡도를 갖는 경우가 흔히 있기에, 계산규모가 큰 문제에는 적합하지 않다. 재귀함수의 단점을 커버하고 강력한 해결능력을 보조하기 위해 선조개발자들은 동적계획법이라는 테크니션을 만들어내고 만다. 동적계획법은 재귀함수의 중복부분 문제를 해결하기 위해서 사용된다. 동적계획법을 공부할 때 꼭 한번씩은 접해본다는 LCS를 예시로 동적계획법을 경험해보기로 하자. LCS: Longest Common Subsequence - 최장공통부분서열 문제 Longest Common Substring이라고도 불리는데, 사실상 서열들의 공통된 부분 서열을 찾아내 .. 2023. 7. 5. 이전 1 다음
