분할 정복

2025-08-03 09:36

Status:

Tags: 알고리즘 소프트웨어 공학

분할(partition) 정복(conquer)

• 복잡한 문제를 유사한 형태의 작은 하위 문제로 분할
• 이들을 재귀적으로 해결한 뒤 결합
• 반복하여 전체 문제를 해결

1. Divide(분할): 문제를 크기가 작아질 때까지 동일한 형태의 여러 하위 문제로 나눈다.
2. Conquer(정복): 하위 문제가 충분히 작아지면 직접 해결하거나, 그렇지 않으면 재귀적으로 다시 분할 정복을 적용한다.
3. Combine(결합): 하위 문제의 해를 모아 원래 문제의 해를 구성한다.

• 더 넓은 범위에서 보았을 땐 모듈화 처럼 큰 프로그램을 작은 모듈 단위로 나누는 것도 분할 정복이라 볼 수도 있음
• 또한 실제 비즈니스에서도 복잡한 프로젝트를 작은 작업 단위로 분할해 할당(정복) 하는 식으로 해결
• 한번에 먹기 어려운 큰 문제를 먹을 수 있는 작은 조각으로 쪼개서 먹는다.

문제 해결위한 3단계 프레임 워크

1. 생각한다: 문제를 6하 원칙(누가, 언제, 어디서, 무엇을, 왜, 어떻게)을 사용하여 구체적으로 정의합니다
2. 쪼갠다: 문제 해결 과정을 최대한 세세한 행동 단위로 나눕니다. 이 단계는 자동화 과정에서 가장 중요하며, 많은 사람들이 간과하는 부분입니다
3. 선택한다: 쪼개진 각 과정을 자동으로 처리할 수 있는 적절한 도구를 선택하고 활용합니다

References

합병 정렬 퀵 정렬 모듈화

분할 정복 핸드북 분할 정복 모듈화 확장 핸드북_ 프로그래밍에서 현실 분야로의 적용