[코드잇-알고리즘2 : 알고리즘 패러다임] 2. Divide and Conquer(분할 정복)

본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 두번째 주제인 '알고리즘 패러다임'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/trees?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz

---

1~2. Divide and Conquer 소개

1) Divide and Conquer의 개념

- 어떤 문제가 있는데 답을 바로 알아내기에는 문제가 너무 크다고 가정하면, 이 문제를 나눠서 풀어야 한다.

- 즉, 기존 문제랑 같은 형태를 가진 부분 문제로 나눠서 해결하는 것

- 각 부분 문제를 풀고 부분 문제에 대한 솔루션들을 이용해서 기존 문제를 해결하면 됨

2) Divide and Conquer 개념의 구조적인 설명

어떤 문제를 해결하는 f를 만들고 싶다고 가정

- f는 파라미터로 인풋 x를 받는데, 이 문제는 단순하게 해결이 안되어 Divide & Conquer를 사용하고 싶음

단계 1 : Divide

- 인풋 x를 x1, x2로 나눈다.

단계 2: Conquer, 부분문제를 정복한다.

- 부분 문제를 해결하기 위해 f(x1)과 f(x2)를 한다. 이렇게 해서 A라는 답과 B라는 답이 나왔다고 가정

 

- f(x1)이 너무 크면 또 1~3단계를 반복한다.

단계 3: Combine, 최종 계산

- 부분 문제를 각각 정복해서 솔루션 두 개가 나왔는데, 마지막으로 Combine 단계에서는 그 두 솔루션 A와 B를 이용해서 기존 문제를 해결하는 f(x)를 계산하면 됨