Divide and Conquer (분할 정복)

정의

**Divide and Conquer (분할 정복)**는 복잡하고 거대한 문제를 작은 단위로 분해(분할)한 후, 각각을 해결(정복)하고 결과를 통합하는 문제 해결 전략.

핵심 원칙

큰 문제 → 작은 문제들로 분해 → 각각 해결 → 결과 통합

결과: 해결 불가능한 문제 → 해결 가능한 문제로 변환

알고리듘 관점의 분할 정복

고전적 예시

Merge Sort (병합 정렬)

[5, 2, 8, 1, 9]

1단계: 분할
├─ [5, 2] | [8, 1] | [9]
├─ [5] | [2] | [8] | [1] | [9]

2단계: 정복 (각 원소는 정렬됨)
├─ [2, 5] | [1, 8] | [9]
├─ [1, 2, 5, 8] | [9]

3단계: 통합
└─ [1, 2, 5, 8, 9]

시간복잡도: O(n) → O(n log n) 개선

Quick Sort (빠른 정렬)

Pivot 선택 → 작은 것/큰 것으로 분할 → 각 부분 재귀 처리 → 통합

AI/ML 분야의 분할 정복

Knowledge Graph Engineering의 혁명

Before (Monolithic 접근):

복잡한 지식 그래프 전체 (4만개 개념)
→ LLM에게 한 번에 던짐
→ LLM 실패 (0% 성공률)
→ 이유: 너무 복잡함 + 일관성 부족

After (Divide and Conquer 접근):

Step 1: 분할 (Divide)
전체 KG 정렬 문제 → 필요한 모듈들만 선택

Step 2: 정복 (Conquer)
선택된 모듈들만 집중 처리

Step 3: 통합 (Combine)
모듈 간 관계 연결

결과: 95% 성공률 (0% → 95%!!!)

모듈 선택 메커니즘

1단계: 문제 입력
질문: "이 문제 풀 때 어떤 모듈들이 필요할까?"

2단계: AI가 필요 모듈 선택
AI: "Module A, C, E가 필요해"

3단계: 선택된 모듈로만 처리
이제 4만개가 아니라 3개 모듈만 이해하면 됨
→ 관리 가능한 복잡도

4단계: 통합
선택된 모듈들로 원래 문제 해결

문제 범위 축소의 효과

복잡도 관점

문제 크기          처리 난이도
─────────────────────────────
전체 (40,000개)   불가능
선택된 모듈 (300개)  어려움
세부 모듈 (50개)   가능

선택된 모듈: 1/133 규모로 축소
→ LLM 성능: 0% → 95%로 증가

인지적 부담 (Cognitive Load)

전체 문제:
"4만개 개념 간의 모든 관계를 파악하고 정렬하세요"
→ 인간 전문가도 불가능

모듈화된 문제:
"생물학 모듈의 단백질-유전자 관계를 파악하세요"
→ 전문가가 집중 가능
→ 높은 정확도 달성

신경망/AI에서의 분할 정복

Hierarchical Task Decomposition (계층적 작업 분해)

원래 작업: 자동 온톨로지 구축

분해:
├─ 개념 추출 (Concept Extraction)
├─ 관계 식별 (Relationship Identification)
├─ 속성 정의 (Attribute Definition)
└─ 일관성 검증 (Consistency Checking)

각 서브태스크:
- 더 작은 입력 공간
- 명확한 목표
- 높은 성공률

멀티태스크 러닝 (Multi-Task Learning)

큰 모델 하나가 모든 것을 하는 대신
→ 특화된 작은 모델들이 각 태스크 담당
→ 전체 성능 향상

실무 문제 해결에서의 분할 정복

전자상거래 예시

문제: 상품 추천 시스템 구축

분할:

├─ 사용자 선호도 모듈
│  └─ 구매 이력, 검색 기록, 평점 분석
├─ 상품 특성 모듈
│  └─ 카테고리, 가격, 특성 분류
└─ 매칭 모듈
   └─ 사용자-상품 유사도 계산

정복:

각 모듈을 독립적으로 최적화
- 사용자 모듈: 정확한 선호도 파악
- 상품 모듈: 정확한 분류
- 매칭 모듈: 효과적인 유사도

통합:

모듈 결과들을 결합하여 최종 추천
→ 전체 시스템 성능 극대화

분할 정복의 조건

분할 가능성

문제가 독립적인 서브 문제들로 나뉠 수 있어야 함

통합 가능성

서브 문제의 해결책들이 통합 가능해야 함

성능 이득

분할로 인한 오버헤드 < 얻는 이득

분할 정복과 모듈성의 관계

모듈성 (Modularity)
└─ 시스템을 모듈로 설계

분할 정복 (Divide and Conquer)
└─ 문제를 부분으로 나누어 해결

둘은 상호 보완적:
모듈화된 시스템 → 분할 정복 적용 용이
분할 정복으로 설계 → 모듈화된 구조 자연 형성

철학적 의미: 우리 삶으로의 확장

Video 9의 통찰

"더 똑똑한 AI를 만드는 비결이
큰 문제를 잘게 나누는 것에 있다면

혹시 우리 삶의 다른 복잡한 문제들도
이 작게 생각하는 방식으로 풀어볼 수 있지 않을까?"

인생 문제의 분할 정복

예시 1: 경력 개발
전체 목표: "성공하는 전문가 되기" (추상적)
분할:
├─ 기술 습득 (작은, 명확한 목표)
├─ 네트워킹 (실행 가능한 액션)
├─ 프로젝트 경험 (측정 가능한 결과)

예시 2: 건강 관리
전체 목표: "건강하게 살기" (막연함)
분할:
├─ 운동 (주 3회, 30분)
├─ 식단 (균형잡힌 식사)
├─ 수면 (8시간 확보)

각 모듈을 따로 관리하면
전체 목표 자연스럽게 달성

관련 개념

• Knowledge Graph Engineering — 분할 정복이 적용된 사례
• Modularity — 분할 정복의 구조적 기초
• Human-AI Collaboration — 인간 구조 + AI 능력의 조합
• — 복잡도 관리
• — 문제 분해 기법

---

출처: AI인터시스브랜드 - Accelerating Knowledge Graph and Ontology Engineering (2025-12-13)

관련 영상: accelerating-kg-ontology

역사적 기원: Donald Ervin Knuth (알고리듬), John von Neumann (컴퓨터 과학)