탐욕적 기법

• 순간의 최적의 선택이 궁극적으로 최적의 선택이다.
• 단순한 방법도 문제 풀이에는 충분하다.
• 탐욕적 기법으로 만드는 방법은 간단하지만 탐욕적 기법으로 방법을 만드는 것은 결코 쉬운일이 아니다!
  

귀류법

• 가설이 아닐 때의 상황에서 모순을 보여줌으로써 오히려 가설이 맞다는 것을 증명하는 역설적인 기법

과정 요약

• 재귀호출의 재귀적 계산 방법
  n일때 n-1을 구해보고 n-1이 된다면 n-2를 구해보고...... 가서 n=1일때를 증명하여 다시 n일때의 식이 모두 성립한다는 것을 증명하는 방법이다.
  

• 재귀호출을 이용한 퀵정렬
  

• 완전탐색
  

• p class : 해결 다항시간
  np : 증명 다항시간
  np-Complete class : 사실상 다항시간 안에 해결 불가능

• np-Complete 처럼 보이는 문제도 연산회수를 줄인다면 p문제처럼 풀 수 있다.

• 

• 어떠한 문제의 시간복잡도가 n^2일 때 정렬을 하려면 O(nlogn)이고 비교는 O(n)의 시간복잡도를 갖는다.

• n개의 원소가 있는 집합에서 부분집합의 개수는 2^n개이다.