자료구조

수학적 알고리즘

스트링 검색 알고리즘

그래프

동적 계획법

1. 그리디 알고리즘과 동적 계획법

• 그리디 알고리즘 : 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 설계 기법. 최적 부분 구조와 그리디 선택 두 가지의 속성을 가지고 있어야 함
  • 최적 부분 구조 : 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우 문제 P가 최적의 부분 구조를 가짐을 의미
  • 그리디 선택 : 문제 P에 대해 지역적 최적 솔루션을 반복적으로 선택하여 전체 최적 솔루션을 구할 수 있는 경우를 의미
• 동적 계획법 : 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법
• 그리디 알고리즘과 동적 계획법의 차이

2. NP 이론과 근사 알고리즘

2.1. P문제와 NP문제

• 다항 시간 알고리즘 : 최악의 경우에도 시간 복잡도 함수가 입력 크기에 대한 다항식에 의해 한정되는 알고리즘