[알고리즘] Divide and Conquer

1. Divide and Conquer

• 문제를 하위 문제로 나누고, 하위 문제들을 각각 해결한 후, 각 해결책들을 결합하여 문제를 해결하는 알고리즘 입니다.

 

동작 원리

분할

• 원래의 문제를 여러 하위 문제로 나눕니다.
• 하위 문제는 원래 문제와 비슷합니다.

 

정복

• 각 하위 문제를 해결합니다.
• 재귀적으로 반복합니다.

 

결합

• 하위 문제의 해결책들을 결합하여 원래 문제의 해결책을 찾습니다.

 

장점

성능

• 하위 문제는 병렬 처리 가능 (서로 독립적입니다)

 

3. 문제

Merge Sort

• 주어진 두 리스트를 하나의 정렬된 리스트로 병합하는 알고리즘 입니다.
• 재귀적으로 반복하면서 전체를 정렬하는 방식입니다.

 

동작 방식

• 분할: 리스트를 반으로 나눕니다.
• 정복: 각 부분 리스트를 정렬합니다.
• 병합: 부분 리스트들을 하나의 정렬된 리스트로 병합합니다.

 

Binary Search

• 정렬된 리스트에서 특정 항목을 찾는 알고리즘 입니다.
• 찾고자 하는 항목을 찾거나 검색 범위가 더 이상 줄어들지 않을 때까지 반복합니다.

 

동작 방식

• 분할: 리스트를 반으로 나누어 찾고자 하는 항목이 있는지 체크
• 정복: 찾고자 하는 항목이 있는 부분 리스트를 선택 (검색 범위 좁히기)
• 결과: 반복적으로 검색 범위를 좁혀가면서 특정 항목을 찾습니다.

 

Binomial coefficient (이항 계수)

• 이항식 (a+b)^n을 전개했을 때 각 항의 계수
• 이는 주어진 크기의 조합의 가짓수와 일치함

C(n,k)= n! / k!(n−k)!
​

 

동작 방식

• 분할: 팩토리얼 변환 및 값 줄여서 호출
• 정복: 팩토리얼 값 구하기
• 결과: 재귀적으로 값 만들어가면서 최종 값 만들기

public static int comb(int n, int k) {        
    if (n < k) return 0;
    if (n == 0 || k == 0 || n == k) return 1;        

    if (dp[n][k] > 0) return dp[n][k];

    return dp[n][k] = comb(n-1, k) + comb(n-1, k-1);
}

 

출처

• Wiki - Divide and conquer algorithm
• Wiki - Binary Search algorithm