그리디알고리즘1 그리디 알고리즘 그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶은 경우, 이때의 최적해는 무엇일까? 아래처럼 5 -> 7 -> 9로 거쳐가면 21이라는 최댓값이 나온다. 하지만 그리디 알고리즘은 어떻게 갈까? 놀랍게도 매순간 선택지 중 가장 최적의 해만 고른다. 루트 노드 5에서 시작해서 7, 10, 8 중에 가장 큰 10을 선택하고 4, 3중에 4를 선택한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 .. 2023. 10. 22. 이전 1 다음
