개발하는 리프터 꽃게맨입니다.

1. 개요동적 계획법 (Dynamic Programming, 이하 DP)는 메모리를 적절히 사용하여 알고리즘의 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 것이죠. 예를 들어서 '피보나치 수열' 의 예시를 봅시다.  피보나치 수열은 위와 같은 점화식으로 나타낼 수 있으며이를 가장 간단하게 구현하는 방법은 재귀를 사용하는 겁니다.  이런 식으로 말이죠. 그런데 잘 살펴보면 피보나치 수열을 재귀로 구현하면 상당히 비효율적인 코드 진행을 보입니다. 피보나치 수열 알고리즘을 재귀 함수로 표현한 경우를 상태 트리로 나타내면 위와 같습니다. 이 상태 트리를 보면 알 수 있듯이미 계산된 값을 또 계산하고 있는 것을 볼 수 있습니다...

1. 신장 트리신장 트리(Spanning tree)란 그래프내의 모든 정점을 포함하는 부분 그래프(혹은 트리)이다.신장 트리는 특수한 형태로 모든 정점들이 연결되어 있어야 하고 사이클을 포함하면 안된다.따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1) 개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.   신장 트리의 경우 BFS, DFS 를 사용하면 도중에 사용된 간선을 모아 만들 수 있다. 신장 트리는 그래프의 최소 연결 부분 그래프가 된다.여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다.n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 ..

참고자료: C언어로 쉽게 풀어쓴 자료구조 - 천인국 저 1. 그래프란?그래프(graph)는 객체 사이 연결 관계를 표현할 수 있는 자료구조다.그래프의 대표적인 예는 '지도'이다. 위 그림은 여러 개의 도시들이 어떻게 연결되었는지를 보여준다.지도를 그래프로 표현하면 특정한 지역에서 다른 지역으로 가는 최단 경로를 쉽게 프로그래밍해서 찾을 수 있다. 또한 전기 소자를 그래프로 표현하게 되면 전기 회로의 소자들이 어떻게 연결되어 있는지를 표현해야 회로가 제대로 동작하는지 분석할 수 있으며, 운영 체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무 등을 알아낼 수 있다. 그래프는 이러한 많은 문제들을 표현할 수 있는 훌륭한 논리적 도구이다.우리가 이때까지 배워온 ..