[알고리즘] Divide and Conquer

1. Divide and Conquer

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

 

동작 원리

분할

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

 

정복

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

 

결합

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

 

장점

• 성능: 하위 문제는 서로 독립적이므로 병렬 처리 가능

 

3. 문제

Merge Sort

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

 

동작 방식

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

 

Binary Search

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

 

동작 방식

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

 

binomial conefficient (이항 계수)

• 주어진 조합의 가짓수 구하기

 

 

 

 

출처

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