문제해결 패러다임

Alogoritm

문제를 해결하기 위한, 명확하며 순서화 된 명령

• 입력
• 출력
• 명확성
• 유한성
• 효과성

문제 해결 패러다임 : 탐욕

최적해를 구하는 데에 사용되는 근사적인 방법
일반적으로 계산이 빠름

여러 경우 중 하나를 결정해야 할 때마다, 그 순간에 최적으로 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

• 작동 실용성 조건
  • 탐욕스런 선택
    앞의 단계의 선택이 이후 단계의 선택에 영향을 주지 않는다.
  • 최적 부분 구조
    문제에 대한 최적해가 부분 문제에 대해서도 최적해이다.

문제 해결 패러다임 : 분할 - 정복

분할 가능한 문제를 독립적인 작은 문제들로 분할한 다음,
각각의 부분 문제를 해결정복하고 이를 최정족으로 결합하여 문제의 해를 구하는 방법
일반적으로 재귀또는 스택, 큐 자료 구조를 활용하여 구현된다.

• 특징
  • 병렬 프로그래밍 가능
  • 재귀로 인한 함수 호출 오버헤드, 스택 오버플로 주의

문제해결 패러다임 : 동적 계획법

복잡한 문제를 여러 개의 나누어 푸는 방법 각 문제가 서로 종속적

• 메모이제이션
  이전에 계산한 값을 메모리에 저장하여 동일한 계산 반복 회피
• 타뷸레이션
  필요 여부와 관계 없이 미리 계산해 두어 동일한 계산 반복 회피

문제해결 패러다임 : 백트래킹

해를 찾는 도중, 해가 아니어서 막힌다면 이전 단계로 되돌아가서 다시 해를 찾아가는 방법