3월 8일 -각 기법의 사용 사례

그리디 알고리즘과 동적 계획법의 사용 사례와 재귀 변환 가능성

그리디 알고리즘 사용 사례

그리디 알고리즘은 각 단계에서 지역적으로 최적의 선택을 함으로써 최종적인 해답에 도달할 수 있는 문제에 적합하다. 주로 사용되는 경우는 다음과 같다:

• 문제의 최적해가 각 단계에서의 지역적 최적해의 집합으로 구성될 때
• 문제에 대한 해답을 여러 번의 선택으로 나눌 수 있으며, 각 선택은 이전 선택과 무관하게 최적의 선택이어야 할 때
• 예시
  • 활동 선택 문제(Activity Selection Problem): 시작 시간과 종료 시간이 주어진 활동들 중 가장 많은 활동을 선택하는 문제
  • 거스름돈 문제: 주어진 금액을 거슬러 줄 수 있는 최소한의 화폐 개수를 찾는 문제
  • 분할 가능 배낭 문제(Fractional Knapsack Problem): 물건을 쪼갤 수 있는 경우, 배낭에 담을 수 있는 최대 가치를 구하는 문제

동적 계획법 사용 사례

동적 계획법은 복잡한 문제를 작은 하위 문제로 나누어 해결할 수 있으며, 각 하위 문제의 해답을 저장하고 재사용함으로써 효율적으로 전체 문제의 해답을 구할 수 있는 문제에 적합하다. 주로 사용되는 경우는 다음과 같다:

• 문제가 중복되는 하위 문제들로 나누어질 수 있을 때
• 최적 부분 구조(Optimal Substructure)와 중복되는 하위 문제(Overlapping Subproblems)가 존재할 때
• 예시
  • 피보나치 수열: n번째 피보나치 수를 구하는 문제
  • 최장 공통 부분 수열(Longest Common Subsequence, LCS): 두 시퀀스에서 순서를 변경하지 않고 모두의 부분 시퀀스가 될 수 있는 가장 긴 시퀀스의 길이를 찾는 문제
  • 0-1 배낭 문제(0-1 Knapsack Problem): 물건을 배낭에 넣을 때, 가치의 합을 최대화하면서 무게 한도를 초과하지 않게 하는 물건의 조합을 찾는 문제

동적 계획법 문제를 재귀로 변환

동적 계획법으로 풀 수 있는 모든 문제는 재귀적 방식으로도 풀 수 있다. 실제로 동적 계획법의 핵심 아이디어 중 하나는 재귀적인 구조를 가지는 문제에 대한 효율적인 해결 방법을 제공하는 것이다. 그러나 재귀 호출만으로 문제를 해결할 경우 중복 계산으로 인한 비효율성이 발생할 수 있어, 메모이제이션과 같은 최적화 기법을 통해 이를 해결한다.

• 재귀적 방식의 한계: 순수한 재귀 호출은 중복 계산을 많이 수행하기 때문에, 특히 큰 입력값에 대해서는 비효율적일 수 있다.
• 메모이제이션 활용: 재귀 호출의 결과를 저장하여 재사용함으로써, 동적 계획법 문제를 효율적으로 해결할 수 있다.

결론

그리디 알고리즘과 동적 계획법은 각기 다른 유형의 문제에 적합한 해결 방법을 제공한다. 문제의 특성을 정확히 이해하고, 적절한 기법을 선택하여 사용하는 것이 중요하다. 동적 계획법 문제를 재귀적으로 접근할 경우, 메모이제이션과 같은 최적화 기법을 적용해야만 효율적인 해결이 가능하다.