그리드 알고리즘

어떤 선택을 할 때 그 순간만을 고려해서 가장 좋은 경우를 고르는 방법이다.

1. 여러 경우 중 하나를 결정해야 할 때마다 그순간이 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하여 해결한다.

2. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만 , 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여 , 그것이 최적이라는 보장은 없다.

예시 )
https://freshrimpsushi.tistory.com/1434

왼쪽 0에서 시작해 오른쪽 1에 도착하는 경로를 찾는 문제가 있다고 하자. 그냥 찾는 게 아니라 가장 적은 노드를 거쳐간다고 하면 최적해는 0-A-C-E-1(3)이 될 것이다. 그러나 그리드 알고리즘은 그 순간 순간 가장 멀리 갈 수 있는 길을 고른다. 따라서 이 문제를 그리드 알고리즘으로 푼다면 그 해는 0-B-D-F-G-H-1(5)이고, 최적해와 비교해 2번의 비용이 더 발생하게 된다. 가장 처음 선택이 0-B이 아니었다면, 하다 못해 D-F가 아니라 D-E만 골랐어도 더 좋은 해를 고를 수 있었을 것이다.

단순하게 바로앞의 로직만 생각해서 당장을 생각했을땐 괜찮은 방법일지는 몰라도 나중을 생각했을때는 좋지 못한 알고리즘이 될 수 있다

그래서 보통은 그리디 알고리즘으로 우선적으로 설계?? 를 하고 풀어본 후 개선된 알고리즘을 만들어 간다.