그리디 정리 및 예제
그리디란? 그리디 알고리즘은 현재의 최적 해를 구하는 알고리즘이다. 즉, 미래를 생각하지 않고 현재에서의 최선의 값을 구하는 방식인데 이는 전체 구조에서의 최적 해가 될 수 없기에 근사 알고리즘이라고도 한다. 최적해를 위한 조건 근사 알고리즘인데 어떻게 정확한 값을 요구하는 코테에서 사용할 수 있을까? 해당 문제로 인해 코테에서 그리디를 사용하기 위해서는 2가지의 조건이 필요하다. 현재의 결정이 미래에 영향을 주지 안는다. 부분의 최적 해가 전체의 최적 해가 된다. 1 조건에 따라 서울에서 대전까지의 최적 경로 결정은 미래의 대전에서 부산까지의 최적해 결정에 영향을 주지 않는다. 2 조건에 따라 서울 대전의 최적해 및 대전 부산의 최적해는 결국 전체의 최적 해가 된다. 그리디 전략 그리디의 전략은 정렬이..