CS/Algorithms3 플로이드(Floyd) 알고리즘 0. Intro 자료구조 수업 때 그래프 부분에서 다익스트라 알고리즘에 대해 배운 적이 있습니다. 다익스트라 알고리즘 경우에는 한 시작점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이었습니다. 이번에는 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 플로이드 알고리즘에 대해 소개해보겠습니다. 개인적으로 다익스트라 알고리즘보다 훨씬 이해하기는 쉬운 알고리즘 같습니다. 단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서만 유효한다는 것을 주의해야 합니다. 1. 플로이드(Floyd) 알고리즘 플로이드 알고리즘은 동적 계획법(Dynamic Programming) 기법을 사용합니다. 이를 위해서는, 그래프의 인접 행렬(adjacency matrix)을 이용하여 모든 정점 쌍 사이의 최단 경.. 2023. 4. 7. 왜 Mergesort 보다 Quicksort를 사용할까? Mergesort가 Quicksort에 비해 항상 유리한 알고리즘이 아닌가? Quicksort에는 최악의 경우 O(n^2)의 시간복잡도를 가지고 있으며, 평균의 경우에는 O(nlogn)의 시간복잡도를 가지고 있습니다. 이에 비해, Mergesort는 최악의 경우와 평균의 경우 모두 O(nlogn)의 시간복잡도를 가지고 있는 굉장히 안정적인 알고리즘입니다. 그래서 알고리즘을 배우면서 Mergesort가 훨씬 유리한 알고리즘 같은데, 왜 Quicksort가 일반적으로 더 많이 사용되는지 알고 싶어졌습니다. 핵심을 말하면, 지역성(Locality) 때문입니다. Locality 지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다. Localit.. 2023. 3. 27. 메모이제이션(Memoization)과 탭레이션(Tabulation)의 차이 0. Intro 메모이제이션(Memoization)과 탭레이션(Tabulation)은 둘 다 동적 프로그래밍(Dynamic Programming)에서 사용되는 방법이며, 입력 크기가 작은 하위 문제의 해답을 이용해 큰 문제를 해결하는 방법을 사용합니다. 그러나 두 방법의 차이점은 계산 방식과 구현 방법에서 차이가 있습니다. 1. 메모이제이션 Memoization은 top-down 방식으로, 큰 문제를 해결할 때 작은 하위 문제의 해답을 이용합니다. 이 때, 작은 하위 문제의 해답을 기록해 두고, 이를 이용하여 중복 계산을 피합니다. 따라서, 재귀 호출을 사용하여 구현하는 경우가 많습니다. 2. 탭레이션 Tabulation은 bottom-up 방식으로, 작은 하위 문제의 해답을 먼저 계산하고, 그것을 이용.. 2023. 3. 13. 이전 1 다음
