안녕

문제)

문제)

문제)

최단 경로를 찾는 두 가지 대표적인 알고리즘 중에 하나입니다. 다른 하나는 다익스트라 알고리즘이 있는데, 이는 탐욕법에서 알아봅니다. 프로이드의 알고리즘은 모든 점에서 모든 다른 점까지의 거리를 알아냅니다. 최단 경로 문제는 Optimization Problem입니다. 여러 가지 해답의 후보가 있고, 각 후보마다 값이 있고, 우리는 최적의 값을 찾아야 합니다. (여기서는 경로의 최솟값) 최단 경로의 문제에서 한 마디에서 다른 마디로 가는 최단 경로는 하나 이상이 있기 때문에, 여기서는 최단 경로 중 하나를 찾습니다. 1. 알고리즘 시작은 단순무식한 접근법 (Brute-Force)입니다. 한 정점에서 다른 정점으로 가는 모든 경로를 구한 후, 그 경로 중 최솟값을 찾는 방법입니다. 이때 경우의 수는 (n-..

문제)

다들 이항 계수 아시죠? \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)입니다. 이때 n!를 계산하기 매우 힘드므로, 재귀 관계식을 이용하여 다음과 같이 정리할 수 있습니다. \(\binom{n}{k}=\left\{\begin{matrix} \binom{n-1}{k-1}+\binom{n-1}{k} & 0

1. 동적 계획법이란? DP (Dynamic Programming)는 코딩 테스트의 절반 이상을 차지하는 알고리즘이라 봐도 무방합니다. DP는 분할 정복과 매우 유사합니다. 하지만 분할 정복은 top-down 방식을 이용하고, DP는 bottom-up 방식을 이용합니다. 가장 작은 instance의 답을 먼저 구하여 저장하고, 필요하면 꺼내 쓰는 '동적 계획'입니다. 여기서 계획이란 문제 해결을 위한 배열(테이블)을 구축한다는 뜻입니다. DP 알고리즘의 개발 절차는 다음과 같습니다. 문제의 instance의 해답을 구하는 재귀 관계식을 세운다. (top-down approach, Divide and Conquer 방식) 작은 instance부터 해결하는 bottom-up 방법으로 전체 instance에 ..