Algorithm/Theory2 Monge array란? 정의 $n \times m$인 matrix가 존재할 때, $A[i, j] + A[k, l] \leqq A[i.l] + A[k,l]$이면 monge array라고 한다. ( $1 \leqq i < k \leqq n and 1 \leqq j 2021. 10. 31. Brute Force vs Dynamic Programming 1. Brute Force(완전탐색) Brute Force의 이름을 살펴보자면, Brute는 짐승을 의미한다. 일반적으로 짐승은 본능에 의지해 '무식함'을 나타낸다. 그렇다면 여기서 '무식함'은 무엇일까? 그것은 모든 경우의 수를 찾아보는 것이다. 아주 간단한 예로 1 ~ 100가지 숫자 중에서 원하는 숫자 하나를 찾아본다고 하자! 100을 찾고 싶다면, 1부터 쭉 조사해서 100번을 찾을 때까지 반복한다. 이런 알고리즘적 '무식함'을 Brute라고 표현한 것이다. 가장 유명한 문제로 '외판원 순회'라는 문제가 있다. 1,2,3,4,5라는 노드가 있고 모든 노드를 1번씩 방문하고 출발했던 노드로 되돌아 오는 최소의 경로를 찾는 문제이다. 아래와 같.. 2019. 4. 1. 이전 1 다음
