📌 Intro 이전에 정리했던 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다. 하지만 이번에 살펴볼 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우"에 사용하는 알고리즘이다. 📌 Floyd-Warshall Algorithm 다익스트라 알고리즘은 매 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 과정을 진행하면서 최단 경로 리스트를 수정해나간다. 그리고 이 때 방문한 노드인지 확인하는 과정을 거친다. 하지만 플로이드 워셜 알고리즘은 노드를 방문할 때 방문한 노드인지 아닌지 확인할 필요가 없이 모든 노드에 대해서 동작하는 알고리..
📌 Intro 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로를 찾기 위한 알고리즘은 여러 종류가 있는데 그 중에서 가장 많이 사용되는 다익스트라 알고리즘에 대해 알아보도록 하자. 📌 Dijkstra Algorithm 다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는데 주로 사용한다. 즉 한 지점으로부터 다른 모든 지점까지 각각의 최단경로를 구할 수 있게 되는 것이다. 다익스트라 알고리즘을 사용하기 위해서는 모든 간선의 가중치가 음이 아니어야 한다는 조건이 있다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류되는데, 매번 "가장 비용이 적은 노드"를 선택하기 때문이다. 알고리즘에 대해 간략하게 정리하면 다음과 같다. 출발 노드를 설정한다. 최단 거..
Quick Sort 정렬 알고리즘 중 하나로 분할 정복(Divide and Conquer) 전략을 사용하는 알고리즘이다. C++ algorithm 헤더에 있는 sort함수는 퀵 소트로 구현되어 있고, 이러한 이유는 평균 수행시간이 빠르기 때문이다. (수행 시간에 대한 분석은 아래에 정리할 것이다.) 퀵 소트에서 중요한 부분은 피벗(pivot)과 파티션(partition)이고, 간단하게 피벗을 뽑고 파티션한다! 라고 생각할 수 있다. 피벗은 비교를 진행하기 위한 기준이 되는 원소를 말한다. 이 때 피벗은 가장 앞에 있는 원소로 선택할 수 있고 구현하는 방법에 따라 random하게 선택할 수도 있다. (여기서는 가장 앞에 있는 원소를 피벗으로 설정할 예정이다.) 다른 모든 원소들을 피벗과 비교하며 피벗보다 ..
백트래킹 백트래킹은 해가 될 수 있는 경로에 대해 탐색을 진행하다가 해가 아니라는 것을 알게 되면 더 이상 탐색을 진행하지 않고 종료한 뒤 다른 경로에 대해 탐색하여 해를 찾는 방법이다. 백트래킹의 개념을 잡을 때 백준에 있는 N과 M시리즈를 풀어보면 도움이 많이 된다. 그 중 첫 번째 문제를 가지고 설명을 진행하며 백트래킹에 대한 개념을 이해해보도록 하자. 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제의 내용 자체도 길지 않으나 요약하면 1~N까지의 수 중 중복 없이 길이가 M인 수열을 모두 찾아 출..
다이나믹 프로그래밍(DP)? 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘을 이야기 한다. 다이나믹 프로그래밍은 다음의 가정 하에서 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 조금 더 쉽게 피보나치 수열(앞의 두 항의 합이 뒤 항의 값으로 되어있는 수열)을 예를 들어 설명해보겠다. 피보나치 수열의 특정 항의 값을 구하기 위해서는 다음과 같은 재귀 함수를 이용할 수 있다. 10번째 항을 구하기 위해서는 fibo함수를 109번을 호출해야 한다. 코드의 가독성은 좋지만 실제 수행 시간은 굉장히 오래 걸리는 문제가 있다. 다이나믹 프로그래밍을 이용하면 수행시간을 ..
