완전 탐색 알고리즘과 탐욕적 알고리즘

프로그래머스에서는 완전 탐색과 탐욕적 알고리즘을 이렇게 설명한다.

완전 탐색

무식해 보여도 사실은 최고의 방법일 때가 있지요. 가능한 모든 상황을 조사해 문제를 풀어보세요.

탐욕적 알고리즘

부분적인 최적해가 전체적인 최적해가 되는 마법! 언제나 통하지는 않지만, 이런 방법이 통하는 문제들을 만나보세요.

이해는 공부를 하는데 있어서 최선의 방법이라고 생각하기 때문에 차이점과 공통점을 공부하고 이해하고 넘어가보자 한다.

3가지 computational model

• 최적화 모델
• 통계적 모될
• 시뮬레이션 모델
  완전 탐색 과 탐욕법은 최적화 모델에 속한다.

최적화 모델이란?

• 극대화 하거나 극소화하는데 목적이 있는 함수
  ex) 서울에서 인천을 가는 시간의 최소값
• 제약사항 내에서 해결해야한다.

가장 인기있는 완전탐색법의 예시는 탐색 트리이다.

탐색트리

모든 노드를 탐색하기 때문에 트리가 커진다면 컴퓨팅 비용이 크다. 동적 계획법으로 대체되기도 한다.

탐욕법

완전탐색의 제약사항(비용)때문에 탐욕법을 사용하여 더 쉽게 최적화 할수 있다.
탐욕법은 연속적인 결정을 만들어낸다. 한 결정이 진행되면 다른 경우의 수는 제외된다.
모든 것을 탐색하지 않기 때문에 완전 탐색보다 빠르다. 하지만 모든 상황에서 최적해를 찾는 것은 아니다.

참조: https://medium.com/self-training-data-science-enthusiast/brute-force-algorithm-and-greedy-algorithm-13195d48e9bf