1 : 완전 검색, 그리디 알고리즘

완전 검색 (Exhaustive Search)

• = Brute-force, generate-and-test

• 모든 경우의 수를 생성하고 테스트하는 방법.
• 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직함.

탐욕 알고리즘 (Greedy Algorithm)

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

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

• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 게속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없음.
• 일반적으로, 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됨.

출처: SW Expert Academy - Learn - Course - Programming Intermediate

SW Expert Academy - Programming Intermediate course