Greedy Algorithm-알고리즘 12

2023.08.20 - [CS(Computer Science)/Algorithm] - DynamicProgramming(DP)-알고리즘08

 

그리디 알고리즘(탐욕법)

그리디 알고리즘(탐욕법):

매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 방법이다. 그러니까 어떤 문제를 풀기위하여 여러 단계를 거쳐 갈때, 각 단계에서 최적의 선택을 선택 해 나가면서 최적해에 도달하는 방법이다.

사용 예시) 

A에서 B를 거쳐서 C까지 가는 최단경로는?

A->B 최적의 방법:150km

B->C로 최적의 방법: 140km

따라서 A->B->C의 최단경로는 290km

 

 

그러나 그리디 알고리즘은 언제나 최적의 해답을 구하지는 못한다. 아래를 보자.

 

다음 트리에서 가장 숫자가 큰 노드를 선택 하여라.(ROOT NODE 0 에서 부터 내려가면서 탐색)

 

출처:https://velog.io/@falling_star3/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm

어떠한 방법으로든 정답은 100이다.

하지만 그리디 알고리즘을 이용하면

맨처음에 3 과 10 중 10을 선택하여 10으로 이동->

7과 8중 더 큰 8을 선택->

자식 노드 없음->

정답을 8 로 인식.

 

 

무슨 문제에 사용?

그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 사용된다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

 

 

탐욕 선택 속성(greedy choice property)

각 단계에서 최적해를 구했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우.
 =각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 뜻

 

최적 부분 구조(optimal substructure)

전체의 해가 부분 문제의 해로 구성 된것.
ex) 어떤 문제의 최적해는 그 해를 구하기 위해 거치는 단계들의 최적해를 포함한다. 위의 A->B->C예시를 참고하면 이해가 쉽다.

2023.08.20 - [CS(Computer Science)/Algorithm] - DynamicProgramming(DP)-알고리즘08

아래에 최적 부분 구조에 대한 설명이 있다.

DynamicProgramming(DP)-알고리즘08

 

문제예시(그리디로 풀 수 있는):

• Activity selection problem
• Minimum spanning tree
• Fractional knapsack prob
• Huffman codes
• Dijkstra's algorithm for shortest path