이번 챕터에서는 그래프에 대해 알아보고, 그래프를 이용해 최단거리를 구하는 Floyd algorithm (플로이드 알고리즘)도 살펴보려고 한다. 목차는 아래와 같다. 그래프 이론 플로이드 알고리즘 최단경로 구하기 - Floyd vs Brute-force 1. 그래프이론 (Graph Theory) 정말정말 x100!! 중요한 부분이다. 그래프 부분을 해놔야 이후에 나오는 다른 문제들을 해결할 수 있다! 그래프는 여러 개의 점(정점)들이 간선으로 연결된 구조를 나타낸다. 즉 그래프는 정점(V)와 간선(E)로 구성된다. G = (V, E) 그래프 종류 그래프는 가중치 존재의 여부, 방향 존재의 여부에 따라 종류가 다양하다. 가중치그래프 (weighted graph) : 간선에 값(가중치)이 존재한다면 그 그래..

이번 챕터에서는 Dynamic Programming에 대해 작성할 예정이다. 목차는 다음과 같다. 동적 프로그래밍 ? Dynamic Programming vs Divide-and-conquer (feat. 피보나치) 1. Dynamic Programming이란? 진짜 동적으로 프로그래밍을 하는게 아니고, 큰 문제를 작은문제로 나누어 푸는 방법을 말한다. Divide-and-Conquer처럼 문제를 하나 이상의 작은 인스턴스로 분할해 접근하지만, Divide-and-Conquer와 달리 Bottom-up approach를 사용한다. Bottom-up approach는 작은 인스턴트들을 먼저 해결해가는 접근법을 의미한다. Bottom-up approach는 다음과 같은 순으로 진행한다. 재귀적 속성 설정 작..