특징#
: 문제를 두 단계 1) 분할 과 2) 정복으로 나눠서 해결하는 것
분할- 주어진 문제를 여러개의 부분 문제로 나눈다
- 문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용
정복- 분할한 문제를 이용하여 문제를 해결
- 문제의 크기가 줄어든다면(
N=1)? 바로 답을 구할 수 있음
→ 재귀 호출의base case(탈출조건)과 같다 - 더 큰 케이스에서
base case를 이용하여 문제의 답을 구함
조건#
- 문제를 부분으로 쪼갤 수 있을 때
- 쪼갠 문제를 합치는 것이 월등하게 빠를 때
ex) 병합정렬, 이분탐색, 거듭제곱연산…
예시: 히스토그램에서 가장 큰 직사각형 구하기#
문제#
[2104: 부분배열 고르기]
[1463: 1로 만들기]
[1149: RGB 거리]
업데이트 중…
🗪 댓글