[자료구조] 완전검색, 그리디 알고리즘

완전 검색 (Exhaustive Search)

• = Brute-force, generate-and-test

주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직합니다.

 

탐욕 알고리즘 (Greedy Algorithm)

• 최적 해를 구하는 데 사용되는 근시안적인 방법

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

 

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

 

일반적으로, 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됩니다.