[알고리즘] Divide and Conquer

1. Divide and Conquer

• 전체 문제를 하위 문제로 나누고, 하위 문제들을 각각 해결한 후, 각 문제의 해를 결합하여 문제를 해결하는 알고리즘

 

동작 원리

1. 분할: 원래의 문제를 여러 하위 문제로 나누기 (하위 문제는 원래 문제와 비슷함)
2. 정복: 각 하위 문제를 해결하기 (재귀적으로 반복)
3. 결합: 하위 문제의 해결책들을 결합하여 원래 문제의 해 찾기

 

장점

• 성능: 병렬 처리 가능 (서로 독립적)

 

2. Merge Sort

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

 

동작 방식

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

 

3. Binary Search

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

 

동작 방식

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

 

코드

public static int binarySearch(int target, int l, int r) {
    if (l > r) return -1;
    
    int m = (l+r)/2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binarySearch(target, l, mid-1);
    
    return binarySearch(target, mid+1, r);
}

 

4. Binomial coefficient (이항 계수)

• 이항식 (a+b)^n을 전개했을 때 각 항의 계수
• ✅ 이는 주어진 크기의 조합의 가짓수와 일치함
• ➡️ C(n,k)= n! / k!(n−k)!

 

동작 방식

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

 

코드

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