• 내용 설명
  
  • 순간 순간마다 하는 선택이 최선이라 가정하고 접근해 나아가는 알고리즘
    
  • 따라서 따질 수 있는 조건이 매우 제약적임(순간순간마다 하는 선택이 최적인 경우에만 사용 가능)
    
• 문제
  
  • 백준Judge 11047번 - 동전 0
    
  • 더블릿 19단계 - knapsack
    
    

• 내용 설명
  
  • 해결 할 수 없는 문제를 작은 문제로 쪼개어서 해결 한 뒤 그 값을 처리하는 알고리즘
    
  • DP는 여러 번 연산을 해야될 경우 값을 저장해놓는데, 분할정복은 그렇지 않음
    

function F(x):
	if F(x)의 문제가 간단 then:
		return F(x)을 직접 계산한 값
	else:
		x 를 y1, y2로 분할
		F(y1)과 F(y2)를 호출
		return F(y1), F(y2)로부터 F(x)를 구한 값 

• 문제
  
  • 백준Judge 2751번 - 수 정렬하기2
    
  • 백준Judge 2630번 - 색종이 만들기