강의에서 탐욕적 선택속성이 각 단계에서의 탐욕스런 선택이 최종답을 구하기 위한 최적의 선택이라고 했는데요 풀어서 얘기하면 단계가 넘어갈때마다 선택을 할때 그 선택이 지금 당장 이득적이라면 그 선택을 하는거고 그 선택들을 하다가 결국에는 그 선택들이 최종답을 구하기 위한 최적의 선택이라는 건가요?
최적 부분구조가 있고 탐욕적 선택속성이 있으면 greedy algorithm이 최적의 솔루션을 보장한다고 했는데 여기서 의문이 듭니다. 탐욕적 선택속성이라는게 각 단계에서 탐욕스런 선택을한게 결국 최종답을 구하기 위한 최적의 선택이라고 했는데 최종답을 구하기 위한 최적의 선택인지를 알 수 있는게 어렵지 않나요? 인풋이나 그 문제의 주어진 부분문제 같은게 작다면은 알 수 있을꺼 같은데 어마어마하게 큰 상황이라면 탐욕적 선택 속성사용이 불가능하지 않나요?